Introduction to Circular Linked Lists: A Comprehensive Guide

A circular linked list is a fascinating and efficient data structure that bridges the gap between functionality and optimization. Unlike a traditional linked list, it forms a closed loop, ensuring that traversal remains uninterrupted and continuous. This tutorial provides an in-depth exploration of circular linked lists, their structure, types, operations, advantages, disadvantages, and applications.

What is a Circular Linked List?

A circular linked list is a specialized type of linked list where the last node connects back to the first node instead of pointing to NULL. This circular connection transforms the list into a loop, allowing for continuous traversal. Unlike regular linked lists, where traversing requires you to know the endpoint, circular linked lists eliminate such constraints, making them ideal for applications requiring cyclic operations, like task scheduling and media playlist management.

In a circular linked list, you can traverse the list starting at any node and will eventually return to that same node. This unique feature ensures dynamic navigation and enables the list to be traversed infinitely without encountering a null pointer.

Types of Circular Linked Lists

There are two primary types of circular linked lists, each suited to specific applications:

1. Circular Singly Linked List

In a Circular Singly Linked List, each node contains:

• Data: The information the node holds.
• Next pointer: Points to the next node in the sequence.

The last node’s next pointer does not point to NULL as in a regular singly linked list. Instead, it points to the first node, completing the circular structure. This configuration allows traversal in one direction only, making it a lightweight and straightforward choice for applications like buffers or basic scheduling systems.

2. Circular Doubly Linked List

A Circular Doubly Linked List is an extension of the singly version with an additional prev pointer in each node.

• The prev pointer points to the previous node in the sequence.
• The next pointer points to the next node.

In this type:

• The last node’s next pointer points back to the first node.
• The first node’s prev pointer points to the last node.

This bidirectional traversal capability makes the Circular Doubly Linked List more versatile for applications like media players, where moving both forward and backward is essential.

Representation of Circular Singly Linked List

The structure of a Circular Singly Linked List in programming typically involves nodes defined using structures or classes. Below is an example of C syntax for defining and creating a node:

// Node structure
struct Node {
    int data;           // Stores data
    struct Node *next;  // Pointer to the next node
};

// Function to create a new node
struct Node *createNode(int value) {
    // Allocate memory
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));

    // Set data
    newNode->data = value;
    
    // Initialize next pointer
    newNode->next = NULL;

    // Return the new node
    return newNode;
}

In the example above, each node contains data and a next pointer. To create a circular structure, the last node’s next pointer is connected to the first node.

Example: Creating a Circular Singly Linked List

Consider a circular linked list with three nodes holding values 1, 2, and 3. Here’s how it works:

• Create three nodes: Each node is allocated memory and initialized with data values.
• Connect nodes sequentially:
  • Set the next pointer of the first node to the second node.
  • Set the next pointer of the second node to the third node.
• Link the last node to the first:
  • The next pointer of the last node is assigned the address of the first node, completing the circle.

Key Features of Circular Linked Lists

• Efficient Memory Use: The circular structure ensures no NULL pointers are required at the end.
• Continuous Traversal: You can traverse the entire list without worrying about termination.
• Dynamic Applications: Great for processes requiring cyclic iteration, like scheduling algorithms.

Operations on Circular Linked Lists

Operations on a circular linked list are similar to those on regular linked lists, with additional considerations for maintaining the circular structure. Key operations include insertion, deletion, and searching.

• Insertion
  • Insertion at the empty list
  • Insertion at the beginning
  • Insertion at the end
  • Insertion at the given position
• Deletion
  • Delete the first node
  • Delete the last node
  • Delete the node from any position
• Searching

1. Insertion in the Circular Linked Lists

Insertion involves adding a node to the list while ensuring it remains circular. Common methods include:

(a.) Insertion into an Empty List in Circular Linked List

To insert into an empty list:

• Create a new node.
• Set its next pointer to point to itself.
• Update the pointer to reference this new node.

This forms a single-node circular linked list.

Implementation of Code in C Programming Language

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

// Define the Node structure
struct Node {
    int data;            // Data field to store the value
    struct Node* next;   // Pointer to the next node
};

// Function to create a new node
struct Node* createNode(int value) {
    // Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    // Set the data value
    newNode->data = value;
    
    // Initialize the next pointer to point to itself
    // since it's a circular linked list
    newNode->next = newNode;
    
    return newNode;
}

// Function to insert a node into an empty circular singly linked list
struct Node* insertInEmptyList(struct Node* last, int data) {
    // Check if the list is empty
    if (last != NULL) {
        return last; // If not empty, return the existing list
    }

    // Create a new node
    struct Node* newNode = createNode(data);

    // Update the 'last' pointer to point to the new node
    last = newNode;

    // Since this is a circular list, make the new node point to itself
    last->next = last;

    return last;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    // If the list is empty, return
    if (last == NULL) {
        printf("List is empty.\n");
        return;
    }

    // Start from the first node (head)
    struct Node* current = last->next;

    // Traverse and print the data of each node
    do {
        printf("%d ", current->data);
        current = current->next; // Move to the next node
    } while (current != last->next); // Stop when we return to the starting node

    printf("\n");
}

// Main function to demonstrate insertion in a circular singly linked list
int main() {
    struct Node* last = NULL; // Initialize the 'last' pointer to NULL

    // Insert a node into the empty circular linked list
    last = insertInEmptyList(last, 1);

    // Print the circular linked list
    printf("List after insertion: ");
    printList(last);

    return 0;
}

Step-by-Step Explanation

• Defining the Node Structure
  • The struct Node defines a single node in the circular linked list:
    • int data: Holds the value of the node.
    • struct Node* next: Points to the next node in the list. In a circular linked list, this pointer eventually loops back to the first node.
• Creating a New Node
  • The createNode function:
    • Allocates memory for a new node using malloc.
    • Sets the data field to the provided value.
    • Initializes the next pointer to point to itself, as it’s a circular linked list.
    • Returns the newly created node.
• Inserting into an Empty List
  • The insertInEmptyList function:
    • Checks if the list is already initialized by examining the last pointer.
    • If the list is empty (last == NULL), it creates a new node using createNode.
    • Sets the last pointer to reference the new node.
    • Ensures that the new node’s next pointer references itself, maintaining the circular structure.
• Printing the Circular Linked List
  • The printList function:
    • Checks if the list is empty (last == NULL). If it is, prints a message and exits.
    • Starts traversal from the node pointed to by last->next (the first node).
    • Uses a do-while loop to traverse and print each node’s data until the traversal returns to the starting node.
    • Ensures that the circular nature of the list is respected by breaking when it returns to the starting node.
• Main Function
  • The main function:
    • Initializes the list by setting the last pointer to NULL.
    • Inserts a single node with the value 1 into the empty list using insertInEmptyList.
    • Prints the resulting circular linked list using printList.

Expected Output

List after insertion: 1

This output demonstrates the successful insertion of a single node into an empty circular linked list. The printList function confirms the circular nature of the list by looping through the single node and printing its value.

(b.) Insertion at the Beginning in Circular Linked List

To insert at the beginning:

• Create a new node.
• Set its next pointer to point to the current head (i.e., last->next).
• Update the last node’s next pointer to point to the new node.

This ensures the circular structure is maintained.

Implementation of Code in C Programming Language

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

// Define the Node structure
struct Node {
    int data;            // Data field to store the value
    struct Node* next;   // Pointer to the next node
};

// Function to create a new node
struct Node* createNode(int value) {
    // Allocate memory for the new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    
    // Set the data field with the provided value
    newNode->data = value;
    
    // Initialize the next pointer to NULL
    newNode->next = NULL;
    
    return newNode; // Return the created node
}

// Function to insert a node at the beginning of a circular linked list
struct Node* insertAtBeginning(struct Node* last, int value) {
    // Create a new node with the given value
    struct Node* newNode = createNode(value);

    // Case 1: If the list is empty
    if (last == NULL) {
        // Make the new node point to itself to form a circular list
        newNode->next = newNode;
        return newNode; // Return the new node as the last node
    }

    // Case 2: If the list is not empty
    // Point the new node to the first node (last->next)
    newNode->next = last->next;
    
    // Update the last node's next pointer to point to the new node
    last->next = newNode;

    // Return the last node (unchanged)
    return last;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    // Check if the list is empty
    if (last == NULL) {
        printf("List is empty.\n");
        return;
    }

    // Start from the first node (last->next)
    struct Node* current = last->next;

    // Traverse the list and print each node's data
    do {
        printf("%d ", current->data);
        current = current->next; // Move to the next node
    } while (current != last->next); // Stop when we return to the first node

    printf("\n");
}

// Main function to demonstrate the operations
int main() {
    // Step 1: Create a circular linked list with nodes 2, 3, 4
    struct Node* first = createNode(2);        // Create the first node
    first->next = createNode(3);              // Create and link the second node
    first->next->next = createNode(4);        // Create and link the third node
    struct Node* last = first->next->next;    // Set the last node
    last->next = first;                       // Complete the circular link

    // Step 2: Print the original list
    printf("Original list: ");
    printList(last);

    // Step 3: Insert 5 at the beginning of the circular linked list
    last = insertAtBeginning(last, 5);

    // Step 4: Print the updated list
    printf("List after inserting 5 at the beginning: ");
    printList(last);

    return 0;
}

Step-by-Step Explanation

• Define the Node Structure
  • The struct Node defines each node in the list:
    • int data: Holds the value of the node.
    • struct Node* next: Points to the next node in the list.
• Create a New Node
  • The createNode function:
    • Allocates memory for a new node using malloc.
    • Sets the data field with the provided value.
    • Initializes the next pointer to NULL (will be updated later).
• Insert a Node at the Beginning
  • The insertAtBeginning function:
    • Creates a new node with the given value.
    • Checks if the list is empty (last == NULL):
      • If empty, the new node points to itself, forming a single-node circular list.
    • If the list is not empty:
      • The new node’s next pointer is updated to point to the current head (last->next).
      • The last node’s next pointer is updated to point to the new node, maintaining the circular structure.
• Print the Circular Linked List
  • The printList function:
    • Starts from the head of the list (last->next).
    • Uses a do-while loop to traverse and print each node’s data.
    • Stops when it loops back to the starting node, ensuring it doesn’t enter an infinite loop.
• Main Function
  • The main function:
    • Creates a circular linked list with nodes 2, 3, and 4.
    • Prints the original list using printList.
    • Inserts a new node with value 5 at the beginning using insertAtBeginning.
    • Prints the updated list to show the insertion result.

Expected Output

Original list: 2 3 4
List after inserting 5 at the beginning: 5 2 3 4

