Java 資料結構與演算法 - 連結串列

上一頁
下一頁

連結串列基礎

連結串列是由一系列連結組成的序列，每個連結包含一個指向另一個連結的連線。連結串列是僅次於陣列的第二常用資料結構。以下是理解連結串列概念的重要術語。

  • 連結 − 連結串列的每個連結都可以儲存稱為元素的資料。

  • 下一個 − 連結串列的每個連結都包含一個指向下一個連結的連結，稱為“下一個”。

  • 連結串列 − 連結串列包含一個指向第一個連結的連線，稱為“第一個”。

連結串列表示

Linked List

根據上面所示的圖示，以下是需要考慮的重要幾點。

  • 連結串列包含一個稱為“第一個”的連結元素。

  • 每個連結都包含一個或多個數據欄位和一個稱為“下一個”的連結欄位。

  • 每個連結都使用其“下一個”連結與其下一個連結連結。

  • 最後一個連結的連結為 null，以標記列表的結尾。

連結串列的型別

以下是連結串列的各種型別。

  • 簡單鏈表 − 項導航只能向前。

  • 雙向連結串列 − 可以向前和向後導航項。

  • 迴圈連結串列 − 最後一項包含下一項的第一個元素的連結，第一個元素包含前一項的最後一個元素的連結。

基本操作

以下是列表支援的基本操作。

  • 插入 − 在列表開頭新增一個元素。

  • 刪除 − 刪除列表開頭的元素。

  • 顯示 − 顯示完整列表。

  • 搜尋 − 使用給定的鍵搜尋元素。

  • 刪除 − 使用給定的鍵刪除元素。

插入操作

插入是一個三步過程

  1. 使用提供的資料建立一個新的連結。

  2. 將新連結指向舊的第一個連結。

  3. 將第一個連結指向此新連結。

Linked List Insert First 
//insert link at the first location
public void insertFirst(int key, int data){
   //create a link
   Link link = new Link(key,data);
   //point it to old first node
   link.next = first;
   //point first to new first node
   first = link;
}

刪除操作

刪除是一個兩步過程

  1. 獲取第一個連結指向的連結作為臨時連結。

  2. 將第一個連結指向臨時連結的下一個連結。

Linked List Delete First 
//delete first item
public Link deleteFirst(){
   //save reference to first link
   Link tempLink = first;
   //mark next to first link as first 
   first = first.next;
   //return the deleted link
   return tempLink;
}

導航操作

導航是一個遞迴步驟過程，是許多操作（如搜尋、刪除等）的基礎。

  1. 獲取第一個連結指向的連結作為當前連結。

  2. 檢查當前連結是否不為 null 並顯示它。

  3. 將當前連結指向當前連結的下一個連結，並移動到上述步驟。

Linked List Navigation

注意 

//display the list
public void display(){
   //start from the beginning
   Link current = first;
   //navigate till the end of the list
   System.out.print("[ ");
   while(current != null){
      //print data
      current.display();
      //move to next item
      current = current.next;
      System.out.print(" ");
   }
   System.out.print(" ]");
}

高階操作

以下是為列表指定的高階操作。

  • 排序 − 基於特定順序對列表進行排序。

  • 反轉 − 反轉連結串列。

  • 連線 − 連線兩個列表。

排序操作

我們使用氣泡排序來對列表進行排序。

public void sort(){

   int i, j, k, tempKey, tempData ;
   Link current,next;
   int size = length();
   k = size ;
   for ( i = 0 ; i < size - 1 ; i++, k-- ) {
      current = first ;
      next = first.next ;
      for ( j = 1 ; j < k ; j++ ) {            
         if ( current.data > next.data ) {
            tempData = current.data ;
            current.data = next.data;
            next.data = tempData ;

            tempKey = current.key;
            current.key = next.key;
            next.key = tempKey;
         }
         current = current.next;
         next = next.next;                        
      }
   }
}

反轉操作

