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 :

package com.netSurfingZone.circularLinkedList;

public class Node<T> {

	private T data ;
	
	private Node<T> next;

	public Node(T data) {
		this.data = data;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public Node<T> getNext() {
		return next;
	}

	public void setNext(Node<T> next) {
		this.next = next;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((data == null) ? 0 : data.hashCode());
		result = prime * result + ((next == null) ? 0 : next.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof Node))
			return false;
		Node other = (Node) obj;
		if (data == null) {
			if (other.data != null)
				return false;
		} else if (!data.equals(other.data))
			return false;
		if (next == null) {
			if (other.next != null)
				return false;
		} else if (!next.equals(other.next))
			return false;
		return true;
	}
}

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

SinglyCircularLinkedList.java :

package com.netSurfingZone.circularLinkedList;

import java.util.Iterator;


public class SinglyCircularLinkedList<T> implements Iterator<T>,Iterable<T>{
	private Node<T> iteratorPointer;
	private int size = 0;
	private Node<T> rootNode;
	private Node<T> lastNode;
	
	/**
	 * Add element
	 * 
	 * @param data
	 */
	public void add(T data) {
		if (data == null) {
			return;
		}
       /**
        * if circular linked list is empty and trying to add data, newly created node will be the 
        * root node and root node and last node will be same.
        */
		if (rootNode == null) {
			rootNode = new Node<T>(data);
			lastNode=rootNode;
			// connect last node to root node
			lastNode.setNext(rootNode);
			resetIteratorPointer();
		} else {
			Node<T> newNode = new Node<T>(data);
			lastNode.setNext(newNode);
			lastNode=newNode;
			// Last node will again connected to first Node; 
			lastNode.setNext(rootNode);
		}
		size++;
	}
	
	/**
	 * Delete the first occurrence of element from circular linked list if exists and returns
	 * true. If data not available , it returns false;
	 * 
	 * @param data
	 * @return
	 */
	public boolean delete(T data) {
		if (this.rootNode == null) {
			return false;
		}
		// Delete first element
		if(this.rootNode.getData().equals(data)) {
			this.rootNode=this.rootNode.getNext();
			lastNode.setNext(this.rootNode);
			resetIteratorPointer();
			size--;
			return true;
		}
		Node<T> pointerNode = this.rootNode;
		Node<T> previousNode=null;
		while (pointerNode.getData()!=null) {
			if(pointerNode.getData().equals(data)) {
				Node<T> nextNode=pointerNode.getNext();
				previousNode.setNext(nextNode);
				size--;
				return true;
			}
			else {
				previousNode=pointerNode;
				pointerNode=pointerNode.getNext();	
			}
		}
		return false;
	}

	@Override
	public boolean hasNext() {
		if(iteratorPointer ==null) {
			return false;
		}
		if(iteratorPointer!=null) {
			return true;
		}
		return false;
	}

	@Override
	public T next() {
		T data=iteratorPointer.getData();
		iteratorPointer=iteratorPointer.getNext();
		return data;
	}

	@Override
	public Iterator<T> iterator() {
		return this;
	}
	public void resetIteratorPointer() {
		iteratorPointer=this.rootNode;
	}
	
	public int size() {
		return this.size;
	}
	
	@Override
	public String toString() {
		if(this.rootNode ==null) {
			return "[]";
		}
		String represent = "[" + this.rootNode.toString() + ",";
		Node<T> nextNode = next(this.rootNode);
		while (nextNode != this.rootNode) {
			represent = represent + nextNode.toString();
			nextNode = next(nextNode);
			if (nextNode != null) {
				represent = represent + ",";
			}
		}
		represent = represent + "]";
		return represent;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = super.hashCode();
		result = prime * result + ((rootNode == null) ? 0 : rootNode.hashCode());
		result = prime * result + size;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (!super.equals(obj))
			return false;
		if (!(obj instanceof SinglyCircularLinkedList))
			return false;
		SinglyCircularLinkedList other = (SinglyCircularLinkedList) obj;
		if (rootNode == null) {
			if (other.rootNode != null)
				return false;
		} else if (!rootNode.equals(other.rootNode))
			return false;
		if (size != other.size)
			return false;
		return true;
	}
	
	private Node<T> next(Node<T> node) {
		if (node.getNext() != null) {
			return node.getNext();
		} else {
			return null;
		}
	}
}

Player.java : DTO class

package com.netSurfingZone.circularLinkedList;

public class Player {

	private Integer playerId;
	private String playerName;
	
	public Player(Integer playerId, String playerName) {
		super();
		this.playerId = playerId;
		this.playerName = playerName;
	}

	public Integer getPlayerId() {
		return playerId;
	}

	public void setPlayerId(Integer playerId) {
		this.playerId = playerId;
	}

	public String getPlayerName() {
		return playerName;
	}

	public void setPlayerName(String playerName) {
		this.playerName = playerName;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((playerId == null) ? 0 : playerId.hashCode());
		result = prime * result + ((playerName == null) ? 0 : playerName.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof Player))
			return false;
		Player other = (Player) obj;
		if (playerId == null) {
			if (other.playerId != null)
				return false;
		} else if (!playerId.equals(other.playerId))
			return false;
		if (playerName == null) {
			if (other.playerName != null)
				return false;
		} else if (!playerName.equals(other.playerName))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Player [playerId=" + playerId + ", playerName=" + playerName + "]";
	}
	
	
}

SinglyCircularLinkedListTest.java : 

package com.netSurfingZone.circularLinkedList;

import java.util.Iterator;

public class SinglyCircularLinkedListTest {

	public static void main(String[] args) { 
		
		Player player1=new Player(1, "Jhon");
		Player player2=new Player(2, "Tom");
		Player player3=new Player(3, "Jerry");
		Player player4=new Player(4, "Smith");
		Player player5=new Player(5, "Temp");

		SinglyCircularLinkedList<Player> list=new SinglyCircularLinkedList<Player>();
		list.add(player1);
		list.add(player2);
		list.add(player3);
		list.add(player4);
		list.add(player5);
		// Deleted player 5
		list.delete(player5);
		
		int counter=1;
		Iterator<Player> iterator = list.iterator();
		while (iterator.hasNext() && counter <= 20) {
			Player next = iterator.next();
			System.out.println(next);
			counter++;
		}
		list.resetIteratorPointer();
	}

}

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]