This output confirms that the node with value 5 has been successfully inserted at the beginning of the circular linked list.

(c.) Insertion at the End in Circular Linked List

To insert at the end:

• Create a new node.
• Set its next pointer to point to the head.
• Update the current last node’s next pointer to point to the new node.
• Update the last pointer to reference the new node.

Implementation of Code in C Programming Language

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

// Define the Node structure
struct Node {
    int data;            // Stores the value of the node
    struct Node* next;   // Points to the next node in the list
};

// Function to create a new node
struct Node* createNode(int value) {
    // Allocate memory for a new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    // Set the data field with the provided value
    newNode->data = value;
    // Initialize the next pointer to NULL
    newNode->next = NULL;
    return newNode; // Return the created node
}

// Function to insert a node at the end of the circular linked list
struct Node* insertEnd(struct Node* tail, int value) {
    // Create a new node with the given value
    struct Node* newNode = createNode(value);

    // Case 1: If the list is empty
    if (tail == NULL) {
        // Initialize the list with the new node, pointing to itself
        tail = newNode;
        newNode->next = newNode; // Make the new node circular
    }
    // Case 2: If the list is not empty
    else {
        // Insert the new node after the current tail
        newNode->next = tail->next; // New node points to the first node
        tail->next = newNode;       // Current tail points to the new node
        tail = newNode;             // Update the tail to the new node
    }
    return tail; // Return the updated tail node
}

// Function to print the circular linked list
void printList(struct Node* tail) {
    // Check if the list is empty
    if (tail == NULL) {
        printf("List is empty.\n");
        return;
    }

    // Start from the first node (tail->next)
    struct Node* current = tail->next;
    do {
        // Print the data of the current node
        printf("%d ", current->data);
        // Move to the next node
        current = current->next;
    } while (current != tail->next); // Stop when back at the first node

    printf("\n");
}

// Main function to demonstrate the operations
int main() {
    // Step 1: Create a circular linked list with nodes 2, 3, and 4
    struct Node* first = createNode(2);        // Create the first node
    first->next = createNode(3);              // Create and link the second node
    first->next->next = createNode(4);        // Create and link the third node
    struct Node* tail = first->next->next;    // Set the tail to the last node
    tail->next = first;                       // Complete the circular link

    // Step 2: Print the original list
    printf("Original list: ");
    printList(tail);

    // Step 3: Insert elements 5 and 6 at the end of the circular linked list
    tail = insertEnd(tail, 5); // Insert 5
    tail = insertEnd(tail, 6); // Insert 6

    // Step 4: Print the updated list
    printf("List after inserting 5 and 6: ");
    printList(tail);

    return 0;
}

Step-by-Step Explanation

• Define the Node Structure
  • The struct Node is defined to represent each element in the circular linked list:
    • int data: Stores the value of the node.
    • struct Node* next: Points to the next node in the list.
• Create a New Node
  • The createNode function:
    • Allocates memory for a new node using malloc.
    • Sets the node’s data field with the given value.
    • Initializes the next pointer to NULL for now.
    • Returns the newly created node.
• Insert a Node at the End
  • The insertEnd function:
    • Creates a new node with the specified value.
    • If the list is empty (tail == NULL):
      • Initializes the list with the new node, making it circular by pointing it to itself.
    • If the list is not empty:
      • The new node’s next pointer is updated to point to the first node (tail->next).
      • The current tail node’s next pointer is updated to point to the new node.
      • The tail pointer is updated to the new node, making it the last node.
• Print the Circular Linked List
  • The printList function:
    • Checks if the list is empty (tail == NULL) and prints a message if so.
    • Starts traversing from the first node (tail->next).
    • Uses a do-while loop to print each node’s data until it loops back to the first node.
• Main Function
  • The main function:
    • Creates a circular linked list with nodes 2, 3, and 4:
      • Creates and links nodes using createNode.
      • Sets the tail pointer to the last node.
      • Makes the list circular by setting the last node’s next pointer to the first node.
    • Prints the original list using printList.
    • Inserts two nodes (5 and 6) at the end using insertEnd.
    • Prints the updated list to confirm the insertion.

Expected Output

Original list: 2 3 4 
List after inserting 5 and 6: 2 3 4 5 6 

This output confirms that the nodes with values 5 and 6 were successfully added at the end of the circular linked list.

(d.) Insertion at a Specific Position in Circular Linked List

To insert at a specific position:

• Traverse the list to the desired position.
• Adjust the next pointer of the preceding node to point to the new node.
• Set the new node’s next pointer to the following node.

Implementation of Code in C Programming Language

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

// Define the Node structure
struct Node {
    int data;            // Stores the value of the node
    struct Node *next;   // Points to the next node in the circular linked list
};

// Function to create a new node
struct Node* createNode(int value) {
    // Allocate memory for a new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value; // Set the data value
    newNode->next = NULL;  // Initialize next pointer to NULL
    return newNode;        // Return the created node
}

// Function to insert a node at a specific position in a circular linked list
struct Node* insertAtPosition(struct Node *last, int data, int pos) {
    // Case 1: If the list is empty
    if (last == NULL) {
        // In an empty list, the only valid position is 1
        if (pos != 1) {
            printf("Invalid position!\n");
            return last;
        }
        // Create a new node and make it point to itself
        struct Node *newNode = createNode(data);
        newNode->next = newNode;
        return newNode; // Return the new node as the only element in the list
    }

    // Case 2: The list is not empty
    struct Node* newNode = createNode(data); // Create a new node
    struct Node* curr = last->next;          // Start from the first node

    // Subcase 1: Insert at the beginning
    if (pos == 1) {
        newNode->next = curr;  // The new node points to the first node
        last->next = newNode;  // Update the last node to point to the new first node
        return last;
    }

    // Subcase 2: Insert at a specific position (other than the first)
    for (int i = 1; i < pos - 1; ++i) {
        curr = curr->next; // Move to the next node
        if (curr == last->next) {
            printf("Invalid position!\n");
            return last; // If position is out of bounds, return the original list
        }
    }

    // Insert the new node at the desired position
    newNode->next = curr->next; // New node points to the next node in the list
    curr->next = newNode;       // Previous node points to the new node

    // If the new node is added at the end, update the last pointer
    if (curr == last) {
        last = newNode;
    }

    return last; // Return the updated list
}

// Function to print the circular linked list
void printList(struct Node *last) {
    if (last == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct Node *head = last->next; // Start from the first node
    do {
        printf("%d ", head->data);  // Print the data
        head = head->next;         // Move to the next node
    } while (head != last->next);  // Stop when back at the first node

    printf("\n");
}

// Main function
int main() {
    // Step 1: Create a circular linked list with nodes 2, 3, and 4
    struct Node *first = createNode(2); // Create the first node
    first->next = createNode(3);        // Create and link the second node
    first->next->next = createNode(4);  // Create and link the third node
    struct Node *last = first->next->next; // Set the last node
    last->next = first; // Complete the circular link

    // Step 2: Print the original list
    printf("Original list: ");
    printList(last);

    // Step 3: Insert a new node with value 5 at position 2
    int data = 5, pos = 2;
    last = insertAtPosition(last, data, pos);

    // Step 4: Print the list after insertion
    printf("List after insertions: ");
    printList(last);

    return 0;
}

Step-by-Step Explanation

• Define the Node Structure
  • The struct Node is defined with two fields:
    • data: Holds the integer value of the node.
    • next: A pointer that links to the next node in the circular linked list.
• Create a New Node
  • The createNode function:
    • Allocates memory for a new node using malloc.
    • Initializes the node’s data with the given value.
    • Sets next to NULL (updated during insertion).
    • Returns the newly created node.
• Insert at a Specific Position
  • The insertAtPosition function handles various insertion cases:
    • Empty List:
      • Only position 1 is valid. Creates a new node pointing to itself.
    • Non-Empty List:
      • For position 1, updates the last node to point to the new first node.
      • For other positions, traverses the list to find the correct insertion point:
        • Updates the next pointers to insert the new node.
        • If the new node is added at the end, updates the last pointer.
• Print the Circular Linked List
  • The printList function:
    • Handles an empty list scenario with a message.
    • Traverses and prints the list starting from the first node (last->next).
    • Stops when the traversal loops back to the starting node.
• Main Function
  • Demonstrates the functionality:
    • Creates a circular linked list with initial values 2, 3, and 4.
    • Prints the original list.
    • Inserts a new node (5) at position 2 using insertAtPosition.
    • Prints the list after the insertion to verify the operation.

Expected Output

Original list: 2 3 4 
List after insertions: 2 5 3 4

This output confirms:

• The original circular linked list (2 -> 3 -> 4) was created successfully.
• The new node with value 5 was correctly inserted at position 2.

2. Deletion in the Circular Linked Lists

Deletion involves removing a node while preserving the circular nature of the list.

(a.) Deleting the First Node in the Circular Linked List

Key Points:

• Update the last node’s next pointer to skip the current head.
• Free the memory of the head node.

To delete the first node of a circular linked list, the process begins with checking if the list is empty. In such cases, a message is displayed indicating the emptiness of the list, and the function returns NULL without making any changes. If the list contains only one node, identified when the head and the last pointer refer to the same node, the single node is removed by freeing its allocated memory, and the last pointer is set to NULL, effectively making the list empty.

For lists with multiple nodes, the deletion is handled by adjusting the last->next pointer to bypass the current head node, effectively detaching it from the list structure. After updating the pointer, the memory allocated for the removed head node is freed to ensure no memory leaks occur.

The function concludes by returning the updated last pointer, which still points to the last node in the modified circular linked list, preserving its circular nature.

Implementation of Code in C programming Language

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

// Define the structure of a node
struct Node {
    int data;            // Data stored in the node
    struct Node* next;   // Pointer to the next node in the circular linked list
};

// Function to delete the first node in the circular linked list
struct Node* deleteFirstNode(struct Node* last) {
    // Case 1: If the list is empty
    if (last == NULL) {
        printf("List is empty\n");
        return NULL;
    }

    // Case 2: If the list has only one node
    struct Node* head = last->next; // The first node (head)
    if (head == last) {
        free(head);     // Deallocate memory for the single node
        return NULL;    // The list becomes empty
    }

    // Case 3: If the list has more than one node
    last->next = head->next; // Update the last node to point to the new first node
    free(head);              // Deallocate memory for the old first node

    return last; // Return the updated last node
}

// Function to print the circular linked list
void printList(struct Node* last) {
    // If the list is empty
    if (last == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct Node* head = last->next; // Start from the first node
    do {
        printf("%d ", head->data);  // Print the data of the current node
        head = head->next;         // Move to the next node
    } while (head != last->next);  // Stop when we loop back to the starting node

    printf("\n");
}

// Function to create a new node with the given value
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory
    newNode->data = value;  // Set the data
    newNode->next = NULL;   // Initialize the next pointer to NULL
    return newNode;         // Return the new node
}

// Main function
int main() {
    // Step 1: Create a circular linked list with nodes 2, 3, and 4
    struct Node* first = createNode(2);         // Create the first node with value 2
    first->next = createNode(3);                // Create the second node with value 3
    first->next->next = createNode(4);          // Create the third node with value 4
    struct Node* last = first->next->next;      // Set the last pointer to the third node
    last->next = first;                         // Complete the circular link

    // Step 2: Print the original list
    printf("Original list: ");
    printList(last);

    // Step 3: Delete the first node from the list
    last = deleteFirstNode(last);

    // Step 4: Print the list after deletion
    printf("List after deleting first node: ");
    printList(last);

    return 0;
}

Step-by–Step Explanation

• Define the Node Structure
  • Each node has two fields:
    • data: Stores the integer value of the node.
    • next: Points to the next node in the circular linked list.
• Delete the First Node
  • The deleteFirstNode function handles three cases:
    • Empty List:
      • If the list is empty (last == NULL), a message is printed, and the function returns NULL.
    • Single Node:
      • If the list has only one node (last == last->next), that node is freed, and the list becomes empty.
    • Multiple Nodes:
      • Updates the next pointer of the last node to point to the second node.
      • Frees the memory allocated for the first node.
• Print the Circular Linked List
  • The printList function:
    • If the list is empty, prints “List is empty.”
    • Otherwise, starts from the first node and traverses the list in a circular manner until it loops back to the starting node.
• Create Nodes
  • The createNode function:
    • Allocates memory for a new node.
    • Initializes its data with the given value and sets its next to NULL.
• Main Function
  • Demonstrates the functionality:
    • Step 1: Creates a circular linked list with three nodes (2 -> 3 -> 4).
    • Step 2: Prints the original list.
    • Step 3: Deletes the first node using deleteFirstNode.
    • Step 4: Prints the list after the deletion.

Expected Output

Original list: 2 3 4 
List after deleting first node: 3 4 

Explanation of the Output

• The original circular linked list (2 -> 3 -> 4) is displayed correctly.
• After deleting the first node, the list becomes (3 -> 4) with 3 as the new head. The circular structure is maintained.

(b.) Deleting a Specific Node in the Circular Linked List

Key Points:

• Traverse the list to locate the target node and its predecessor.
• Adjust the predecessor’s next pointer to bypass the target node.
• Free the memory of the target node.

To delete a specific node from a circular linked list, the first step is to verify if the list is empty. If the list is empty, a message is printed, and the function returns nullptr to indicate that there are no nodes to delete. In the case where the list contains only one node, if that node matches the key we want to delete, we free the node’s memory and update the last pointer to nullptr, making the list empty.

If the node to be deleted is the first node (the head node), we update the next pointer of the last node to bypass the head and point to the second node in the list. After this adjustment, the head node is deleted, effectively removing it from the list.

For deleting other nodes, we traverse the list using two pointers: curr (which is used to find the node to be deleted) and prev (which keeps track of the previous node). When the node with the matching key is found, we modify the next pointer of the prev node to point to the node following curr, effectively removing curr from the list. If the deleted node is the last node, we also update the last pointer to point to prev.

If the node is not found, no changes are made, and the last pointer remains unchanged. In the end, the updated last pointer is returned to maintain the integrity of the circular structure of the list.

Implementation of Code in C Programming Language

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

// Define the structure for a node in the circular linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to delete a specific node in the circular linked list
struct Node* deleteSpecificNode(struct Node* last, int key) {
    if (last == NULL) {
        // If the list is empty
        printf("List is empty, nothing to delete.\n");
        return NULL;
    }

    struct Node* curr = last->next;  // Set curr to point to the first node (head)
    struct Node* prev = last;        // Set prev to point to the last node initially

    // Case 1: If the list has only one node and it matches the key
    if (curr == last && curr->data == key) {
        free(curr);  // Free the only node
        last = NULL;  // Set last to NULL since the list is empty now
        return last;
    }

    // Case 2: If the node to be deleted is the first node (head node)
    if (curr->data == key) {
        last->next = curr->next;  // Update the last node's next to the second node
        free(curr);  // Free the head node
        return last;
    }

    // Case 3: Traverse the list to find the node to be deleted
    while (curr != last && curr->data != key) {
        prev = curr;
        curr = curr->next;
    }

    // Case 4: If the node to be deleted is found
    if (curr->data == key) {
        prev->next = curr->next;  // Skip the node by linking prev to curr->next
        if (curr == last) {
            last = prev;  // If the last node was deleted, update last pointer
        }
        free(curr);  // Free the node
    } else {
        // Case 5: If the node to be deleted is not found
        printf("Node with data %d not found.\n", key);
    }

    return last;  // Return the updated last pointer
}

// Function to print the circular linked list
void printList(struct Node* last) {
    if (last == NULL) {
        printf("List is Empty\n");
        return;
    }

    struct Node* head = last->next;  // Start from the head node
    while (1) {
        printf("%d ", head->data);  // Print the data of the current node
        head = head->next;  // Move to the next node
        if (head == last->next) break;  // If we have looped back to the head, stop
    }
    printf("\n");
}

// Function to create a new node with a given value
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  // Allocate memory for the node
    newNode->data = value;  // Set the data of the new node
    newNode->next = NULL;  // Set next pointer to NULL
    return newNode;  // Return the newly created node
}

