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

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

2018-02-28 17:48:49   資料結構

鏈結串列

上一篇文章我們已經基本的介紹過了鏈結串列,請參考上一篇文章「串列—單向鏈結串列之介紹與範例」。

環狀鏈結串列

之前在佇列時有學過"環狀佇列",同理環狀串列也是將資料的末端與資料的前端連在一起。(在環狀佇列的示意圖很像圓餅圖,但意思都是循環)

操作(Java實作)

Java無法直接操作指標,故以物件設計。

類別與實體變數

class Node1{
    public int data;
    public Node1 next; 
}

這是節點之類別,命名為Node1只是為了與上一篇的Node做出區別,沒有特別意義。

    static Node1 ptr,head,current,prev,forward;
    static Scanner input = new Scanner(System.in);
    
    CircularLinkList(){
        head=new Node1();
        head.next=head; //當一開始創立串列,就要將自己與自己串聯
    
    }

此為整個串列之類別與節點之實體變數,CircularLinkList則為該類別之建構子,如需看這兩個類別的宣告全貌,請參考下面的完整程式碼。

加入節點至前端

宣告一個新節點,我們以9為例:

1.將ptr指向head.next

2.將head指向ptr

public static void insert_h(){ //插入至前端
        
        ptr=new Node1();
        System.out.println("請輸入要插入的資料:");
        ptr.data=input.nextInt();
        ptr.next=head.next;
        head.next=ptr;
        System.out.println("您的資料已經加入成功!");
    
    }

加入節點至末端

宣告新的節點,我們以7為例:

1.找到資料末端 (current.next!=head)

2.將末端current指向到ptr

3.將ptr指向head

    public static void insert_c(){  //插入至末端
   
        ptr=new Node1();
        System.out.println("請輸入要插入的資料:");
        ptr.data=input.nextInt();
        current=head.next;
        while(current.next!=head){  //與單向串列不同,不是null而是head
            
            current=current.next;
        
        }
        
        current.next=ptr;
        ptr.next=head;
        System.out.println("您的資料已經加入成功!");
    
    }

由大至小加入

我們以插入7為例:

1.找到資料符合的插入點 (current!=head) && (current.data>=ptr.data)

2.將ptr指向current

3.將prev指向ptr

   public static void insert_f(){  //由大至小插入
        
        ptr=new Node1();
        System.out.println("請輸入要插入的資料:");
        ptr.data=input.nextInt();
        prev=head;
        current=head.next;
        while((current!=head) && (current.data>=ptr.data)){
            
            prev=current;
            current=current.next;
        
        }
        ptr.next=current;
        prev.next=ptr;
        System.out.println("您的資料已經加入成功!");
    
    }

刪除前端

我們以刪除4為例:

1.找到head所指向的節點為current

2.將head指向current.next

3.釋放該節點

    public static void del_h(){
        
        current=head.next;  //另CURRENT在前端
        head.next=current.next;
        current=null;
        System.out.println("前端資料已被刪除");
    
    }

刪除末端

我們以刪除7為例:

1.找到資料末端(current.next!=head),記得紀錄前一個節點為prev

2.將prev指向head

3.回收current節點

    public static void del_c(){
        
        current=head.next;
        while(current.next!=head){
            
            prev=current;
            current=current.next;
        
        }
        prev.next=head;
        current=null;
        
    }

刪除指定節點

1.找到要刪除之節點(current!=head) && (current.data != del),並以prev紀錄前一個節點

2.將prev指向current.next

3.回收current節點

(關於示意圖請參考上一篇文章,其原理與此相同)

    public static void del_f(){
        
        System.out.println("請輸入要刪除的資料內容:");
        int del=input.nextInt();
        prev=head;
        current=head.next;
        while ((current!=head) && (current.data != del)){
            
            prev=current;
            current=current.next;
        
        }
        if (current==head){
            System.out.println("資料不存在");
        }
        else{
            prev.next=current.next;
            current=null;
            System.out.printf("%d 已經被刪除!",del);
        }
        
    }

環狀串列之相連

