Circular Linked List – Explanation and Implementation

In a circular linked list all nodes are connected in a continuous cycle. Each node has two part Data and Next as a singly linked list has. The last node rather pointing to NULL, points to the first node, to which head points. As a result, the structure of the linked list looks like forming a loop, thus named as Circular Linked list.

It provides a way to traverse the list as many times as required. See the linked list shown, once element 50(last node) is traversed, pointer now reaches to the first node, therefore the list can be traversed again. Time taken in revisiting a node takes O(n). This is where a circular linked list lacks, the worst case is if needed to traverse the node just visited then it has to traverse the whole list again. Although it’s better than singly linked list but lacks backward traversing.

Read more – Linked List Types – Explanation

Implementation:

Implementation of a circular linked list is pretty similar to a singly linked list. The only change is how to get to the end of the list. Under singly linked list, it becomes NULL at the end but, for circular linked list traversing till Next starts pointing the head node. Therefore next of last node will contain address of first node(head of linked list).

head = firstNode;
lastNode->next = firstNode;

Implementation in C

#include<stdio.h>
#include<stdlib.h>

//DECLARATION
struct node 
{
	int data;
	struct node *next;
};


// This function prints contents of linked list from given node
void printLinkedList(struct node *list)
{
	struct node *currentNode = list;
	
    do
    {
    	printf(" %d ", list->data);
    	list = list->next; // accessing and assigning the next element of list
    }while(list != currentNode);
}


// Main method to initialize the program
int main()
{
	//INITIALIZATION
    //Declare and allocate 3 nodes in the heap 
    struct node* head;
    struct node* first = (struct node*)malloc(sizeof(struct node)); 
    struct node* second = (struct node*)malloc(sizeof(struct node));
    struct node* third = (struct node*)malloc(sizeof(struct node));
    struct node* fourth = (struct node*)malloc(sizeof(struct node));
    
	//ASSIGNINMENT
    first->data = 10; //assign data in first node
    first->next = second; // Link first node with second 
    
    second->data = 20; //assign data to second node
    second->next = third; 
    
    third->data = 30; //assign data to third node
    third->next = fourth;

    fourth->data = 50; //assign data to fourth node
    fourth->next = first; // last node pointing to the first node

    head = first;    //head pointing to the linked list

   printLinkedList(head);
    
    return 0;
}

Output:-

10 20 30 50

Advantages of Circular linked list over singly linked list:

• Circular linked list acts like a loop, any node can be the beginning node and traversing will be till the pointer reaches the same beginning node. Therefore Round robin fashion of access can be implemented. As a result, a large number of applications are there which can use circular linked list such as in Multi-player Games, Resource allocation in OS, etc. In short, it is widely used wherever the resource pooling is required.
• Circular Doubly linked list results in better implementation of Queue, as there is no overhead of two variable needed to maintain (Front and Rear).
• Any node can be made starting point as required.

Disadvantages

• Backward traversing is not possible.
• Insertion and Deletion takes O(n) in some cases.
• Reversal Operation is same as in singly linked list, there is no better optimization here.

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂

Recommended -