我这里有一个用于制作拼贴画的程序的单个链接列表。这运行完美，但我想知道如何使其成为双链表。我真的不知道什么是双链接，也不知道如何创建双链接。任何帮助将不胜感激...
有3个班级。
class LinearCollage
{
private Picture myArray[];
private class Node
{
Picture data;
Node pNext;
};
private Node pFirst;
private Node pLast;
private int nPictures;
private Picture clipboard;
public LinearCollage()
{
pFirst = null;
pLast = null;
nPictures = 0;
}
public void addPictureAtEnd(Picture aPictureReference)
{
Node temp = new Node();
temp.data = aPictureReference;
temp.pNext = null;
if( pLast == null )
{
pLast = temp;
pFirst = temp;
}
else
{
pLast.pNext = temp;
pLast = temp;
}
nPictures++;
}
public Picture makeCollage()
{
int collageHeight = 400;
int collageWidth = 400;
for( Node finger = pFirst; finger != null; finger = finger.pNext )
{
System.out.println("Process Picture " + finger.data);
}
Picture retval = new Picture(collageHeight,collageWidth);
int i = 0;
for( Node finger = pFirst; finger != null; finger = finger.pNext )
{
System.out.println("Process Picture " + finger.data);
finger.data.compose(retval, 50*i, 50*i);
i++;
}
return retval;
}
public void cutMiddle()
{
int cutIndex = nPictures-1;
clipboard = myArray[cutIndex];
for( int i = cutIndex; i < nPictures - 1; i++ )
{
myArray[i] = myArray[i + 1];
}
nPictures--;
}
public void cutEnd()
{
int cutIndex = nPictures;
clipboard = myArray[cutIndex];
for( int i = cutIndex; i<nPictures - 1; i++)
{
myArray[i] = myArray[i + 1];
}
nPictures--;
}
public void pasteEnd()
{
myArray[nPictures] = clipboard;
nPictures++;
}
public boolean isFull()
{
return false;
}
public boolean isEmpty()
{
return nPictures == 0;
}
}
import java.util.Scanner;
class LineCollageMaker
{
public static void main(String a[])
{
LinearCollage myCollage;
Scanner uiInput = new Scanner(System.in);
myCollage = new LinearCollage();
FileChooser.pickMediaPath();
boolean inputting = true;
while( inputting )
{
System.out.println("Another picture? Type Y if so.");
String answer = uiInput.next();
if(answer.equals("Y"))
{
Picture pin = new Picture(FileChooser.pickAFile());
myCollage.addPictureAtEnd(pin);
}
else
{
inputting = false;
}
}
Picture firstToShow = myCollage.makeCollage();
firstToShow.show();
//YOU Code the user inteface loop and dispatch to methods
//of myCollage here..
boolean done = false;
while( !done )
{
System.out.println("MENU (CASE SENSITIVE!)");
System.out.println("CM - cut middle and move it to the clipboard");
System.out.println("PE - paste clipboard to end");
System.out.println("CE - cut end and move it to clipboard");
System.out.println("XX - stop running this program");
String command = uiInput.next();
if(command.equals("XX"))
done = true;
else if(command.equals("CM"))
{
if(myCollage.isEmpty())
{
System.out.println("Can't cut from an empty collage.");
}
else
{
myCollage.cutMiddle();
myCollage.makeCollage().show();
}
}
else if(command.equals("PE"))
{
if(myCollage.isFull())
{
System.out.println("Can't paste to an empty collage.");
}
else
{
myCollage.pasteEnd();
myCollage.makeCollage().show();
}
}
else if(command.equals("CE"))
{
if(myCollage.isEmpty())
{
System.out.println("Can't copy from an empty collage.");
}
else
{
myCollage.cutEnd();
myCollage.makeCollage().show();
}
}
else
System.out.println("Unrecognized command. Try again.");
}
}
}
public class Node
{
//le class variables
private Picture myPic;
private Node next;
//le constructors
public Node(Picture heldPic)
{
myPic=heldPic;
next=null;
}
public void setNext(Node nextOne)
{
this.next=nextOne;
}
public Node getNext()
{
return this.next;
}
public Picture getPicture()
{
return this.myPic;
}
//le methods
public void drawFromMeOn(Picture bg)
{
Node current;
int currentX=0, currentY=bg.getHeight()-1;
current = this;
while (current != null)
{
current.drawMeOn(bg,currentX, currentY);
currentX = currentX + current.getPicture().getWidth();
current=current.getNext();
}
}
private void drawMeOn(Picture bg, int left, int bottom)
{
this.getPicture().blueScreen(bg, left, bottom-this.getPicture().getHeight());
}
}
双向链表只是一个链表，其中每个元素都有下一个和上一个成员，指向其之前和之后的元素，而不仅仅是单个链表中其之后的元素。
因此，要将列表转换为双向链表，只需将节点更改为：
private class Node
{
Picture data;
Node pNext;
Node pPrev;
};
并且在迭代列表时，在每个新节点上添加对前一个节点的引用。
双向链表比单链表更进一步，它还引用了前一个节点，而不仅仅是下一个节点。
我承认我对你的代码有点困惑，因为看起来你有一个 Node 的私有类，然后还有另一个公共类。要使其成为双向链表，请将另一个 Node 实例变量添加到引用前一个节点的 Node 类中，然后在添加新节点时更新此变量。
您可以通过称为基于 XOR 的链表的概念将单链表转换为双链表。 XOR 真值表的美妙之处使其适合这种用例。
检查一下：https://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/
为了构建之前的答案，您将希望在内部 Node 类中拥有下一个和上一个节点。然后，您将在节点类中建立一个参数化构造函数来设置所有内容（如果您所拥有的有效，则并非真正必要）。实现双链表时最重要的事情之一，如果您希望能够删除元素，则需要将 Node.previous.next 设置为 Node.next，并且需要将 Node.next.previous 设置为设置为 Node.previous。这是因为链表现在有两个链接，因此您必须向前和向后连接。请注意，这是假设您在第一个和最后一个保留了最少的指针。如果您要实现额外的下一个和上一个指针，这将使用一些额外的内存，您还可以将删除重新表述为设置当前的下一个和当前的上一个，然后将上一个（如果存在）设置为当前的上一个。另外，在您的添加上和删除方法，除了链接下一个节点之外，您还必须确保将 pLast.prev 链接到它的新前一个节点。这是因为您现在有两个链接需要管理，而不是一个。