以下程式碼演示了反轉單鏈表。

public LinkedList reverse() { 
   LinkedList reversedlist = new LinkedList();
   Link nextLink = null;     
   reversedlist.insertFirst(first.key, first.data);

   Link currentLink = first;       
   // Until no more data in list, 
   // insert current link before first and move ahead.
   while(currentLink.next != null){
      nextLink = currentLink.next;           
      // Insert at start of new list.
      reversedlist.insertFirst(nextLink.key, nextLink.data); 
      //advance to next node
      currentLink = currentLink.next;            
   }      
   return reversedlist;
}

連線操作

以下程式碼演示了反轉單鏈表。

public void concatenate(LinkedList list){
   if(first == null){
      first = list.first;
   }
   if(list.first == null){
      return;
   }
   Link temp = first;
   while(temp.next !=null) {
      temp = temp.next;
   }
   temp.next = list.first;       
}

演示

Link.java 
package com.tutorialspoint.list;

public class Link {
   public int key;
   public int data;
   public Link next;

   public Link(int key, int data){
      this.key = key;
      this.data = data;
   }

   public void display(){
      System.out.print("{"+key+","+data+"}");
   }
}
LinkedList.java 
package com.tutorialspoint.list;

public class LinkedList {
   //this link always point to first Link 
   //in the Linked List 
   private Link first;

   // create an empty linked list 
   public LinkedList(){
      first = null;
   }

   //insert link at the first location
   public void insertFirst(int key, int data){
      //create a link
      Link link = new Link(key,data);
      //point it to old first node
      link.next = first;
      //point first to new first node
      first = link;
   }

   //delete first item
   public Link deleteFirst(){
      //save reference to first link
      Link tempLink = first;
      //mark next to first link as first 
      first = first.next;
      //return the deleted link
      return tempLink;
   }

   //display the list
   public void display(){
      //start from the beginning
      Link current = first;
      //navigate till the end of the list
      System.out.print("[ ");
      while(current != null){
         //print data
         current.display();
         //move to next item
         current = current.next;
         System.out.print(" ");
      }
      System.out.print(" ]");
   }

   //find a link with given key
   public Link find(int key){
      //start from the first link
      Link current = first;

      //if list is empty
      if(first == null){
         return null;
      }
      //navigate through list
      while(current.key != key){
         //if it is last node
         if(current.next == null){
            return null;
         }else{
            //go to next link
            current = current.next;
         }
      }      
      //if data found, return the current Link
      return current;
   }

   //delete a link with given key
   public Link delete(int key){
      //start from the first link
      Link current = first;
      Link previous = null;
      //if list is empty
      if(first == null){
         return null;
      }

      //navigate through list
      while(current.key != key){
         //if it is last node
         if(current.next == null){
            return null;
         }else{
            //store reference to current link
            previous = current;
            //move to next link
            current = current.next;             
         }
      }

      //found a match, update the link
      if(current == first) {
         //change first to point to next link
         first = first.next;
      }else {
         //bypass the current link
         previous.next = current.next;
      }    
      return current;
   }


   //is list empty
   public boolean isEmpty(){
      return first == null;
   }
   
   public int length(){
      int length = 0;
      for(Link current = first; current!=null;
         current = current.next){
         length++;
      }
      return length;
   }
   
   public void sort(){
      int i, j, k, tempKey, tempData ;
      Link current,next;
      int size = length();
      k = size ;
      for ( i = 0 ; i < size - 1 ; i++, k-- ) {
         current = first ;
         next = first.next ;
         for ( j = 1 ; j < k ; j++ ) {            
            if ( current.data > next.data ) {
               tempData = current.data ;
               current.data = next.data;
               next.data = tempData ;
	 
	           tempKey = current.key;
	           current.key = next.key;
	           next.key = tempKey;
            }
            current = current.next;
           next = next.next;                        
         }
      }
   }

