将单个链接列表转换为双链接列表

Question

我在这里为一个拼贴程序的单个链接列表。这运行完美，但我想知道如何使它成为一个双链表。我真的不知道什么是双链接，或者如何创建链接。任何帮助将不胜感激...

有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()); 
} 
} 

Answer 1

双向链表通过引用前一个节点而不是下一个节点来进一步获取单链表。

我承认我对你的代码有点困惑，因为它看起来像你有一个私人类的节点，然后是另一个公共类。为了使它成为一个双向链表，将另一个Node实例变量添加到引用前一个节点的Node类中，然后在添加新节点时更新此变量。

Answer 2

双向链表只是一个链表，其中每个元素都有next和prev mebers，指向前后的元素，而不仅仅是单个链表之后的元素。

所以你的列表转换为一个双向链表，只是改变你的节点是：

private class Node 
    { 
    Picture data; 
    Node pNext; 
    Node pPrev; 
    }; 

并遍历列表时，每一个新的节点上的引用添加到前一个节点。