Java 数据结构 - 环形链表

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

单链表作为环形链表

在单链表中，最后一个节点的 next 指针指向第一个节点。

双向链表作为环形链表

在双向链表中，最后一个节点的 next 指针指向第一个节点，第一个节点的 previous 指针指向最后一个节点，从而形成双向环形链表。

根据以上说明，以下是一些需要考虑的重要事项。

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

对于双向链表，第一个链接的 previous 指针指向列表的最后一个链接。

示例

class Node{	
   int data;
   Node preNode, nextNode, CurrentNode;
   Node() {
      preNode = null;
      nextNode = null; 
   }	   
   Node(int data) {
      this.data = data;
   }		
}
public class CircularLinked {
   Node head, tail;
   int size;
	   
   public void printData() {
      Node node = head;
      if(size<=0) {
         System.out.print("List is empty");
      } else {
         do {
            System.out.print(" " + node.data);
            node = node.nextNode;
         }
         while(node!=head);
      }
   }
   public void insertStart(int data) {
      Node node = new Node();
      node.data = data;
      node.nextNode = head;
      node.preNode = null;
      
      if(size==0) {
         head = node;
         tail = node;
         node.nextNode = head;
      } else {
         Node tempNode = head;
         node.nextNode = tempNode;
         head = node;
         tail.nextNode = node;
      }
      size++;   
   }
   public void insertEnd(int data) {
      if(size==0) {
         insertStart(data);
      } else {
         Node node = new Node();
         tail.nextNode =node;
         tail = node; 
         tail.nextNode = head;
         size++;   
      }
   }
	public static void main(String args[]) {
      CircularLinked dl = new CircularLinked();
      dl.insertStart(10);
      dl.insertStart(20);
      dl.insertStart(30);
      dl.insertStart(1);
      dl.insertStart(56);
      dl.insertStart(40);
      dl.printData();
   }			
}

输出

40 56 1 30 20 10