使用 Java 的 DSA - 循环链接列表

循环链接列表基础知识

循环链接列表是链接列表的一种变体，其中第一个元素指向最后一个元素，最后一个元素指向第一个元素。单链表和双链表都可以制成循环链表

单链表作为循环

双链表作为循环

根据上图，以下是需要考虑的重要点。

• 无论是单链表还是双链表，Last Link'next 都指向列表的第一个链接列表。

• 如果是双向链表，第一个链接的 prev 指向列表的最后一个。

基本操作

以下是循环列表支持的重要操作。

• 插入 − 在列表开头插入一个元素。

• 删除 − 从列表开头插入一个元素。

• 显示 −显示列表。

长度操作

以下代码演示了基于单链表的循环链表中的插入操作。

//在第一个位置插入链接
public void insertFirst(int key, int data){
    //创建链接
   Link link = new Link(key,data);
   if (isEmpty()) {
      first  = link;
      first.next = first;
   }      
   else{
      //将其指向旧的第一个节点
      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 display(){  
    //从头开始
    Link current = first;
    //导航到列表末尾
    System.out.print("[ ");
    if(first != null){
        while(current.next != current){
            //打印数据
            current.display();
            //移动到下一个项目
            current = current.next;
            System.out.print(" ");
        }
    }
    System.out.print(" ]");
}

演示

Link.java

package com.tutorialspoint.list;
   
public class CircularLinkedList {
    //此链接始终指向第一个链接
    private Link first;
    
    // 创建一个空的链接列表
   public CircularLinkedList(){
      first = null;       
   }

   public boolean isEmpty(){
      return first == null;
   }

   public int length(){
      int length = 0;

      //如果列表为空
      if(first == null){
         return 0;
      }

      Link current = first.next;

      while(current != first){
         length++;
         current = current.next;   
      }
      return length;
   }

   //在第一个位置插入链接
   public void insertFirst(int key, int data){
   //创建链接
   Link link = new Link(key,data);
      if (isEmpty()) {
         first  = link;
         first.next = first;
      }      
      else{
         //将其指向旧的第一个节点
         link.next = first;
         //将 first 指向新的第一个节点
         first = link;
      }      
   }

   //delete first item
   public Link deleteFirst(){
      //保存对第一个链接的引用
      Link tempLink = first;
      if(first.next == first){  
         first = null;
         return tempLink;
      }     

      //将第一个链接旁边的标记为第一个
      first = first.next;
      //返回删除的链接
      return tempLink;
   }

   public void display(){

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

DoublyLinkedListDemo.java

package com.tutorialspoint.list;

public class CircularLinkedListDemo {
   public static void main(String args[]){
      CircularLinkedList list = new CircularLinkedList();

      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("原始列表: ");  
      list.display();
      System.out.println("");  
      while(!list.isEmpty()){            
         Link temp = list.deleteFirst();
         System.out.print("删除的值:");  
         temp.display();
         System.out.println("");
      }         
      System.out.print("删除所有项目后的列表: ");          
      list.display();
      System.out.println("");
   }
}

如果我们编译并运行上述程序，则会产生以下结果 −

原始列表: [ {6,56} {5,40} {4,1} {3,30} {2,20}  ]
删除的值:{6,56}
删除的值:{5,40}
删除的值:{4,1}
删除的值:{3,30}
删除的值:{2,20}
删除的值:{1,10}
删除所有项目后的列表: [  ]