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

上一頁
下一頁

雙向連結串列基礎

雙向連結串列是連結串列的一種變體，與單向連結串列相比，它可以方便地向前和向後導航。以下是一些理解雙向連結串列概念的重要術語：

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

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

  • Prev − 連結串列的每個連結都包含一個指向前一個連結的連結，稱為 Prev。

  • LinkedList − LinkedList 包含指向第一個連結（稱為 First）和最後一個連結（稱為 Last）的連線連結。

雙向連結串列表示

Doubly Linked List

根據上面所示的圖示，以下是要考慮的重要事項。

  • 雙向連結串列包含一個稱為 first 和 last 的連結元素。

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

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

  • 每個連結都使用其 prev 連結與其前一個連結連結。

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

基本操作

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

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

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

  • 插入到末尾 − 在列表末尾新增一個元素。

  • 刪除末尾 − 刪除列表末尾的元素。

  • 在之後插入 − 在列表的某個元素之後新增一個元素。

  • 刪除 − 使用鍵從列表中刪除元素。

  • 向前顯示 − 以向前的方式顯示完整列表。

  • 向後顯示 − 以向後的方式顯示完整列表。

插入操作

以下程式碼演示了在雙向連結串列開頭進行插入操作。

//insert link at the first location
public void insertFirst(int key, int data){
   //create a link
   Link link = new Link(key,data);

   if(isEmpty()){
      //make it the last link
      last = link;
   }else {
      //update first prev link
      first.prev = link;
   }

   //point it to old first link
   link.next = first;
   //point first to new first link
   first = link;
}

刪除操作

以下程式碼演示了在雙向連結串列開頭進行刪除操作。

//delete link at the first location
public Link deleteFirst(){
   //save reference to first link
   Link tempLink = first;
   //if only one link
   if(first.next == null){
      last = null;
   }else {
      first.next.prev = null;
   }
   first = first.next;
   //return the deleted link
   return tempLink;
}

在末尾插入操作

以下程式碼演示了在雙向連結串列的最後一個位置進行插入操作。

//insert link at the last location
public void insertLast(int key, int data){
   //create a link
   Link link = new Link(key,data);

   if(isEmpty()){
      //make it the last link
      last = link;
   }else {
      //make link a new last link
      last.next = link;     
      //mark old last node as prev of new link
      link.prev = last;
   }

   //point last to new last node
   last = link;
}

演示

Link.java

package com.tutorialspoint.list;

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

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

   public void display(){
      System.out.print("{"+key+","+data+"}");
   }
}

DoublyLinkedList.java

package com.tutorialspoint.list;

public class DoublyLinkedList {
   
   //this link always point to first Link 
   private Link first;
   //this link always point to last Link 
   private Link last;

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

   //is list empty
   public boolean isEmpty(){
      return first == null;
   }

   //insert link at the first location
   public void insertFirst(int key, int data){
      //create a link
      Link link = new Link(key,data);

      if(isEmpty()){
         //make it the last link
         last = link;
      }else {
         //update first prev link
         first.prev = link;
      }

      //point it to old first link
      link.next = first;
      //point first to new first link
      first = link;
   }

   //insert link at the last location
   public void insertLast(int key, int data){
      //create a link
      Link link = new Link(key,data);

      if(isEmpty()){
         //make it the last link
         last = link;
      }else {
         //make link a new last link
         last.next = link;     
         //mark old last node as prev of new link
         link.prev = last;
      }

      //point last to new last node
      last = link;
   }

   //delete link at the first location
   public Link deleteFirst(){
      //save reference to first link
      Link tempLink = first;
      //if only one link
      if(first.next == null){
         last = null;
      }else {
         first.next.prev = null;
      }
      first = first.next;
      //return the deleted link
      return tempLink;
   }

   //delete link at the last location
   public Link deleteLast(){
      //save reference to last link
      Link tempLink = last;
      //if only one link
      if(first.next == null){
         first = null;
      }else {
         last.prev.next = null;
      }
      last = last.prev;
      //return the deleted link
      return tempLink;
   }

   //display the list in from first to last
   public void displayForward(){
      //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(" ]");
   }

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

   //delete a link with given key
   public Link delete(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{           
            //move to next link
            current = current.next;             
         }
      }

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

         if(current == last){
            //change last to point to prev link
            last = current.prev;
         }else {
            current.next.prev = current.prev;
         }
         return current;
      }

   public boolean insertAfter(int key, int newKey, int data){
      //start from the first link
      Link current = first;      
      //if list is empty
      if(first == null){
         return false;
      }

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

      Link newLink = new Link(newKey,data); 
      if(current==last) {
         newLink.next = null; 
         last = newLink; 
      }
      else {
         newLink.next = current.next;         
         current.next.prev = newLink;
      }
      newLink.prev = current; 
      current.next = newLink; 
      return true; 
   }
}

DoublyLinkedListDemo.java

package com.tutorialspoint.list;

public class DoublyLinkedListDemo {
    public static void main(String args[]){
        DoublyLinkedList list = new DoublyLinkedList();
        
        list.insertFirst(1, 10);
        list.insertFirst(2, 20);
        list.insertFirst(3, 30);
        
        list.insertLast(4, 1);
        list.insertLast(5, 40);
        list.insertLast(6, 56);
       
        System.out.print("\nList (First to Last): ");  
        list.displayForward();
        System.out.println("");
        System.out.print("\nList (Last to first): "); 
        list.displayBackward();
        
        System.out.print("\nList , after deleting first record: ");
        list.deleteFirst();        
        list.displayForward();
        
        System.out.print("\nList , after deleting last record: ");  
        list.deleteLast();
        list.displayForward();
        
        System.out.print("\nList , insert after key(4) : ");  
        list.insertAfter(4,7, 13);
        list.displayForward();
        
        System.out.print("\nList  , after delete key(4) : ");  
        list.delete(4);
        list.displayForward();
        
    }
}

如果我們編譯並執行上述程式，它將產生以下結果：

List (First to Last): [ {3,30} {2,20} {1,10} {4,1} {5,40} {6,56}  ]

List (Last to first): [ {6,56} {5,40} {4,1} {1,10} {2,20} {3,30}  ]
List (First to Last) after deleting first record: [ {2,20} {1,10} {4,1} {5,40} {6,56}  ]
List  (First to Last) after deleting last record: [ {2,20} {1,10} {4,1} {5,40}  ]
List  (First to Last) insert after key(4) : [ {2,20} {1,10} {4,1} {7,13} {5,40}  ]
List  (First to Last) after delete key(4) : [ {2,20} {1,10} {7,13} {5,40}  ]
列印頁面
上一頁
下一頁
廣告

© . All rights reserved.