   public LinkedList reverse() { 
      LinkedList reversedlist = new LinkedList();
      Link nextLink = null;     
      reversedlist.insertFirst(first.key, first.data);

      Link currentLink = first;       
      // Until no more data in list, 
      // insert current link before first and move ahead.
      while(currentLink.next != null){
         nextLink = currentLink.next;           
         // Insert at start of new list.
         reversedlist.insertFirst(nextLink.key, nextLink.data); 
         //advance to next node
         currentLink = currentLink.next;            
      }      
      return reversedlist;
   }

   public void concatenate(LinkedList list){
      if(first == null){
         first = list.first;
      }
      if(list.first == null){
         return;
      }
      Link temp = first;

      while(temp.next !=null) {
         temp = temp.next;
      }
      temp.next = list.first;       
   }
}
LinkedListDemo.java 
package com.tutorialspoint.list;

public class LinkedListDemo {
   public static void main(String args[]){
      LinkedList list = new LinkedList();
        
      list.insertFirst(1, 10);
      list.insertFirst(2, 20);
      list.insertFirst(3, 30);
      list.insertFirst(4, 1);
      list.insertFirst(5, 40);
      list.insertFirst(6, 56);

      System.out.print("\nOriginal List: ");  
      list.display();
      System.out.println("");
      while(!list.isEmpty()){            
         Link temp = list.deleteFirst();
         System.out.print("Deleted value:");  
         temp.display();
         System.out.println("");
      }         
      System.out.print("List after deleting all items: ");          
      list.display();
      System.out.println("");
      list.insertFirst(1, 10);
      list.insertFirst(2, 20);
      list.insertFirst(3, 30);
      list.insertFirst(4, 1);
      list.insertFirst(5, 40);
      list.insertFirst(6, 56);

      System.out.print("Restored List: ");  
      list.display();
      System.out.println("");  

      Link foundLink = list.find(4);
      if(foundLink != null){
        System.out.print("Element found: ");  
         foundLink.display();
         System.out.println("");  
      }else{
         System.out.println("Element not found.");  
      }

      list.delete(4);
      System.out.print("List after deleting an item: ");  
      list.display();
      System.out.println(""); 
      foundLink = list.find(4);
      if(foundLink != null){
         System.out.print("Element found: ");  
         foundLink.display();
         System.out.println("");  
      }else{
         System.out.print("Element not found. {4,1}");  
      }
      System.out.println(""); 
      list.sort();
      System.out.print("List after sorting the data: ");  
      list.display();
      System.out.println(""); 
      System.out.print("Reverse of the list: ");  
      LinkedList list1 = list.reverse();
      list1.display();
      System.out.println(""); 
      
      LinkedList list2 = new LinkedList();

      list2.insertFirst(9, 50);
      list2.insertFirst(8, 40);
      list2.insertFirst(7, 20);

      list.concatenate(list2);
      System.out.print("List after concatenation: ");  
      list.display();
      System.out.println(""); 
   }
}

如果我們編譯並執行上述程式，則會產生以下結果

Original List: [ {6,56} {5,40} {4,1} {3,30} {2,20} {1,10}  ]
Deleted value:{6,56}
Deleted value:{5,40}
Deleted value:{4,1}
Deleted value:{3,30}
Deleted value:{2,20}
Deleted value:{1,10}
List after deleting all items: [  ]
Restored List: [ {6,56} {5,40} {4,1} {3,30} {2,20} {1,10}  ]
Element found: {4,1}
List after deleting an item: [ {6,56} {5,40} {3,30} {2,20} {1,10}  ]
Element not found. {4,1}
List after sorting the data: [ {1,10} {2,20} {3,30} {5,40} {6,56}  ]
Reverse of the list: [ {6,56} {5,40} {3,30} {2,20} {1,10}  ]
List after concatenation: [ {1,10} {2,20} {3,30} {5,40} {6,56} {7,20} {8,40} {9,50}  ]
列印頁面
上一頁
下一頁
廣告