Circular Linked List Complete Implementation

Earlier we have seen what is Singly Linked List and How to implement it. In a way you say that it’s an extension of singly linked list. I would suggest that if you do not about Linked list, then i would recommend that first read “Singly Linked List“. Now we will see the difference between them.

So as we can see the in circular linked list last node in the list is not pointing to null but its pointing the first node in the linked list and this makes a circle that is why it is called “Circular Linked List”.

Let’s see how the Node structure will look like

class Node{
     int data;
     Node next;
     public Node(int data){
        this.data = data;
     }
}

Operations:

NOTE: we are two references here, head and tail. Head points the start of the linked list and tail points to the last node of the linked list.

Add at the Start : Add a node the beginning of the linked list. Its O(1). If size is 0 then make the new node as head and tail else put the at the start, change the head and do not change the tail.

Add at the End : Add a node at the end of the linked list. its O(1) since we have tail reference. If size is 0 then make the new node as head and tail else put node at the end of the list using tail reference and make the new node as tail.

Delete at the Start : Delete a node from beginning of the linked list and make the head points to the 2nd node in the list. Its O(1).

Get Size: returns the size of the linked list.

Get Element at Index : Return the element at specific index, if index is greater than the size then return –1. its O(n) in worst case.

Print: Prints the entire linked list. O(n).

Complete Code:


	public class CircularLinkedList {

	public int size =0;
	public Node head=null;
	public Node tail=null;

	//add a new node at the start of the linked list
	public void addNodeAtStart(int data){
	System.out.println("Adding node " + data + " at start");
	Node n = new Node(data);
	if(size==0){
	head = n;
	tail = n;
	n.next = head;
	}else{
	Node temp = head;
	n.next = temp;
	head = n;
	tail.next = head;
	}
	size++;
	}

	public void addNodeAtEnd(int data){
	if(size==0){
	addNodeAtStart(data);
	}else{
	Node n = new Node(data);
	tail.next =n;
	tail=n;
	tail.next = head;
	size++;
	}
	System.out.println("\nNode " + data + " is added at the end of the list");
	}

	public void deleteNodeFromStart(){
	if(size==0){
	System.out.println("\nList is Empty");
	}else{
	System.out.println("\ndeleting node " + head.data + " from start");
	head = head.next;
	tail.next=head;
	size—;
	}
	}

	public int elementAt(int index){
	if(index>size){
	return –1;
	}
	Node n = head;
	while(index–1!=0){
	n=n.next;
	index—;
	}
	return n.data;
	}

	//print the linked list
	public void print(){
	System.out.print("Circular Linked List:");
	Node temp = head;
	if(size<=0){
	System.out.print("List is empty");
	}else{
	do {
	System.out.print(" " + temp.data);
	temp = temp.next;
	}
	while(temp!=head);
	}
	System.out.println();
	}

	//get Size
	public int getSize(){
	return size;
	}

	public static void main(String[] args) {
	CircularLinkedList c = new CircularLinkedList();
	c.addNodeAtStart(3);
	c.addNodeAtStart(2);
	c.addNodeAtStart(1);
	c.print();
	c.deleteNodeFromStart();
	c.print();
	c.addNodeAtEnd(4);
	c.print();
	System.out.println("Size of linked list: "+ c.getSize());
	System.out.println("Element at 2nd position: "+ c.elementAt(2));
	}

	}

	class Node{
	int data;
	Node next;
	public Node(int data){
	this.data = data;
	}
	}

view raw

CircularLinkedList.java

hosted with ❤ by GitHub

Output:

Adding node 3 at start
Adding node 2 at start
Adding node 1 at start
Circular Linked List: 1 2 3
deleting node 1 from start
Circular Linked List: 2 3
Node 4 is added at the end of the list
Circular Linked List: 2 3 4
Size of linked list: 3
Element at 2nd position: 3

Related Posts: