鏈結串列—雙向環狀鍊結串列之介紹與範例 - 筆記長也

鏈結串列—雙向環狀鍊結串列之介紹與範例

2018-03-01 22:45:18   資料結構

環狀雙向鏈結串列

雙向之鏈結串列有別於單向鏈結串列,他不僅指向後一個節點,也會指向前一個節點。

而雙向鏈結串列通常具有三個欄位,左鏈結(llink)、資料(data)、右鏈結(rlink)。請參考下圖:

而環狀雙向鏈結則是將head與末端相連,則稱為環狀雙向鏈結。若頭尾沒有相連,也能稱為雙向鏈結。

當一個雙向鏈結串列為空串列時,該串列僅有一個head,而且若為環狀,則head的左右鏈結都會指向自己

操作(以Java實作)

本篇文章我們主要介紹環狀雙向鏈結串列之實作

類別與實體變數之宣告

這裡與前面串列的實作差不多,僅實體變數上有些不同,故不再贅述

class Node3{
    
    public int data;
    public Node3 llink,rlink;
    
}
class DoubleLinkList {
    
    static Node3 ptr, head, current, prev, tail,first;
    static Scanner key = new Scanner(System.in);
    
    DoubleLinkList(){
        
        head=new Node3();
        head.llink=head;
        head.rlink=head;
        
    }
}

如需知道該類別之宣告全貌,請參考最後的完整程式碼

加入節點至前端

假設要加入"鑽"至串列之首:

1.先取得first = head.rlink (之後的head.rlilnk會被指向其他地方,先取得first)

2.將ptr的右鏈結指向head.rlink

3.將ptr的左鏈結指向head

4.將head的右鏈結指向ptr

5.將first的左鏈結指向ptr

    public static void insert_h(){
        
        ptr=new Node3();
        System.out.println("請輸入您想加入的資料:");
        ptr.data=key.nextInt();
        first=head.rlink;
        ptr.rlink=head.rlink;
        ptr.llink=head;
        head.rlink=ptr;
        first.llink=ptr;
        System.out.println("您的資料已加入!");
        
    }

加入節點至末端

假設我們要加入"牌"字至串列末端:

1.將末端設為head.llink (tail=head.llink)

2.將ptr右鏈結指向tail.rlink (實際上就是head)

3.將tail的右鏈結指向ptr (tail.rlink=ptr)

4.將ptr的左鏈結指向tail

5.將head的左鏈結指向ptr

    public static void insert_c(){
        
        ptr=new Node3();
        System.out.println("請輸入您想加入的資料:");
        ptr.data=key.nextInt();
        tail=head.llink;
        ptr.rlink=head;
        tail.rlink=ptr;
        ptr.llink=tail;
        head.llink=ptr;
        System.out.println("您的資料已加入!");
        
    }

加入節點依照資料由大到小

假設要加入節點"87":

1.找到要加入的位置 (current!=head) && (current.data>=ptr.data)

2.將ptr的右鏈結指向current

3.將ptr的左鏈結指向prev

4.將prev的右鏈結指向ptr

5.將current的左鏈結指向ptr

    public static void insert_f(){
        
        ptr=new Node3();
        System.out.println("請輸入您想加入的資料:");
        ptr.data=key.nextInt();
        prev=head;
        current=head.rlink;
        while ((current!=head) && (current.data>=ptr.data)){
            
            prev=current;
            current=current.rlink;
            
        }
        
        ptr.rlink=current;
        ptr.llink=prev;
        prev.rlink=ptr;
        current.llink=ptr;
        System.out.println("您的資料已加入!");
    }

刪除前端節點

1.current = head.rlink (第一個節點為head.rlink,head沒有東西)

2.將head的右鏈結指向current.rlink (head.rlink=current.rlink)

3.current.rlink.llink=current.llink

4.current=null

    public static void del_h(){
        
        current=head.rlink;
        head.rlink=current.rlink;
        current.rlink.llink=head;
        current=null;
        System.out.println("資料已被刪除");
        
    }

刪除末端節點

1.tail=head.llink

2.tail.llink.rlink=tail.rlink (實際上就是head)

3.將head的左鏈結指向tail.llink

    public static void del_c(){
        
        tail=head.llink;
        tail.llink.rlink=tail.rlink;
        head.llink=tail.llink;
        tail=null;
        System.out.println("資料已被刪除");
        
    }

刪除指定節點

1.找到要刪除的節點 (current.rlink!=head) && (current.data!=del)

2.將prev的右鏈結指向current.rlink

3.current.rlink.llink=prev

