Java实现的数据结构与算法 - 环形链表

环形链表基础

环形链表是链表的一种变体，其中第一个元素指向最后一个元素，最后一个元素指向第一个元素。单链表和双向链表都可以转换为环形链表。

单链表作为环形链表

双向链表作为环形链表

根据以上所示图例，需要考虑以下重要事项。

• 在单链表和双向链表两种情况下，最后一个链接的“next”都指向列表的第一个链接。

• 在双向链表中，第一个链接的“prev”指向列表的最后一个链接。

基本操作

以下是环形链表支持的重要操作。

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

• 删除 − 从列表开头删除元素。

• 显示 − 显示列表。

长度操作

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

//insert link at the first location
public void insertFirst(int key, int data){
   //create a link
   Link link = new Link(key,data);
   if (isEmpty()) {
      first  = link;
      first.next = first;
   }      
   else{
      //point it to old first node
      link.next = first;
      //point first to new first node
      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;
}

显示列表操作

以下代码演示了环形链表中的显示列表操作。

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

演示

Link.java

package com.tutorialspoint.list;
   
public class CircularLinkedList {
   //this link always point to first Link 
   private Link first;

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

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

   public int length(){
      int length = 0;

      //if list is empty
      if(first == null){
         return 0;
      }

      Link current = first.next;

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

   //insert link at the first location
   public void insertFirst(int key, int data){
   //create a link
   Link link = new Link(key,data);
      if (isEmpty()) {
         first  = link;
         first.next = first;
      }      
      else{
         //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;
      if(first.next == first){  
         first = null;
         return tempLink;
      }     

      //mark next to first link as first 
      first = first.next;
      //return the deleted link
      return tempLink;
   }

   public void display(){

      //start from the beginning
      Link current = first;
      //navigate till the end of the list
      System.out.print("[ ");
      if(first != null){
         while(current.next != current){
            //print data
            current.display();
            //move to next item
            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("\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("");
   }
}

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

Original List: [ {6,56} {5,40} {4,1} {3,30} {2,20}  ]
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: [  ]