使用 Java 的 DSA - 双向链表

双向链表基础知识

双向链表是链表的一种变体，与单链表相比，双向链表可以轻松地向前和向后导航。以下是理解双向链表概念的重要术语

链接 − 链表的每个链接都可以存储称为元素的数据。
下一个 − 链表的每个链接都包含一个指向下一个链接的链接，称为下一个。
上一个 − 链表的每个链接都包含一个指向上一个链接的链接，称为上一个。
链接列表 − LinkedList 包含指向第一个 Link(称为 First)和最后一个 Link(称为 Last)的连接链接。

双向链接列表表示

如上图所示，以下是需要考虑的重要点。

双向链接列表包含一个称为 first 和 last 的链接元素。
每个 Link 都带有一个数据字段和一个称为 next 的链接字段。
每个 Link 都使用其下一个链接与其下一个链接链接。
每个 Link 都使用其上一个链接与其上一个链接链接。
最后一个 Link 带有一个为 null 的 Link 来标记结束列表。

基本操作

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

插入 − 在列表开头添加一个元素。
删除 − 删除列表开头的一个元素。
插入最后一个 − 在列表末尾添加一个元素。
删除最后一个 − 从列表末尾删除一个元素。
在后面插入 − 在列表的某项后面添加一个元素。
删除 −使用键从列表中删除一个元素。
向前显示 − 以向前方式显示完整列表。
向后显示 − 以向后方式显示完整列表。

插入操作

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

//在第一个位置插入链接
public void insertFirst(int key, int data){
   //创建链接
   Link link = new Link(key,data);

    if(isEmpty()){
        //使其成为最后一个链接
        last = link;
    }else {
        //更新第一个上一个链接
        first.prev = link;
    }
    
    //将其指向旧的第一个链接
    link.next = first;
    //将 first 指向新的第一个链接
    first = link;
}

删除操作

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

//删除第一个位置的链接
public Link deleteFirst(){
   //保存对第一个链接的引用
   Link tempLink = first;
   //如果只有一个链接
   if(first.next == null){
      last = null;
   }else {
      first.next.prev = null;
   }
   first = first.next;
   //返回删除的链接
   return tempLink;
}

在末尾插入操作

以下代码演示了在双向链表的最后一个位置插入操作。

//在最后一个位置插入链接
public void insertLast(int key, int data){
   //创建链接
   Link link = new Link(key,data);

    if(isEmpty()){
        //使其成为最后一个链接
        last = link;
    }else {
        //使链接成为新的最后一个链接
        last.next = link;
        //将旧的最后一个节点标记为新链接的前一个
        link.prev = last;
    }
    
    //将最后一个指向新的最后一个节点
    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 {
   
    //此链接始终指向第一个链接
    private Link first;
    //此链接始终指向最后一个链接
    private Link last;
    
    // 创建一个空的链接列表
   public DoublyLinkedList(){
      first = null;
      last = null;
   }

   //列表是否为空
   public boolean isEmpty(){
      return first == null;
   }

   //在第一个位置插入链接
   public void insertFirst(int key, int data){
      	//创建链接
        Link link = new Link(key,data);
        
        if(isEmpty()){
            //使其成为最后一个链接
            last = link;
        }else {
            //更新第一个上一个链接
            first.prev = link;
        }
        
        //将其指向旧的第一个链接
        link.next = first;
        //将 first 指向新的第一个链接
        first = link;
   }

   //在最后位置插入链接
   public void insertLast(int key, int data){
        //创建链接
        Link link = new Link(key,data);

        if(isEmpty()){
            //使其成为最后一个链接
            last = link;
        }else {
            //使链接成为新的最后一个链接
            last.next = link;
            //将旧的最后一个节点标记为新链接的前一个
            link.prev = last;
        }
        
        //将最后一个指向新的最后一个节点
        last = link;
   }

   //删除第一个位置的链接
   public Link deleteFirst(){
      //保存对第一个链接的引用
      Link tempLink = first;
      //如果只有一个链接
      if(first.next == null){
         last = null;
      }else {
         first.next.prev = null;
      }
      first = first.next;
      //返回删除的链接
      return tempLink;
   }

   //删除最后一个位置的链接
   public Link deleteLast(){
      //保存对最后一个链接的引用
      Link tempLink = last;
      //如果只有一个链接
      if(first.next == null){
         first = null;
      }else {
         last.prev.next = null;
      }
      last = last.prev;
      //返回删除的链接
      return tempLink;
   }

   //从第一个到最后一个显示列表
   public void displayForward(){
      //从头开始
      Link current = first;
      //导航到列表末尾
      System.out.print("[ ");
      while(current != null){
         //打印数据
         current.display();
         //移动到下一个项目
         current = current.next;
         System.out.print(" ");
      }      
      System.out.print(" ]");
   }

    //从最后一个到第一个显示列表
    public void displayBackward(){
        //从最后一个开始
        Link current = last;
        //导航到列表开头
        System.out.print("[ ");
        while(current != null){
         //打印数据
         current.display();
         //移动到下一个项目
         current = current.prev;
         System.out.print(" ");
      }
      System.out.print(" ]");
   }

   //删除指定键的链接
   public Link delete(int key){
      //从第一个链接开始
      Link current = first;      
      //如果列表为空
      if(first == null){
         return null;
      }

      //浏览列表
      while(current.key != key){
      //如果它是最后一个节点
      if(current.next == null){
            return null;
         }else{           
            //移动到下一个链接
            current = current.next;             
         }
      }

      //找到匹配项，更新链接
      if(current == first) {
         //将 first 改为指向 next 链接
            first = current.next;
         }else {
            //绕过当前链接
            current.prev.next = current.next;
         }    

         if(current == last){
            //将最后一个链接改为指向上一个链接
            last = current.prev;
         }else {
            current.next.prev = current.prev;
         }
         return current;
      }

   public boolean insertAfter(int key, int newKey, int data){
      //从第一个链接开始
      Link current = first;      
      //如果列表为空
      if(first == null){
         return false;
      }

      //浏览列表
      while(current.key != key){
         //如果它是最后一个节点
         if(current.next == null){
            return false;
         }else{           
            //移动到下一个链接
            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("
List (First to Last): ");  
        list.displayForward();
        System.out.println("");
        System.out.print("
List (Last to first): "); 
        list.displayBackward();
        
        System.out.print("
List , after deleting first record: ");
        list.deleteFirst();        
        list.displayForward();
        
        System.out.print("
List , after deleting last record: ");  
        list.deleteLast();
        list.displayForward();
        
        System.out.print("
List , insert after key(4) : ");  
        list.insertAfter(4,7, 13);
        list.displayForward();
        
        System.out.print("
List  , 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}  ]

使用 Java 的 DSA 教程

有用资源

使用 Java 的 DSA - 双向链表

双向链表基础知识

双向链接列表表示

基本操作

插入操作

删除操作

在末尾插入操作

演示

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！