CC-15 : Implement CircularSingleLinkedList .

Description:

Create and test a CircularSingleLinkedList implementation.

CircularLinkedList.

CircularSingleLinkedList consists of list of nodes, where each node has a single link pointing to next node. Additionally, the last node of the CircularSingleLinkedList points to the first node of the CircularSingleLinkedList leading to a circular structure. The structure of a SingleLinkedList node is shown below. The image shows an integer stored as data in the node of the SingleLinkedList node, but you can store any other data type such characters, strings, objects etc. as data in the node. In a CircularSingleLinkedList, if nextNode points to firstNode indicates that we have reached the last node of the CircularSingleLinkedList. In the image, as the first node is the only node in the list, the nextNode link will point to itself indicating there are no further nodes.

 11->points to firstNode (itself)

In the below image, node with data 11 is the first node the CircularSingleLinkedList. Similarly, node with data 54 is the last node the CircularSingleLinkedList so its nextNode link points to first node.

 11->23->16- > 19->54->points to firstNode

Below is the code for the SingleLinkedListNode java class:

public class SingleLinkedListNode  {
	private SingleLinkedListNode nextNode=null;
	private int nodeData=0;
	public SingleLinkedListNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(SingleLinkedListNode nextNode) {
		this.nextNode = nextNode;
	}
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}	
}

Besides SingleLinkedListNode class shown above we also need a class named CircularSingleLinkedList that contains a reference to the firstNode of the CircularSingleLinkedList. Whenever we need to access the data nodes in the CircularSingleLinkedList, we will start from the firstNode and then traverse the whole list using nextNode links. The CircularSingleLinkedList class also contains all the code to add/delete/access/traverse the CircularSingleLinkedList nodes. (partial code snapshot of the DoubleLinkedList is given below):

public class CircularSingleLinkedList {
private SingleLinkedListNode firstNode=null;

public SingleLinkedListNode getFirstNode() {
	return firstNode;
}

public void setFirstNode(SingleLinkedListNode firstNode) {
		this.firstNode = firstNode;
}

public boolean addLast(int data){
	...
}
	

public boolean addFirst(int data){
	...
}
	
...
...
...
}

Addition of node to end of CircularSingleLinkedList.

Pseudocode:

To handle addition of a newNode to end of a SingleLinkedList, we need to handle 2 cases:

If the SingleLinkedList is empty, add the newNode as the firstNode of the SingleLinkedList.

If the SingleLinkedList already has nodes:

Find the last node of the SingleLinkedList and add the newNode as the nextNode of this last node.

As newNode is being added to end of the CircularSingleLinkedList make sure its nextNode link points to firstNode.

Code:

public boolean addLast(int data){
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(firstNode);
		return true;
	}
	else {
		SingleLinkedListNode currentNode=firstNode;
		while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
		currentNode.setNextNode(node);
		node.setNextNode(firstNode);
		return true;	
	}
}

Addition of node to start of CircularSingleLinkedList.

Pseudocode:

To handle addition of newNode to start of a CircularSingleLinkedList, we need to handle 2 cases:

If the CircularSingleLinkedList is empty, add newNode as the firstNode of the SingleLinkedList.

As newNode is first node of the CircularSingleLinkedList make sure its nextNode link points to firstNode.

If the CircularSingleLinkedList already has nodes:

Set nextNode variable of the newNode to current firstNode of the SingleLinkedList.

Set newNode as the firstNode of the SingleLinkedList.

o Find the last node of the CircularSingleLinkedList, and make nextNode of last node point to firstNode of the CircularSingleLinkedList.

Code:

public boolean addFirst(int data){
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(firstNode);
		return true;
	}
	else {
		SingleLinkedListNode currentNode=firstNode;
		while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
		currentNode.setNextNode(node);;
		node.setNextNode(firstNode);
		firstNode=node; 
		return true;			
	}
}

Addition of node to required index in the CircularSingleLinkedList.

Pseudocode:

To handle addition of a newNode to index pos of a CircularSingleLinkedList, we need to handle 3 cases:

If pos is 0 add newNode to start of CircularSingleLinkedList.

If pos is equal to number of nodes in the CircularSingleLinkedList, then add new node to end of the CircularSingleLinkedList.

If pos is an intermediate index:

Identify the node prevNode at position pos-1.

Set nextNode of newNode to nextNode of prevNode.

Set nextNode of prevNode to newNode.

Code:

public boolean add(int data, int pos){	
	int size=getSize();
	if ((pos<0) || (pos > size)) { return false;}
	if (pos==0) {
		addFirst(data);
		return true;
	}
	if (pos==size) {
		addLast(data);
		return true;
	}
	if (firstNode==null) {return false;}
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
	SingleLinkedListNode currentNode=firstNode;
	SingleLinkedListNode prevNode=null;
	int idx=0;
	do  {
	  	if ((idx==pos)){
	  	  	node.setNextNode(prevNode.getNextNode());
	  	  	prevNode.setNextNode(node);
	  	  	return true;
	  	}
	  	prevNode=currentNode;
	  	currentNode=currentNode.getNextNode();
	  	idx++;
	 }  while (currentNode !=firstNode);
	 return false;  	
}

Deletion of first node of CircularSingleLinkedList.

Pseudocode:

To handle deletion of firstNode of CircularSingleLinkedList, we need to handle 2 cases:

If the CircularSingleLinkedList has only one node, the set firstNode variable of CircularSingleLinkedList to null.

If the CircularSingleLinkedList already has more than 1 nodes:

Set firstNode of SingleLinkedList to firstNode.nextNode.

Find the last node of the CircularSingleLinkedList, and make nextNode of last node point to firstNode of the CircularSingleLinkedList.

Code:

public boolean removeFirst() {
	if (firstNode == null) { return false; }
	if (firstNode.getNextNode()==firstNode) {
		firstNode=null; 
		return true;
	}
	SingleLinkedListNode currentNode=firstNode;
	while (currentNode.getNextNode()!=firstNode) {
		currentNode=currentNode.getNextNode(); }
	currentNode.setNextNode(firstNode.getNextNode());
	firstNode=firstNode.getNextNode(); 
	return true;
}

Deletion of last node of CircularSingleLinkedList.

Pseudocode:

To handle deletion of last node of CircularSingleLinkedList, we need to handle 2 cases:

If the CircularSingleLinkedList has only one node, the set firstNode variable of SingleLinkedList to null.

If the CircularSingleLinkedList already has more than 1 nodes:

Find the second last node of the CircularSingleLinkedList and store its reference in prevNode.

Set prevNode.nextNode to firstNode.

Code:

public boolean removeLast() {
	if (firstNode == null) { return false; }
	SingleLinkedListNode currentNode=firstNode;
	SingleLinkedListNode prevNode=null;
	do {
		if (currentNode.getNextNode()==firstNode) {
			if (prevNode==null) {
				firstNode=null;
				return true;
			}
	  		prevNode.setNextNode(firstNode);
	  		return true;
		}
		prevNode=currentNode;
	  	currentNode=currentNode.getNextNode();    		
	  }	while (currentNode !=firstNode);
	return false;
}

Delete node at particular index in the CircularSingleLinkedList.

Pseudocode:

To handle deletion of a node from index pos of a CircularSingleLinkedList, we need to handle 3 cases:

If pos is 0, remove the firstNode of CircularSingleLinkedList.

If pos is equal to number of nodes in the CircularSingleLinkedList, then remove the last node of the CircularSingleLinkedList.

If pos is an intermediate index:

Identify the node prevNode at position pos-1.

Identify the node currentNode at position pos.

Set prevNode.nextNode to currentNode.nextNode.

Code:

public boolean removeAtPos(int pos){	
	if (firstNode == null) { return false; }
	SingleLinkedListNode currentNode=firstNode;
	SingleLinkedListNode prevNode=null;
	int idx=0;
	do {
	   if (idx==pos) {
	   if (prevNode==null) {
	  		removeFirst();
	  		return true;
	  	}
	  	if (currentNode.getNextNode()==firstNode) {
	  		removeLast();
	  		return true;
	  	}
	  	prevNode.setNextNode(currentNode.getNextNode());
	  	return true;
	  	}
	  	prevNode=currentNode;
	  	currentNode=currentNode.getNextNode();  
	  	idx++;
	 } while (currentNode !=firstNode);
	 return false;  	  	
}

Accessing a node at a particular index in the CircularSingleLinkedList.

Pseudocode:

To access a node at particular index, use the nextNode link to traverse through the CircularSingleLinkedList till the required node is reached.

Code:

public int get(int idx) {
	if (firstNode == null) { return Integer.MIN_VALUE; }
	SingleLinkedListNode currentNode=firstNode;
	int currIdx=0;
	do {
	  	if (currIdx==idx) {return currentNode.getNodeData();}
	  	currentNode=currentNode.getNextNode();
	  	currIdx++;
	}while (currentNode !=firstNode);
	return Integer.MIN_VALUE;
}

Getting the size of the CircularSingleLinkedList.

Pseudocode:

To get the size of the CircularSingleLinkedList traverse the CircularSingleLinkedList from firstNode to last node and increment a variable idx for each node traversed.

Code:

public void traverse() {
	SingleLinkedListNode currentNode=firstNode;
	do{
	  	System.out.println(currentNode.getNodeData());
	  	currentNode=currentNode.getNextNode();
	 }while (currentNode !=firstNode);
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class CircularSingleLinkedList {
private SingleLinkedListNode firstNode=null;

public SingleLinkedListNode getFirstNode() {
	return firstNode;
}

public void setFirstNode(SingleLinkedListNode firstNode) {
		this.firstNode = firstNode;
	}

public boolean addLast(int data){
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(firstNode);
		return true;
	}
	else {
		SingleLinkedListNode currentNode=firstNode;
		while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
		currentNode.setNextNode(node);
		node.setNextNode(firstNode);
		return true;	
	}
}
	

public boolean addFirst(int data){
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(firstNode);
		return true;
	}
	else {
		SingleLinkedListNode currentNode=firstNode;
		while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
		currentNode.setNextNode(node);;
		node.setNextNode(firstNode);
		firstNode=node; 
		return true;			
	}
}
	
	
public boolean add(int data, int pos){	
	int size=getSize();
	if ((pos<0) || (pos > size)) { return false;}
	if (pos==0) {
		addFirst(data);
		return true;
	}
	if (pos==size) {
		addLast(data);
		return true;
	}
	if (firstNode==null) {return false;}
	SingleLinkedListNode node=new SingleLinkedListNode();
	node.setNodeData(data);
	SingleLinkedListNode currentNode=firstNode;
	SingleLinkedListNode prevNode=null;
	int idx=0;
	do  {
	  	if ((idx==pos)){
	  	  	node.setNextNode(prevNode.getNextNode());
	  	  	prevNode.setNextNode(node);
	  	  	return true;
	  	}
	  	prevNode=currentNode;
	  	currentNode=currentNode.getNextNode();
	  	idx++;
	 }  while (currentNode !=firstNode);
	 return false;  	
}	
		
		

	
public int getSize() {
	if (firstNode == null) { return 0; }
	SingleLinkedListNode currentNode=firstNode;
	int idx=0;
	do {
	  	currentNode=currentNode.getNextNode();
	  	idx++;
	}while (currentNode !=firstNode) ;
	return idx;
}
	

