Dsa Using Java 简明教程

DSA using Java - Doubly Linked List

Doubly Linked List Basics

双向链表是链表的一种变体，与单向链表相比，它可以在两个方向（向前或向后）轻松地导航。以下是理解双向链表概念的重要术语

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways either forward and backward easily as compared to Single Linked List. Following are important terms to understand the concepts of doubly Linked List

Link − Each Link of a linked list can store a data called an element.
Next − Each Link of a linked list contain a link to next link called Next.
Prev − Each Link of a linked list contain a link to previous link called Prev.
LinkedList − A LinkedList contains the connection link to the first Link called First and to the last link called Last.

Doubly Linked List Representation

根据以上所示的说明，以下是要考虑的重要要点。

As per above shown illustration, following are the important points to be considered.

Doubly LinkedList contains an link element called first and last.
Each Link carries a data field(s) and a Link Field called next.
Each Link is linked with its next link using its next link.
Each Link is linked with its previous link using its prev link.
Last Link carries a Link as null to mark the end of the list.

Basic Operations

以下是由链表支持的基本操作。

Following are the basic operations supported by an list.

Insertion − add an element at the beginning of the list.
Deletion − delete an element at the beginning of the list.
Insert Last − add an element in the end of the list.
Delete Last − delete an element from the end of the list.
Insert After − add an element after an item of the list.
Delete − delete an element from the list using key.
Display forward − displaying complete list in forward manner.

Display backward − displaying complete list in backward manner.

Insertion Operation

以下代码演示在双向链表的开头执行插入操作。

Following code demonstrate insertion operation at beginning in a doubly linked list.

//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;
}

Deletion Operation

以下代码演示在双向链表的开头执行删除操作。

Following code demonstrate deletion operation at beginning in a doubly linked list.

//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;
}

Insertion at End Operation

以下代码演示在双向链表的末尾执行插入操作。

Following code demonstrate insertion operation at last position in a doubly linked list.

//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;
}

Demo

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();

    }
}

如果我们编译并运行上述程序，它将生成以下结果 -

If we compile and run the above program then it would produce following result −

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}  ]