由於此處範例需兩個串列,故將在另外一篇文章中介紹。

完整程式碼

import java.util.Scanner;

class Node1{
    public int data;
    public Node1 next;
    
}

public class CircularLinkList {
    
    static Node1 ptr,head,current,prev,forward;
    static Scanner input = new Scanner(System.in);
    
    CircularLinkList(){
        head=new Node1();
        head.next=head; //當一開始創立串列,就要將自己與自己串聯
    
    }
    
    public static void insert_h(){ //插入至前端
        
        ptr=new Node1();
        System.out.println("請輸入要插入的資料:");
        ptr.data=input.nextInt();
        ptr.next=head.next;
        head.next=ptr;
        System.out.println("您的資料已經加入成功!");
    
    }
    
    public static void insert_c(){  //插入至末端
   
        ptr=new Node1();
        System.out.println("請輸入要插入的資料:");
        ptr.data=input.nextInt();
        current=head.next;
        while(current.next!=head){  //與單向串列不同,不是null而是head
            
            current=current.next;
        
        }
        
        current.next=ptr;
        ptr.next=head;
        System.out.println("您的資料已經加入成功!");
    
    }
    
    public static void insert_f(){  //由大至小插入
        
        ptr=new Node1();
        System.out.println("請輸入要插入的資料:");
        ptr.data=input.nextInt();
        prev=head;
        current=head.next;
        while((current!=head) && (current.data>=ptr.data)){
            
            prev=current;
            current=current.next;
        
        }
        ptr.next=current;
        prev.next=ptr;
        System.out.println("您的資料已經加入成功!");
    
    }
    
    public static void del_h(){
        
        current=head.next;  //另CURRENT在前端
        head.next=current.next;
        current=null;
        System.out.println("前端資料已被刪除");
    
    }
    
    public static void del_c(){
        
        current=head.next;
        while(current.next!=head){
            
            prev=current;
            current=current.next;
        
        }
        prev.next=head;
        current=null;
        
    }
    
    public static void del_f(){
        
        System.out.println("請輸入要刪除的資料內容:");
        int del=input.nextInt();
        prev=head;
        current=head.next;
        while ((current!=head) && (current.data != del)){
            
            prev=current;
            current=current.next;
        
        }
        if (current==head){
            System.out.println("資料不存在");
        }
        else{
            prev.next=current.next;
            current=null;
            System.out.printf("%d 已經被刪除!",del);
        }
        
    }
    
    public static void print(){
        current=head.next;
        while(current!=head){
            System.out.printf("%d ",current.data);
            current=current.next;
        }
        System.out.println();
    }


    public static void main(String[] args) {
        CircularLinkList obj = new CircularLinkList();
        System.out.println("--------------------------\n");
        System.out.println("--環狀串列的基本加入和刪除--\n");
        System.out.println("--------<1>按大小插入-------\n");
        System.out.println("--------<2>插入至前端-------\n");
        System.out.println("--------<3>插入至末端-------\n");
        System.out.println("--------<4>刪 除 前端-------\n");
        System.out.println("--------<5>刪 除 末端-------\n");
        System.out.println("-------<6>刪除指定資料------\n");
        System.out.println("--------<7>列       印-------\n");
        System.out.println("--------<8>結       束-------\n");
        while(true){
            Scanner doing=new Scanner(System.in);
            int doin=doing.nextInt();
            switch(doin){
                case 1://按照大至小
                    obj.insert_f();
                    break;
                case 2:
                    obj.insert_h();
                    break;
                case 3:
                    obj.insert_c();
                    break;
                case 4:
                    obj.del_h();
                    break;
                case 5:
                    obj.del_c();
                    break;
                case 6:
                    obj.del_f();
                    break;
                case 7:
                    obj.print();
                    break;
                case 8:
                    System.exit(0);
                    break;
            
            }
        
        
        }
    }
    
}

總結

環狀串列之最大差異即在於它的末端並不是單向鏈結串列指向的null,而是指向串列之前端head,實際上並沒有什麼差異。

關於作者


長也

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