public boolean removeFirst() {
	if (firstNode == null) { return false; }
	if (firstNode.getNextNode()==firstNode) {
		firstNode=null; 
		return true;
	}
	SingleLinkedListNode currentNode=firstNode;
	while (currentNode.getNextNode()!=firstNode) {
		currentNode=currentNode.getNextNode(); }
	currentNode.setNextNode(firstNode.getNextNode());
	firstNode=firstNode.getNextNode(); 
	return true;
}
	
	
public boolean removeLast() {
	if (firstNode == null) { return false; }
	SingleLinkedListNode currentNode=firstNode;
	SingleLinkedListNode prevNode=null;
	do {
		if (currentNode.getNextNode()==firstNode) {
			if (prevNode==null) {
				firstNode=null;
				return true;
			}
	  		prevNode.setNextNode(firstNode);
	  		return true;
		}
		prevNode=currentNode;
	  	currentNode=currentNode.getNextNode();    		
	  }	while (currentNode !=firstNode);
	return false;
}
	
	
	public boolean remove(int data){
		if (firstNode == null) { return false; }
		SingleLinkedListNode currentNode=firstNode;
	  	SingleLinkedListNode prevNode=null;
	  	 do {
	  		if (currentNode.getNodeData() == data) {
	  			if (prevNode==null) {
	  				removeFirst();
	  				return true;
	  			}
	  			if (currentNode.getNextNode()==firstNode) {
	  				removeLast();
	  				return true;
	  			}
	  			prevNode.setNextNode(currentNode.getNextNode());
	  			return true;
	  		}
	  		prevNode=currentNode;
	  		currentNode=currentNode.getNextNode();  		
	  	}  	while (currentNode !=firstNode);
	  	return false;  	
	 }	
		
	
public boolean removeAtPos(int pos){	
	if (firstNode == null) { return false; }
	SingleLinkedListNode currentNode=firstNode;
	SingleLinkedListNode prevNode=null;
	int idx=0;
	do {
	   if (idx==pos) {
	   if (prevNode==null) {
	  		removeFirst();
	  		return true;
	  	}
	  	if (currentNode.getNextNode()==firstNode) {
	  		removeLast();
	  		return true;
	  	}
	  	prevNode.setNextNode(currentNode.getNextNode());
	  	return true;
	  	}
	  	prevNode=currentNode;
	  	currentNode=currentNode.getNextNode();  
	  	idx++;
	 } while (currentNode !=firstNode);
	 return false;  	  	
}	
	
