Introduction to Circular Linked Lists

In our journey through data structures with C, we've explored various forms of linked lists. Today, we delve into a fascinating variant: the Circular Linked List. Unlike singly or doubly linked lists, where the last node points to NULL, a circular linked list forms a continuous loop where the last node points back to the first node.

This simple modification opens up a world of possibilities, making certain operations more efficient and providing unique advantages in specific scenarios. This post will guide you through understanding, defining, and implementing the core operations of a circular linked list in C.

Understanding the Node Structure

Just like other linked lists, the fundamental building block of a circular linked list is a node. Each node typically contains two parts:

1. Data Part: Stores the actual value or information.
2. Next Pointer: Stores the address of the next node in the sequence.

The key difference is how these nodes are connected. Instead of a NULL terminator, the next pointer of the last node points to the first node, completing the circle. Often, we maintain a pointer to the last node (let's call it tail), because from the tail, we can easily access the first node (tail->next) and perform insertions/deletions at both ends efficiently.

Key Operations and C Implementation

1. Node Definition

First, let's define the structure for our nodes. We'll use a simple integer data type for demonstration.

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

// Define the structure for a node
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// Global pointer to the tail of the circular linked list
// A tail pointer allows easy access to both head (tail->next) and tail.
Node *tail = NULL;

2. Initializing a Circular Linked List

An empty circular linked list is represented by a NULL tail pointer.

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL; // Initially points to null, will be set during insertion
    return newNode;
}

3. Insertion Operations

Inserting at the Beginning (Prepending)

To insert a new node at the beginning, we make the new node's next point to the current head (tail->next), and then make the current tail's next point to the new node. If the list is empty, the new node becomes both head and tail, pointing to itself.

// Function to insert a node at the beginning of the list
void insertAtBeginning(int data) {
    Node* newNode = createNode(data);

    if (tail == NULL) { // List is empty
        tail = newNode;
        tail->next = tail; // Point to itself
    } else {
        newNode->next = tail->next; // New node points to current head
        tail->next = newNode;       // Tail's next points to new node (new head)
    }
    printf("Inserted %d at the beginning.\n", data);
}

Inserting at the End (Appending)

Inserting at the end is similar to the beginning, but we also update the tail pointer. The new node's next points to the current head (tail->next), the current tail's next points to the new node, and finally, the new node becomes the new tail.

// Function to insert a node at the end of the list
void insertAtEnd(int data) {
    Node* newNode = createNode(data);

    if (tail == NULL) { // List is empty
        tail = newNode;
        tail->next = tail; // Point to itself
    } else {
        newNode->next = tail->next; // New node points to current head
        tail->next = newNode;       // Current tail points to new node
        tail = newNode;             // New node becomes the new tail
    }
    printf("Inserted %d at the end.\n", data);
}

Inserting After a Specific Node

To insert a node after a specific data value, we first traverse the list to find the node with the given value. Once found, we insert the new node between the found node and its successor.

// Function to insert a node after a specific value
void insertAfter(int existingData, int newData) {
    if (tail == NULL) {
        printf("List is empty. Cannot insert after %d.\n", existingData);
        return;
    }

    Node* current = tail->next; // Start from head
    Node* newNode = createNode(newData);
    int found = 0;

    do {
        if (current->data == existingData) {
            newNode->next = current->next; // New node points to current's next
            current->next = newNode;       // Current points to new node
            if (current == tail) {         // If we inserted after the tail, new node becomes the new tail
                tail = newNode;
            }
            found = 1;
            printf("Inserted %d after %d.\n", newData, existingData);
            break;
        }
        current = current->next;
    } while (current != tail->next); // Traverse until we come back to head

    if (!found) {
        printf("%d not found in the list. Cannot insert %d after it.\n", existingData, newData);
    }
}

4. Deletion Operations

Deleting from the Beginning

Deleting the head node involves making the tail's next pointer point to the second node. Special care is needed for an empty list or a list with only one node.

// Function to delete a node from the beginning
void deleteFromBeginning() {
    if (tail == NULL) {
        printf("List is empty. Cannot delete from beginning.\n");
        return;
    }

    Node* head = tail->next;
    int data = head->data;

    if (head == tail) { // Only one node in the list
        free(head);
        tail = NULL;
    } else {
        tail->next = head->next; // Tail's next points to the second node
        free(head);
    }
    printf("Deleted %d from the beginning.\n", data);
}

Deleting from the End

To delete the last node (tail), we need to traverse the list to find the node *before* the tail. This node will then become the new tail, and its next pointer will point to the original head.

// Function to delete a node from the end
void deleteFromEnd() {
    if (tail == NULL) {
        printf("List is empty. Cannot delete from end.\n");
        return;
    }

    Node* head = tail->next;
    int data = tail->data;

    if (head == tail) { // Only one node in the list
        free(tail);
        tail = NULL;
    } else {
        Node* current = head;
        while (current->next != tail) { // Find the node before the tail
            current = current->next;
        }
        current->next = head; // Current (new tail) points to head
        free(tail);           // Free the old tail
        tail = current;       // Update tail pointer
    }
    printf("Deleted %d from the end.\n", data);
}

Deleting a Specific Node by Value

Deleting a node with a specific value requires finding the node and its predecessor. Once found, the predecessor's next pointer bypasses the node to be deleted. Special handling is needed if the node to be deleted is the head or the tail.