4.current=null

    public static void del_f(){
        
        System.out.println("請輸入要刪除的資料:");
        int del = key.nextInt();
        prev=head;
        current=head.rlink;
        while ((current.rlink!=head) && (current.data!=del)){
            
            prev=current;
            current=current.rlink;
            
        }
        if (current==head)
            System.out.println("資料找不到");
        else{
            
            prev.rlink=current.rlink;
            current.rlink.llink=prev;
            current=null;
            System.out.println("資料已被刪除!");
        
        }
           
    }

完整程式碼

package LinkLIst;

import java.util.Scanner;

class Node3{
    
    public int data;
    public Node3 llink,rlink;
    
}

class DoubleLinkList {
    
    static Node3 ptr, head, current, prev, tail,first;
    static Scanner key = new Scanner(System.in);
    
    DoubleLinkList(){
        
        head=new Node3();
        head.llink=head;
        head.rlink=head;
        
    }
    
    public static void insert_h(){
        
        ptr=new Node3();
        System.out.println("請輸入您想加入的資料:");
        ptr.data=key.nextInt();
        first=head.rlink;
        ptr.rlink=head.rlink;
        ptr.llink=head;
        head.rlink=ptr;
        first.llink=ptr;
        System.out.println("您的資料已加入!");
        
    }
    
    public static void insert_c(){
        
        ptr=new Node3();
        System.out.println("請輸入您想加入的資料:");
        ptr.data=key.nextInt();
        tail=head.llink;
        ptr.rlink=head;
        tail.rlink=ptr;
        ptr.llink=tail;
        head.llink=ptr;
        System.out.println("您的資料已加入!");
        
    }
    
    public static void insert_f(){
        
        ptr=new Node3();
        System.out.println("請輸入您想加入的資料:");
        ptr.data=key.nextInt();
        prev=head;
        current=head.rlink;
        while ((current!=head) && (current.data>=ptr.data)){
            
            prev=current;
            current=current.rlink;
            
        }
        
        ptr.rlink=current;
        ptr.llink=prev;
        prev.rlink=ptr;
        current.llink=ptr;
        System.out.println("您的資料已加入!");
    }
    
    public static void del_h(){
        
        current=head.rlink;
        head.rlink=current.rlink;
        current.rlink.llink=head;
        current=null;
        System.out.println("資料已被刪除");
        
    }
    
    public static void del_c(){
        
        tail=head.llink;
        tail.llink.rlink=tail.rlink;
        head.llink=tail.llink;
        tail=null;
        System.out.println("資料已被刪除");
        
    }
    
    public static void del_f(){
        
        System.out.println("請輸入要刪除的資料:");
        int del = key.nextInt();
        prev=head;
        current=head.rlink;
        while ((current.rlink!=head) && (current.data!=del)){
            
            prev=current;
            current=current.rlink;
            
        }
        if (current==head)
            System.out.println("資料找不到");
        else{
            
            prev.rlink=current.rlink;
            current.rlink.llink=prev;
            current=null;
            System.out.println("資料已被刪除!");
        
        }
           
    }
    
    
    public static void print(){
        current=head.rlink;
        while(current!=head){
            System.out.println(current.data);
            current=current.rlink;
        }
    }
        
    
    public static void main(String[] args) {
        
        DoubleLinkList obj = new DoubleLinkList(); 
        System.out.println("1.插入前端/2.插入末端/3.由大至小插入/4.刪除前端/5.刪除末端/6.刪除指定/7.列出");
        Scanner doing = new Scanner(System.in);
        while (true){
            
            int don=doing.nextInt();
            switch(don){
                case 1:
                    obj.insert_h();
                    break;
                case 2:
                    obj.insert_c();
                    break;
                case 3:
                    obj.insert_f();
                    break;
                case 4:
                    obj.del_h();
                    break;
                case 5:
                    obj.del_c();
                    break;
                case 6:
                    obj.del_f();
                    break;
                case 7:
                    obj.print();
                    break;
            
            }
            
            
        }
        
    }
    
}

結論

雙向的串列與單向的差異僅在於單向只指向下一個節點(node.next),而雙向則同時指向前後的節點(node.llink、node.rlink),實際上的操作並沒有太大的差異。關於一些串列的應用,請參考後續的文章。

關於作者


長也

資管菸酒生,嘗試成為網頁全端工程師(laravel / React),技能樹成長中,閒暇之餘就寫一些筆記。 喔對了,也愛追一些劇,例如火神跟遺物整理師,推推。最愛的樂團應該是告五人吧(?)