int main() {
    // Create a circular linked list with nodes: 2 -> 3 -> 4
    struct Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);

    struct Node* last = first->next->next;  // Set last to the last node (4)
    last->next = first;  // Make the list circular by linking last node to first

    // Print the original list
    printf("Original list: ");
    printList(last);

    // Delete a specific node (node with value 3)
    int key = 3;
    last = deleteSpecificNode(last, key);

    // Print the list after deleting the node
    printf("List after deleting node %d: ", key);
    printList(last);

    return 0;
}

Step-By-Step Code Explanation

• Node Structure (struct Node):
  • A Node structure is defined with an integer data field (data) and a pointer to the next node (next). This structure is used to represent each node in the circular linked list.
• deleteSpecificNode Function:
  • This function is responsible for deleting a node with the given key from the circular linked list.
  • Step 1: If the list is empty (last == NULL), a message is printed, and the function returns NULL.
  • Step 2: If the list has only one node and that node matches the key, the node is freed, and last is set to NULL to indicate that the list is now empty.
  • Step 3: If the node to delete is the head (the first node in the list), we update the next pointer of the last node to skip the head node and point to the second node. The head node is then freed.
  • Step 4: If the node to delete is found while traversing the list, the next pointer of the previous node is updated to skip the current node (the one to be deleted). If the node to be deleted is the last node, we update the last pointer to point to the previous node.
  • Step 5: If the node is not found in the list, a message is printed, and the list remains unchanged.
