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

鏈結串列—單向鏈結串列之介紹與範例

2018-02-12 17:38:55   資料結構

鏈結串列

鏈結串列是利用指標將資料連結起來的資料結構,需要利用額外的指標空間將資料串起來。

節點:有儲存的資料與指標兩個空間

串列:負責串接各節點

(各節點示意圖,分為儲存資料與指標)

與陣列的差異

串列基本上與陣列相似,明顯差異如下:

(1).陣列屬於連續記憶體空間,串列則是非連續的

(2).陣列不用指標空間,而串列則需要指標空間。

(3).陣列需要事先宣告空間,串列則否。

(4).陣列內的元素資料型態需相同,串列之節點則否。

串列之種類

串列常見的種類:單向鏈結串列、雙向鏈結串列、環狀鏈結串列,則本文要介紹的是單向鏈結串列。

單向鏈結串列

顧名思義,單向鏈結串列每個節點只有一個指標也只指向一個方向。如圖所示:

操作(以Java實作)

由於Java無法直接操作指標,故需以物件之方式,才能利用指標。

類別與實體變數之宣告

class Node { /*節點*/
    public int data;  /*節點中的資料*/
    public Node next; /*下一個節點*/
}

節點宣告為Node類別,分為data與next。分別儲存資料與下一個指標。

另外宣告一個類別為singleList,為整個List之結構,並宣告以下變數:

static Node ptr, head, current, prev, forward;
static Scanner key = new Scanner(System.in);

singleList類別之建構子:

    singleList() { /*建立LIST,head*/
        head = new Node();
        head.next = null;
    }

主要負責建立新的head。

加入節點(前端)

若要將"6"加入串列之前端,步驟如下:

1.宣告新結點    ( ptr=new Node(); )

2.將該節點指向head.next    ( ptr.next = head.next  ,此時的head.next變為ptr.next)

3.再將原本的head指向該節點( head.next = ptr )

    public static void insert_h(){
        ptr=new Node();
        ptr.next=head.next;
        System.out.print("請輸入要新增的資料:");
        ptr.data=key.nextInt();
        head.next=ptr;
   
    }

加入資料(末端)

加入末端其實與前端差不多,但是需要追蹤串列的末端。假設我們要加入資料"6":

1.宣告新的節點

2.將該新節點指向null (由於串列末端指向null代表結束)

3.利用迴圈找到末端,直到current.next ==null,代表已到末端

4.將該末端指向該節點

    public static void insert_c(){
        
        ptr=new Node();
        ptr.next=null;
        System.out.print("請輸入要新增的資料:");
        ptr.data=key.nextInt();
        current=head;/*CURRENT從頭開始找*/
        while (current.next!=null){
            current=current.next;
        }
        current.next=ptr;
    
    }

加入資料(按照順序由大至小)

按照大小加入需利用兩個變數:prev為前面的節點,current為要插入的節點,假設我們要加入資料"6":

1.宣告新節點

2.將該節點指向null (還不知道要指向哪裡)

3.尋找要插入的點

4.將該節點指向current

5.將上一個節點(prev)指向該節點

    public static void insert_f(){ /*依照數字大小排列*/
    
        ptr=new Node();/*建立新的節點*/
        ptr.next=null;
        System.out.print("請輸入要插入的資料:");
        ptr.data=key.nextInt();
        /*利用像是夾擊的方法,prev為前一個節點,current為當前的節點*/
        prev=head;
        current=head.next;
        /*current!=null時代表還尚未抵達串列末端,但不是current.next!=null否則會使current停留在最後一筆資料,而導致ptr原本應該插入末端,但卻插入末端的前一個*/
        /*將要插入之資料與current比對,當要插入之PTR已經大於CURRENT代表已到達應插入位置*/
        while ((current!=null) && (current.data>=ptr.data)){
            prev=current;
            current=current.next;
        
        }
        ptr.next=current; /*將PTR串聯至CURRENT*/
        prev.next=ptr;
    
    }

刪除指定節點之資料

刪除需利用兩個變數:prev (該節點的前一個節點)、current(該節點)。假設我們要刪除資料"6":

1.先找到要刪除的節點

2.將該節點的前一個節點指向curretn.next 