public int get(int idx) {
	if (firstNode == null) { return Integer.MIN_VALUE; }
	SingleLinkedListNode currentNode=firstNode;
	int currIdx=0;
	do {
	  	if (currIdx==idx) {return currentNode.getNodeData();}
	  	currentNode=currentNode.getNextNode();
	  	currIdx++;
	}while (currentNode !=firstNode);
	return Integer.MIN_VALUE;
}
	
	
public void traverse() {
	SingleLinkedListNode currentNode=firstNode;
	do{
	  	System.out.println(currentNode.getNodeData());
	  	currentNode=currentNode.getNextNode();
	 }while (currentNode !=firstNode);
}

	
	
			
public void printSingleLinkList() throws Exception    {
	// Case 1: The Circular Linked list is empty !!
	if (firstNode == null) { System.out.println("Circular Linked list empty"); return; }
	// Case 2: Print CircularLinkedList node by node
	SingleLinkedListNode currentNode=firstNode;
	System.out.println();
	System.out.println("**************************************************************************************************");
	System.out.print("CircularSingleLinkedList nodes: ");
	do  {
		    System.out.print(currentNode.getNodeData());
		    if (currentNode.getNextNode() != firstNode)  System.out.print(" -> ");
			currentNode=currentNode.getNextNode();
			
		} while( currentNode != firstNode);
	    System.out.print("");
		System.out.println();
		System.out.println("**************************************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		;
		return;
}

public void printSingleLinkList(String labelText) throws Exception    {
	// Case 1: The Circular Linked list is empty !!
	if (firstNode == null) { System.out.println("Circular Linked list empty"); return; }
	// Case 2: Print CircularLinkedList node by node
	SingleLinkedListNode currentNode=firstNode;
	System.out.println();
	System.out.println("**************************************************************************************************");
	System.out.print(labelText);
	do  {
		    System.out.print(currentNode.getNodeData());
		    if (currentNode.getNextNode() != firstNode)  System.out.print(" -> ");
			currentNode=currentNode.getNextNode();
			
		} while( currentNode != firstNode);
	    System.out.print("");
		System.out.println();
		System.out.println("**************************************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		;
		return;
}

public static void main(String[] args) {
	
	
	CircularSingleLinkedList singleLinkedList=new CircularSingleLinkedList();
	try {
	System.out.print("Add First");
	singleLinkedList.addFirst(9);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add First");
	singleLinkedList.addFirst(5);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add First");
	singleLinkedList.addFirst(3);
	singleLinkedList.printSingleLinkList();
	System.out.print("remove First");
	singleLinkedList.removeFirst();
	singleLinkedList.printSingleLinkList();
	System.out.print("remove First");
	singleLinkedList.removeFirst();
	singleLinkedList.printSingleLinkList();
	System.out.print("remove First");
	singleLinkedList.removeFirst();
	singleLinkedList.printSingleLinkList();
	System.out.print("remove First");
	singleLinkedList.removeFirst();
	singleLinkedList.printSingleLinkList();
	
	System.out.print("************************************************************");
	System.out.print("Add Last");
	singleLinkedList.addLast(9);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add Last");
	singleLinkedList.addLast(5);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add Last");
	singleLinkedList.addLast(3);
	singleLinkedList.printSingleLinkList();
	System.out.print("remove Last");
	singleLinkedList.removeLast();
	singleLinkedList.printSingleLinkList();
	System.out.print("remove Last");
	singleLinkedList.removeLast();
	singleLinkedList.printSingleLinkList();
	System.out.print("remove Last");
	singleLinkedList.removeLast();
	singleLinkedList.printSingleLinkList();
	System.out.print("remove Last");
	singleLinkedList.removeLast();
	singleLinkedList.printSingleLinkList();
	
	System.out.print("************************************************************");
	System.out.print("Add First");
	singleLinkedList.addFirst(9);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add First");
	singleLinkedList.addFirst(5);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add First");
	singleLinkedList.addFirst(3);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add Last");
	singleLinkedList.addLast(12);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add Last");
	singleLinkedList.addLast(15);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add Last");
	singleLinkedList.addLast(23);
	singleLinkedList.printSingleLinkList();
	System.out.println("**************SIZE : "+singleLinkedList.getSize());
	System.out.print("Remove 3");
	singleLinkedList.remove(3);
	singleLinkedList.printSingleLinkList();
	System.out.print("Remove 15");
	singleLinkedList.remove(15);
	singleLinkedList.printSingleLinkList();
	System.out.print("Remove 9");
	singleLinkedList.remove(9);
	singleLinkedList.printSingleLinkList();
	System.out.print("Remove 23");
	singleLinkedList.remove(23);
	singleLinkedList.printSingleLinkList();
	System.out.println("**************SIZE : "+singleLinkedList.getSize());
	System.out.print("Add 55  Pos 1");
	singleLinkedList.add(55,1);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add 77  Pos 1");
	singleLinkedList.add(77,1);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add 88  Pos 4");
	singleLinkedList.add(88,4);
	singleLinkedList.printSingleLinkList();
	System.out.print("Add 99  Pos 0");
	singleLinkedList.add(99,0);
	singleLinkedList.printSingleLinkList();
	System.out.println("ELEMENT AT IDX : 0 "+singleLinkedList.get(0));
	System.out.println("ELEMENT AT IDX : 6 "+singleLinkedList.get(6));
	System.out.println("ELEMENT AT IDX : 5 "+singleLinkedList.get(5));
	System.out.println("ELEMENT AT IDX : 2 "+singleLinkedList.get(2));
	System.out.println("TRAVERSE ***** ");
	singleLinkedList.traverse();
	

	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	}
}

public class SingleLinkedListNode  {
	private SingleLinkedListNode nextNode=null;
	private int nodeData=0;
	public SingleLinkedListNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(SingleLinkedListNode nextNode) {
		this.nextNode = nextNode;
	}
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}	
}

		
}