• printList Function:
  • This function is used to print the elements of the circular linked list.
  • It starts from the head node (last->next) and traverses the list, printing the data of each node.
  • The loop stops when we reach the head node again, indicating that we have traversed the entire circular list.
• createNode Function:
  • This function creates a new node with a given value. The node’s data is set to the provided value, and the next pointer is initialized to NULL.
• main Function:
  • A circular linked list is created with nodes containing values 2, 3, and 4.
  • The last node (last->next) is set to point to the first node to make the list circular.
  • The list is printed before and after deleting the node with the value 3.

Output

Original list: 2 3 4 
List after deleting node 3: 2 4

This code successfully creates a circular linked list, deletes a specific node, and then prints the list before and after the deletion.

(c.) Deleting the Last Node in the Circular Linked List

Key Points:

• Traverse to the second-to-last node.
• Update its next pointer to point to the head.
• Free the memory of the last node.

To delete the last node in a circular linked list, we first check whether the list is empty. If the list is empty (last == NULL), we print a message and return nullptr. If the list contains only one node, where the head is the same as the last, we delete that node and set last to nullptr to indicate an empty list.

For lists with multiple nodes, we need to locate the second last node. We begin by starting from the head and traverse the list until we find the node whose next pointer points to the last node. Once found, we update the next pointer of the second last node to point to the head, effectively removing the last node from the circular list. After that, we delete the last node and return the updated last pointer, which now points to the new last node in the list.

Implementation of Code in C programming Language

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

// Define the structure for a node in the circular linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to delete the last node in the circular linked list
struct Node* deleteLastNode(struct Node* last) {
    if (last == NULL) {
        // If the list is empty, print a message and return NULL
        printf("List is empty, nothing to delete.\n");
        return NULL;
    }
    
    struct Node* head = last->next;

    // If there is only one node in the list
    if (head == last) {
        free(last);
        last = NULL;  // The list becomes empty
        return last;
    }
    
    // Traverse the list to find the second last node
    struct Node* curr = head;
    while (curr->next != last) {
        curr = curr->next;
    }
    
    // Update the second last node's next pointer to point to the head
    curr->next = head;
    
    // Free the memory occupied by the last node
    free(last);
    
    // Update the last pointer to point to the second last node
    last = curr;

    return last;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    if (last == NULL) {
        // If the list is empty, return
        printf("List is Empty\n");
        return;
    }

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

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

int main() {
    // Create a circular linked list: 2 -> 3 -> 4 -> 2
    struct Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);
    
    struct Node* last = first->next->next;
    last->next = first;  // Circular link: last node points to first

    printf("Original list: ");
    printList(last);

    // Delete the last node
    last = deleteLastNode(last);

    printf("List after deleting last node: ");
    printList(last);

    return 0;
}

Output:

Original list: 2 3 4 
List after deleting last node: 2 3 

Explanation of the Code:

• Struct Definition:
  • The struct Node defines the structure of a node in the circular linked list, containing an integer data and a pointer next to the next node.
• createNode Function:
  • This function takes an integer value as input, creates a new node, assigns the value to data, and sets the next pointer to NULL.
• deleteLastNode Function:
  • This function is responsible for deleting the last node in the circular linked list:
    • It first checks if the list is empty (last == NULL). If empty, it prints a message and returns NULL.
    • If the list contains only one node (i.e., the head is the same as the last node), it frees the memory of that node and sets last to NULL, effectively making the list empty.
    • If there are multiple nodes, it traverses the list to find the second last node (i.e., the node whose next pointer points to the last node).
    • Once the second last node is found, its next pointer is updated to point back to the head, removing the last node from the circular list.
    • The last node is then deleted (free(last)), and the last pointer is updated to point to the second last node.
