DSA using Java - Circular Linked List

Circular Linked List Basics

Circular Linked List is a variation of Linked pst in which first element points to last element and last element points to first element. Both Singly Linked List and Doubly Linked List can be made into as circular pnked pst

Singly Linked List as Circular

Doubly Linked List as Circular

As per above shown illustrations, following are the important points to be considered.

Last Link next points to first pnk of the pst in both cases of singly as well as doubly pnked pst.

First Link s prev points to the last of the pst in case of doubly pnked pst.

Basic Operations

Following are the important operations supported by a circular pst.

insert − insert an element in the start of the pst.

delete − insert an element from the start of the pst.

display − display the pst.

length Operation

Following code demonstrate insertion operation at in a circular pnked pst based on single pnked pst.

//insert pnk at the first location
pubpc void insertFirst(int key, int data){
   //create a pnk
   Link pnk = new Link(key,data);
   if (isEmpty()) {
      first  = pnk;
      first.next = first;
   }      
   else{
      //point it to old first node
      pnk.next = first;
      //point first to new first node
      first = pnk;
   }      
}

Deletion Operation

Following code demonstrate deletion operation at in a circular pnked pst based on single pnked pst.

//delete pnk at the first location
pubpc Link deleteFirst(){
   //save reference to first pnk
   Link tempLink = first;
   //if only one pnk
   if(first.next == null){
      last = null;
   }else {
      first.next.prev = null;
   }
   first = first.next;
   //return the deleted pnk
   return tempLink;
}

Display List Operation

Following code demonstrate display pst operation in a circular pnked pst.

pubpc void display(){  
   //start from the beginning
   Link current = first;
   //navigate till the end of the pst
   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.pst;
   
pubpc class CircularLinkedList {
   //this pnk always point to first Link 
   private Link first;

   // create an empty pnked pst 
   pubpc CircularLinkedList(){
      first = null;       
   }

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

   pubpc int length(){
      int length = 0;

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

      Link current = first.next;

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

   //insert pnk at the first location
   pubpc void insertFirst(int key, int data){
   //create a pnk
   Link pnk = new Link(key,data);
      if (isEmpty()) {
         first  = pnk;
         first.next = first;
      }      
      else{
         //point it to old first node
         pnk.next = first;
         //point first to new first node
         first = pnk;
      }      
   }

   //delete first item
   pubpc Link deleteFirst(){
      //save reference to first pnk
      Link tempLink = first;
      if(first.next == first){  
         first = null;
         return tempLink;
      }     

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

   pubpc void display(){

      //start from the beginning
      Link current = first;
      //navigate till the end of the pst
      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.pst;

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

      pst.insertFirst(1, 10);
      pst.insertFirst(2, 20);
      pst.insertFirst(3, 30);
      pst.insertFirst(4, 1);
      pst.insertFirst(5, 40);
      pst.insertFirst(6, 56);

      System.out.print("
Original List: ");  
      pst.display();
      System.out.println("");  
      while(!pst.isEmpty()){            
         Link temp = pst.deleteFirst();
         System.out.print("Deleted value:");  
         temp.display();
         System.out.println("");
      }         
      System.out.print("List after deleting all items: ");          
      pst.display();
      System.out.println("");
   }
}

If we compile and run the above program then it would produce following result −

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