Dsa Using Java 简明教程

DSA using Java - Circular Linked List

Circular Linked List Basics

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

Singly Linked List as Circular

dsa singly circularlinkedlist

Doubly Linked List as Circular

dsa doubly circularlinkedlist

根据上面显示的说明，以下是需要考虑的重要事项。

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

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

Basic Operations

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

  1. insert − 在列表的开头插入一个元素。

  2. delete − 从列表的开头插入一个元素。

  3. display − 显示列表。

length Operation

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

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

Deletion Operation

以下代码演示基于单链表的循环链表中的删除操作。

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

Display List Operation

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

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(" ]");
}

Demo

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: [  ]