• printList Function:
  • This function prints all the nodes in the circular linked list:
    • If the list is empty (last == NULL), it prints “List is Empty”.
    • It starts from the head (i.e., last->next) and prints the data of each node until it loops back to the head.
• main Function:
  • This function demonstrates the creation of a circular linked list and performs the operation of deleting the last node:
    • It first creates a list with values 2 -> 3 -> 4 and links the last node back to the first node to form a circular list.
    • It prints the original list using printList.
    • It then deletes the last node using deleteLastNode and prints the updated list.

Summary:

• The code successfully creates a circular linked list, deletes the last node, and prints the updated list.
• It handles edge cases such as an empty list and a list with only one node.

3. Searching

To search for a specific value:

• Start from any node and traverse the list.
• Check each node’s data value.
• If the value matches, return the node; otherwise, continue until you return to the starting node.

To search for a specific value in a circular linked list, we first verify if the list is empty. If it is, we return false, indicating that no nodes exist to search. If the list contains nodes, we begin the search from the head node (which can be accessed using last->next). We use a pointer curr to traverse through each node in the list, starting from the head and continuing until we loop back to the head, ensuring we check all nodes in the circular structure.

During the traversal, if we find a node where the data matches the given key, we immediately return true, signaling that the value has been found. After completing the loop and checking every node, we also check the last node explicitly to ensure no node is missed. If the entire list has been traversed and no match is found, we return false, indicating that the key is not present in the list.

Implementation of Code in C Programming Language

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

// Definition of the Node structure
struct Node{
    int data;
    struct Node *next;
};

// Function to search for a specific value in the circular linked list
int search(struct Node *last, int key){
    if (last == NULL){
        // If the list is empty
        return 0;
    }

    struct Node *head = last->next;
    struct Node *curr = head;

    // Traverse the list to find the key
    while (curr != last){
        if (curr->data == key){
            // Key found
            return 1;
        }
        curr = curr->next;
    }

    // Check the last node
    if (last->data == key){
        // Key found
        return 1;
    }
    // Key not found
    return 0;
}

// Function to print the circular linked list
void printList(struct Node *last){
    if (last == NULL) return;

    struct Node *head = last->next;
    while (1){
        printf("%d ", head->data);
        head = head->next;
        if (head == last->next)
            break;
    }
    printf("\n");
}

// Function to create a new node
struct Node *createNode(int value){
    struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
    temp->data = value;
    temp->next = NULL;
    return temp;
}

int main(){
    // Create circular linked list: 2, 3, 4
    struct Node *first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);

    struct Node *last = first->next->next;
    last->next = first;

    printf("Original list: ");
    printList(last);

    // Search for a specific value
    int key = 3;
    int found = search(last, key);
    if (found){
        printf("Value %d found in the list.\n", key);
    }
    else{
        printf("Value %d not found in the list.\n", key);
    }

    return 0;
}

Output:

Original list: 2 3 4 
Value 3 found in the list.

Step-by-Step Code Explanation

• Node Structure Definition:
  • We define a structure Node to represent a node in the circular linked list. Each node has an integer data field (data) and a pointer (next) to the next node in the list.
• search() Function:
  • The function search() accepts the last node of the list and a key (value to search for).
  • If the list is empty (last == NULL), it returns 0, indicating that the key cannot be found.
  • It starts from the head node (which is last->next) and traverses the list using the pointer curr.
  • During traversal, if it finds a node whose data matches the key, it returns 1, indicating the value was found.
  • Once it reaches the last node, it also checks if the last node’s data matches the key.
  • If the key is found, it returns 1; otherwise, after completing the traversal, it returns 0 to indicate the key wasn’t found.
• printList() Function:
  • This function prints the entire circular linked list.
  • It starts from the head node (last->next) and iterates through the list, printing each node’s data.
  • The loop terminates when it reaches back to the head node, ensuring that all nodes are printed exactly once.
• createNode() Function:
  • A helper function that creates a new node with a specified value. It allocates memory for the node, sets its data field to the given value, and initializes the next pointer to NULL.
• main() Function:
  • In main(), we create a circular linked list by manually linking three nodes (values 2, 3, and 4).
  • After the list is created, the last node’s next pointer is linked to the first node to complete the circular structure.
  • The original list is printed using printList().
  • We then search for the value 3 using the search() function and print whether the value was found or not.

This approach efficiently handles searching for a value in a circular linked list, ensuring that the entire list is traversed and the key is properly checked.

Advantages of Circular Linked Lists

• Continuous Navigation: No null terminators, enabling uninterrupted traversal.
• Efficient for Cyclic Processes: Ideal for queues, round-robin scheduling, and buffers.
• Flexibility in Operations: Supports dynamic insertion and deletion with minimal overhead.

Disadvantages of Circular Linked Lists

• Complex Traversal: Requires careful handling to avoid infinite loops.
• Increased Complexity: Slightly more complex to implement than regular linked lists.
• Difficulty in Debugging: Identifying errors can be challenging due to the absence of NULL endpoints.

Applications of Circular Linked Lists

• Operating Systems: For round-robin scheduling in multitasking environments.
• Media Players: Managing playlists with seamless forward and backward navigation.
• Data Buffers: Implementing buffers for data streams or real-time applications.
• Gaming: Storing player turns in multi-player games.