// Function to delete a node with a specific value
void deleteNode(int value) {
    if (tail == NULL) {
        printf("List is empty. Cannot delete %d.\n", value);
        return;
    }

    Node* current = tail->next; // Start from head
    Node* prev = tail;          // Previous node, initially tail

    int found = 0;

    // Handle single node list
    if (current == tail && current->data == value) {
        free(current);
        tail = NULL;
        printf("Deleted %d from the list.\n", value);
        return;
    }

    // Traverse to find the node and its predecessor
    do {
        if (current->data == value) {
            // Node found
            prev->next = current->next; // Bypass the current node
            if (current == tail) {      // If deleting the tail
                tail = prev;            // Update tail to the previous node
            }
            free(current);
            found = 1;
            printf("Deleted %d from the list.\n", value);
            break;
        }
        prev = current;
        current = current->next;
    } while (current != tail->next); // Traverse until we come back to head

    if (!found) {
        printf("%d not found in the list. Cannot delete.\n", value);
    }
}

5. Traversing the Circular Linked List

Traversal starts from the head (tail->next) and continues until we reach the head again. A do-while loop is perfect for this, as it ensures at least one iteration even if there's only one node.

// Function to traverse and print the circular linked list
void displayList() {
    if (tail == NULL) {
        printf("Circular Linked List is empty.\n");
        return;
    }

    Node* current = tail->next; // Start from the head
    printf("Circular Linked List: ");
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != tail->next); // Loop until we come back to the head
    printf(" (Head)\n");
}

6. Searching in a Circular Linked List

Searching is similar to traversal: iterate through the list until the desired element is found or the entire list has been checked.

// Function to search for an element in the list
int search(int value) {
    if (tail == NULL) {
        return 0; // Not found in empty list
    }

    Node* current = tail->next; // Start from head
    do {
        if (current->data == value) {
            return 1; // Found
        }
        current = current->next;
    } while (current != tail->next);

    return 0; // Not found
}

7. Example `main` function to demonstrate operations

int main() {
    printf("--- Circular Linked List Operations ---\n");

    displayList(); // Empty list

    insertAtEnd(10);
    insertAtBeginning(5);
    insertAtEnd(20);
    insertAtBeginning(2);
    displayList(); // Expected: 2 -> 5 -> 10 -> 20 -> (Head)

    insertAfter(10, 15);
    displayList(); // Expected: 2 -> 5 -> 10 -> 15 -> 20 -> (Head)

    insertAfter(20, 25); // Insert after current tail
    displayList(); // Expected: 2 -> 5 -> 10 -> 15 -> 20 -> 25 -> (Head)

    printf("\nSearching for 15: %s\n", search(15) ? "Found" : "Not Found");
    printf("Searching for 99: %s\n", search(99) ? "Found" : "Not Found");

    deleteFromBeginning();
    displayList(); // Expected: 5 -> 10 -> 15 -> 20 -> 25 -> (Head)

    deleteFromEnd();
    displayList(); // Expected: 5 -> 10 -> 15 -> 20 -> (Head)

    deleteNode(15);
    displayList(); // Expected: 5 -> 10 -> 20 -> (Head)

    deleteNode(5); // Delete head
    displayList(); // Expected: 10 -> 20 -> (Head)

    deleteNode(20); // Delete tail
    displayList(); // Expected: 10 -> (Head)

    deleteNode(10); // Delete last remaining node
    displayList(); // Expected: Circular Linked List is empty.

    deleteFromBeginning(); // Try to delete from empty list
    deleteFromEnd();       // Try to delete from empty list
    deleteNode(100);       // Try to delete from empty list

    return 0;
}

Advantages of Circular Linked Lists

• Continuous Traversal: You can traverse the entire list starting from any node and return to the starting point. This is useful in scenarios like round-robin scheduling.
• Efficient Access: Access to the first and last nodes is highly efficient when a tail pointer is maintained (tail->next for head, tail for tail).
• Implementation of Queues: A circular linked list can implement a queue efficiently, where both enqueue and dequeue operations can be done in O(1) time by maintaining only a tail pointer.
• Multi-processor Scheduling: Used to manage the list of processes waiting to be executed by the CPU.

Disadvantages of Circular Linked Lists

• Complexity in Operations: Operations like insertion and deletion can be slightly more complex than in singly linked lists due to the circular nature and the need to maintain the circular link.
• Infinite Loop Risk: Errors in implementation can easily lead to infinite loops during traversal if the termination condition (returning to the head) is not handled correctly.
• Reverse Traversal: Reverse traversal is not straightforward in a singly linked circular list; it would require either a doubly linked circular list or explicit stack usage.

Common Use Cases

• CPU Scheduling (Round Robin): Processes are kept in a circular queue. The CPU executes each process for a fixed time slice and then moves to the next process in the circle.
• Music/Video Playlists: When the last song/video finishes, the playlist can loop back to the first one.
• Buffer Management: Circular buffers are often implemented using circular linked lists, especially in networking or operating systems.
• Game Development: Managing game turns for multiple players in a cyclic manner.

Conclusion

The circular linked list is a powerful and versatile data structure that offers unique benefits for specific applications where cyclic data flow or continuous iteration is required. By understanding its structure and mastering its core operations, you can effectively leverage its advantages in your C programming endeavors. Remember to always handle edge cases like empty lists and single-node lists to ensure robust implementations.

Keep practicing, and stay tuned for more in our C-Language Series!