Circular Linked List and Operations

Circular Linked List and Operations in Data Structures

Circular Linked List and Operations

Till now, we've covered linked lists, which consist of a head, the body, and an end pointing to NULL. Basically, it was linear. We could perform traversal, insertion, deletion, searching, and many more operations while traversing to the end of the list.

Today, we’ll explore a variant of it—circular linked lists. We’ll also go through all the operations that we could do in a linear linked list and see how they work in a circular linked list.

Introduction:

A circular linked list is a linked list where the last element points to the first element (head), hence forming a circular chain. There is no node pointing to NULL, meaning there’s no "end" node. In circular linked lists, we have a head pointer, but no starting or ending in the traditional sense.

Refer to the illustration of a circular linked list below:

Operations on a Circular Linked List:

Operations on circular linked lists can be performed just like a singly linked list. The only difference is that we need to maintain an extra pointer to check if we’ve gone through the list once.

Traversal:

Traversal in a circular linked list can be achieved by creating a new struct Node* pointer p, which starts from the head and goes through the list until it points back at the head. This way, we traverse the circle only once, visiting each node.
Since traversal is possible, all other operations (like insertion, deletion, etc.) in a circular linked list become as easy as they are in a linear linked list.
You might find it confusing that there is a head but no "starting" of the circular linked list. That’s correct—the head pointer is just there for our convenience while operating on the list. There’s no first element as such; it’s circular.

Example with Code

In the last section, we learned about circular linked lists, and we discussed the differences and similarities between circular and linear linked lists.

Let me quickly summarize the key points:

Unlike singly linked lists, a circular linked list has no node pointing to NULL. Instead, the last element points to the head node, forming a circle.
All operations (traversal, insertion, deletion, etc.) can be done by maintaining an extra pointer fixed at the head node.
A circular linked list has a head node, but no specific starting or ending node.
We learned to traverse a circular linked list using a do-while loop.

Now, let’s move to coding. Below is an example that shows how to perform insertion in a circular linked list in C.

Creating the Circular Linked List:

Creating a circular linked list is no different from creating a singly linked list. The only difference is that, instead of having the last element point to NULL, we’ll make it point to the head.
While creating these nodes and connecting them, this is the third time we are doing it, so by now you should be gaining confidence!

struct Node
{
    int data;
    struct Node *next;
};
int main(){
    
    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
 
    // Allocate memory for nodes in the linked list in Heap
    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));
 
    // Link first and second nodes
    head->data = 4;
    head->next = second;
 
    // Link second and third nodes
    second->data = 3;
    second->next = third;
 
    // Link third and fourth nodes
    third->data = 6;
    third->next = fourth;
 
    // Terminate the list at the third node
    fourth->data = 1;
    fourth->next = head;
 
    return 0;
}

Code Snippet 1: Creating the circular linked list

Traversing the Circular Linked List:

Create a void function named linkedListTraversal and pass the head pointer of the circular linked list to the function.
Inside the function, create a pointer named ptr and set it to point to the head.
Use a do-while loop to traverse the list. The loop should continue until ptr reaches the last node and ptr->next points back to the head (i.e., ptr->next == head). During the traversal, print the data of each node.
The do-while loop is crucial here because it allows you to handle the circular nature of the list, ensuring you traverse through it exactly once.

void linkedListTraversal(struct Node *head){
    struct Node *ptr = head;
    do{
        printf("Element is %d\n", ptr->data);
        ptr = ptr->next;
    }while(ptr!=head);
}

Code Snippet 2: Traversing the circular linked list

Inserting into a Circular Linked List:

Let’s focus on the insertion at the head. The rest of the variations (insertion at other positions) will be quite similar to what you already know from singly linked lists.
Create a function called insertAtFirst which will return the pointer to the new head of the circular linked list.
Pass the current head pointer and the data to be inserted at the beginning as arguments to this function.
Inside the function, create a pointer called ptr that will point to a new memory location allocated in the heap (this will be the new node). Don’t forget to include the header file <stdlib.h> when you're working with dynamic memory.
Next, create another pointer, p, which points to the next node of the current head (p = head->next).
Use a while loop to traverse the list until p points to the last node (i.e., until p->next becomes the head).

Now, assign ptr to the next of p, i.e., p->next = ptr. Then, set the next of ptr to point to the head, i.e., ptr->next = head.
Finally, make ptr the new head by assigning head = ptr.

Return head.

struct Node * insertAtFirst(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;
 
    struct Node * p = head->next;
    while(p->next != head){
        p = p->next;
    }
    // At this point p points to the last node of this circular linked list
 
    p->next = ptr;
    ptr->next = head;
    head = ptr;
    return head;
 
}

Code Snippet 3: Inserting into a circular linked list

Here is the whole source code:

#include<stdio.h>
#include<stdlib.h>
 
struct Node
{
    int data;
    struct Node *next;
};
 
void linkedListTraversal(struct Node *head){
    struct Node *ptr = head;
    do{
        printf("Element is %d\n", ptr->data);
        ptr = ptr->next;
    }while(ptr!=head);
}
 
struct Node * insertAtFirst(struct Node *head, int data){
    struct Node * ptr = (struct Node *) malloc(sizeof(struct Node));
    ptr->data = data;
 
    struct Node * p = head->next;
    while(p->next != head){
        p = p->next;
    }
    // At this point p points to the last node of this circular linked list
 
    p->next = ptr;
    ptr->next = head;
    head = ptr;
    return head;
 
}
 
int main(){
    
    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
 
    // Allocate memory for nodes in the linked list in Heap
    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));
 
    // Link first and second nodes
    head->data = 4;
    head->next = second;
 
    // Link second and third nodes
    second->data = 3;
    second->next = third;
 
    // Link third and fourth nodes
    third->data = 6;
    third->next = fourth;
 
    // Terminate the list at the third node
    fourth->data = 1;
    fourth->next = head;
 
    return 0;
}

Code Snippet 4: Insertion and traversal in a circular linked list

We’ll now see whether the functions work accurately. Let’s insert a few nodes at the beginning.

  printf("Circular Linked list before insertion\n");
    linkedListTraversal(head);
    head = insertAtFirst(head, 54);
    head = insertAtFirst(head, 58);
    head = insertAtFirst(head, 59);
    printf("Circular Linked list after insertion\n");
    linkedListTraversal(head);

Code snippet 5: Using the insertAtFirst function

Refer to the output below:

Circular Linked list before insertion
Element is 4
Element is 3
Element is 6
Element is 1
Circular Linked list after insertion
Element is 59
Element is 58
Element is 54
Element is 4
Element is 3
Element is 6
Element is 1

Deletion in a Linked ListTree

Doubly Linked Lists

Circular Linked List and Operations