By understanding and mastering circular linked lists, programmers unlock a robust toolset for crafting efficient and dynamic solutions to a wide range of problems in computer science. This versatile data structure, with its unique characteristics, remains a cornerstone in algorithm design and software development.

Frequently Asked Questions (FAQs) on Circular Linked Lists

What is a Circular Linked List, and how does it differ from a regular linked list?

A Circular Linked List is a specialized form of a linked list where the last node connects back to the first node, forming a continuous loop. This connection eliminates the presence of a NULL pointer at the end, a key feature in regular linked lists.

• In a Singly Linked List, traversal stops when the next pointer of the last node is NULL.
• In a Circular Linked List, you can traverse infinitely because the last node’s next pointer points to the head.

This makes Circular Linked Lists ideal for applications requiring cyclic traversal or continuous processes, like task scheduling or media playlists.

What are the types of Circular Linked Lists, and what are their differences?

There are two primary types of Circular Linked Lists:

(a.) Circular Singly Linked List

• Each node has one pointer: the next pointer, which points to the next node.
• The last node’s next pointer connects back to the first node, enabling unidirectional traversal.
• It is simple and lightweight, commonly used in scenarios requiring straightforward cyclic navigation.

(b.) Circular Doubly Linked List

• Each node contains two pointers: next (to the next node) and prev (to the previous node).
• The last node’s next pointer connects to the first node, and the first node’s prev pointer connects to the last node, enabling bidirectional traversal.
• More versatile but slightly more complex, making it suitable for tasks like media players or undo/redo operations.

How can you represent a Circular Linked List in a program?

A Circular Linked List is typically represented using a struct or class in programming. Here is an example in C:

struct Node {
    int data;           // Data in the node
    struct Node *next;  // Pointer to the next node
};

// Function to create a new node
struct Node *createNode(int value) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

In this structure:

• data stores the node’s value.
• next is the pointer to the next node.
• The circular connection is created by setting the next pointer of the last node to the first node.

What are the key advantages of Circular Linked Lists over regular linked lists?

Circular Linked Lists offer several advantages:

• Continuous Traversal: You can traverse the list indefinitely without encountering a NULL pointer.
• Efficient Cyclic Processes: Perfect for applications like round-robin scheduling and buffer management.
• Dynamic and Flexible: Nodes can be inserted or deleted dynamically with ease, making it ideal for tasks with variable data sizes.
• Constant-Time Insertions at Both Ends: With a pointer to the last node, insertions at the beginning or end take constant time.

How do you insert a new node in a Circular Linked List?

Insertion in a Circular Linked List can occur in four ways:

• (a.) Insertion in an Empty List
  • Create a new node.
  • Set its next pointer to point to itself.
  • Update the pointer to reference this node as the last node.
• (b.) Insertion at the Beginning
  • Create a new node.
  • Set its next pointer to the current head (last->next).
  • Update the last node’s next pointer to point to the new node.
• (c.) Insertion at the End
  • Create a new node.
  • Set its next pointer to the head.
  • Update the last node’s next pointer to the new node.
  • Update the last pointer to the new node.
• (d.) Insertion at a Specific Position
  • Traverse to the desired position.
  • Adjust pointers to insert the new node between nodes.
  • Maintain the circular structure by ensuring connections to the first and last nodes are preserved.

What are the steps to delete a node in a Circular Linked List?

Deletion can occur at various points in the list:

• (a.) Deleting the First Node
  • Update the last node’s next pointer to bypass the current head.
  • Free the memory occupied by the head node.
• (b.) Deleting the Last Node
  • Traverse to the second-to-last node.
  • Update its next pointer to point to the head.
  • Free the memory of the last node.
• (c.) Deleting a Specific Node
  • Locate the target node and its predecessor.
  • Update the predecessor’s next pointer to skip the target node.
  • Free the memory of the target node.

How does searching work in a Circular Linked List?

Searching in a Circular Linked List involves traversing the list while ensuring the circular structure is respected. Steps include:

• Check if the list is empty. If yes, return false.
• Start from the head node (last->next).
• Traverse nodes using a pointer and compare each node’s data to the target value.
• Stop if the value is found or if traversal returns to the starting node.
• Return true if the value is found; otherwise, return false.

Why is a pointer to the last node preferred over the first node?

Using a pointer to the last node instead of the head offers key advantages:

• Constant-Time Insertions: Inserting at the beginning or end does not require full traversal, as the last node directly points to the first node.
• Simplified Operations: Traversing or manipulating nodes becomes more efficient when the last pointer is readily accessible.

This optimization significantly reduces the time complexity for insertion and deletion operations.

What are some real-world applications of Circular Linked Lists?

Circular Linked Lists are highly versatile and find applications in numerous areas:

• Operating Systems: Used in round-robin scheduling to ensure equitable CPU time for processes.
• Media Players: Enables seamless playback of playlists, both forward and backward.
• Gaming: Stores player turns in multi-player games, cycling through them continuously.
• Data Buffers: Useful in implementing buffers for real-time data streaming.

What are the limitations of Circular Linked Lists?

Despite their advantages, Circular Linked Lists have some drawbacks:

• Complex Traversal: Extra care is needed to avoid infinite loops due to the absence of a NULL terminator.
• Increased Debugging Efforts: Identifying issues in a circular structure can be challenging.
• Memory Overhead: In the case of Circular Doubly Linked Lists, the additional prev pointer increases memory usage.

Understanding these limitations is crucial for effectively implementing Circular Linked Lists in real-world applications.