Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Circular Linked List Complete Implementation

Ear­lier we have seen what is Singly Linked List and How to imple­ment it. In a way you say that it’s an exten­sion of singly linked list. I would sug­gest that if you do not about Linked list, then i would rec­om­mend that first read “Singly Linked List”. Now we will see the dif­fer­ence between them.

Circular Linked List

Cir­cu­lar Linked List

So as we can see the in cir­cu­lar linked list last node in the list is not point­ing to null but its point­ing the first node in the linked list and this makes a cir­cle that is why it is called “Cir­cu­lar Linked List”.

Let’s see how the Node struc­ture will look like

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

Oper­a­tions:

NOTE: we are two ref­er­ences 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 begin­ning 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 ref­er­ence. If size is 0 then make the new node as head and tail else put node at the end of the list using tail ref­er­ence and make the new node as tail.

Delete at the Start : Delete a node from begin­ning 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 Ele­ment at Index : Return the ele­ment at spe­cific 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).

Com­plete Code:

Out­put:

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

You may also like...