Circular Linked List in Java

Introduction: Circular linked list is a special type of linked list where all nodes are connected to each other in a circular manner.A circular linked list can be implemented using singly node (Singly Circular Linked List) or doubly node (Doubly Circular Linked List).In this post, we will see the implementation of Singly Circular Linked List using JAVA but before going for implementation, we should know the key features and advantages of circular linked list.

 

Key Feature:

  1. All nodes are connected to each other. No NULL pointers are present in circular linked list.
  2. Any node of circular linked list can be the starting point. Each node is unique (data of nodes might be same).
  3. Identify the root node in one shot
  4. Useful in multiple problem solving algorithms like Round Robin and Josephus Circle.

Advantage:

  1. Multi-Player Gaming Applications. We all know a very famous game named ” Ludo” and “Snakes & Ladders”. This is a multi-player game where each player will get the chance to rotate the dice in a sequential way. Circular linked list could be the data structure to implement such type of gaming applications. Each player will be treated as single node of circular linked list and they will get the chance to rotate the dice in periodic manner.
  2. Time sharing environment in operating system. The operating system should maintain a list of program and must alternately allow each program to use a small slice of CPU time. The operating system will pick a program, let program use a small amount of CPU time and then move on to the next program.
  3. Base data structure for implementing Queue and advance DS like Fibonacci Heap.

Now, We will see the implementation of add and delete operations of singly circular linked list in java. It’s recommended to refer the add and delete operations of singly linked list before going for circular linked list. The only difference between singly linked list and singly circular linked list is, in case of singly linked list, next pointer of last node will be always NULL but in case of singly circular linked list, next pointer of last node will be start node to form loop.

Node.java :

 

Below is the SinglyCircularLinkedList class having add and delete operations. Also, class is implementing the iterable  interface to have iterator functionality.

SinglyCircularLinkedList.java :

Player.java : DTO class

 

SinglyCircularLinkedListTest.java : 

 

Output:

Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]
Player [playerId=1, playerName=Jhon]
Player [playerId=2, playerName=Tom]
Player [playerId=3, playerName=Jerry]
Player [playerId=4, playerName=Smith]

 

Top