單向連結的缺點

前一章所提及的單向連結, 可以無限的擴充長度, 只要記憶體不要爆掉就好. 但有一個缺失, 就是無法反向列印回來

解決方案

單向連結無法反向列印, 其實是可以用其他演算法解決. 但這演算法實在是太耗費時間了, 所以才會有如下的結構.

下面是每個節點又多一個記錄前一個節點的變數 prev, 如果就可以正反向列印了

代碼

public class DoubleLink {
    public static void main(String[] args){
        Node root=new Node();
        Node index=root;
        Scanner in=new Scanner(System.in);
        int x=0;
        while(true){
            System.out.print("請輸入數字(-1離開) : ");
            x=in.nextInt();
            if(x==-1)break;
            index.d=x;
            index.next=new Node();
            index.next.prev=index;
            index=index.next;
        }
        //正向列印
        index=root;
        System.out.println("正向列印......");
        while(index.next!=null){
            System.out.printf("%d ", index.d);
            index=index.next;
        }
        System.out.println();
        //反向列印
        index=root;
        while(index.next!=null)index=index.next;
        System.out.println("反向列印......");
        while(index.prev!=null){
            System.out.printf("%d ", index.prev.d);
            index=index.prev;
        }
        System.out.println();
    }
}
class Node{
    Node prev;
    int d;
    Node next;
}
結果 : 
請輸入數字(-1離開) : 10
請輸入數字(-1離開) : 20
請輸入數字(-1離開) : 30
請輸入數字(-1離開) : 40
請輸入數字(-1離開) : 50
請輸入數字(-1離開) : -1
正向列印......
10 20 30 40 50 
反向列印......
50 40 30 20 10