3.回收該節點

    public static void del(){
        if(head.next==null){
            System.out.println("串列為空");
        }
        else{
            System.out.print("請輸入要刪除的資料節點之內容:");
            int del_node=key.nextInt();
            prev=head; 
            current=head.next; 
            while((current!=null)&&(del_node!=current.data)){
                prev=current;
                current=current.next;
            }
            if(current!=null){
                
                prev.next=current.next; /*將prev連結到要刪除的資料之後的節點*/
                current=null; /*回收節點*/
                System.out.printf("del Data: %d\n",del_node);
            
            }
            else{
                
                System.out.println("Not Find Data.");
                
            }            
        }
    }

串列之反轉

反轉需要用到三個變數:prev(前)、current(中)、forward(後)

1.每次轉換時,將prev向後移動到current

2.將current向後移動到forward

3.將forward移動到下一個

4.將current向前指向prev

5.重複上述動作之後,最後將head移到另一邊

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

完整程式碼

class Node { //節點

    public int data;  //節點中的資料
    public Node next; //紀錄下一個節點

}

class singleList { //整個LIST的結構

    static Node ptr, head, current, prev, forward;
    static Scanner key = new Scanner(System.in);

    singleList() { //建立LIST,head

        head = new Node();
        head.next = null;
    }
    
    public static void insert_f(){ /*依照數字大小排列*/
    
        ptr=new Node();/*建立新的節點*/
        ptr.next=null;
        System.out.print("請輸入要插入的資料:");
        ptr.data=key.nextInt();
        /*利用像是夾擊的方法,prev為前一個節點,current為當前的節點*/
        prev=head;
        current=head.next;
        /*current!=null時代表還尚未抵達串列末端,但不是current.next!=null否則會使current停留在最後一筆資料,而導致ptr原本應該插入末端,但卻插入末端的前一個*/
        /*將要插入之資料與current比對,當要插入之PTR已經大於CURRENT代表已到達應插入位置*/
        while ((current!=null) && (current.data>=ptr.data)){
            prev=current;
            current=current.next;
        
        }
        ptr.next=current; /*將PTR串聯至CURRENT*/
        prev.next=ptr;
    
    }
    
    public static void insert_h(){
        ptr=new Node();
        ptr.next=head.next;//插入前端,目前ptr與head都指向同一個節點
        System.out.print("請輸入要新增的資料:");
        ptr.data=key.nextInt();
        head.next=ptr;
   
    }
    
    public static void insert_c(){
        
        ptr=new Node();
        ptr.next=null;
        System.out.print("請輸入要新增的資料:");
        ptr.data=key.nextInt();
        current=head;/*CURRENT從頭開始找*/
        while (current.next!=null){
            current=current.next;
        }
        current.next=ptr;
    
    }
    
    public static void reverse(){
        
        current=null;
        forward=head.next;
        while(forward!=null){
            
            prev=current;
            current=forward;
            forward=forward.next;
            current.next=prev;
           
        }
        head.next=current;
    }
    
    public static void del(){
        if(head.next==null){
            System.out.println("串列為空");
        }
        else{
            System.out.print("請輸入要刪除的資料節點之內容:");
            int del_node=key.nextInt();
            prev=head; 
            current=head.next; 
            while((current!=null)&&(del_node!=current.data)){
                prev=current;
                current=current.next;
            }
            if(current!=null){
                
                prev.next=current.next; /*將prev連結到要刪除的資料之後的節點*/
                current=null; /*回收節點*/
                System.out.printf("del Data: %d\n",del_node);
            
            }
            else{
                
                System.out.println("Not Find Data.");
                
            }            
        }

    }
    public static void print(){
        current=head.next;
        while(current!=null){
            System.out.println(current.data);
            current=current.next;
        }
        
        }
    
    
    public static void main(String[] args) {
        singleList obj = new singleList();
        while(true){
            Scanner doing=new Scanner(System.in);
            int doin=doing.nextInt();
            switch(doin){
                case 1://按照大至小
                    obj.insert_f();
                    break;
                case 2:
                    obj.del();
                    break;
                case 3:
                    obj.print();
                    break;
                case 4:
                    obj.insert_h(); //加入前端
                    break;
                case 5: //加入後端
                    obj.insert_c();
                    break;
                case 6:
                    obj.reverse();
                    break;
                case 7:
                    System.exit(0);
                    break;
            
            }
        
        
        }
    }      
}
 

關於作者


長也

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