A Beginner’s Guide to Circular Linked Lists in C

Table of Contents

1. What are Circular Linked Lists?
2. Basic Structure of a Circular Linked List in C
3. Creating a Circular Linked List
4. Traversing a Circular Linked List
5. Inserting a Node in a Circular Linked List
6. Deleting a Node from a Circular Linked List
7. Common Practices and Best Practices
8. Conclusion
9. References

What are Circular Linked Lists?

A circular linked list is a collection of nodes where each node contains data and a pointer to the next node. In a circular linked list, the last node’s pointer does not point to NULL as in a regular linked list. Instead, it points back to the first node of the list, creating a closed loop. This circular nature allows for continuous traversal of the list, which can be useful in applications such as scheduling algorithms, gaming, and multimedia systems.

Basic Structure of a Circular Linked List in C

In C, we can represent a circular linked list using a structure for the nodes. Here is the basic structure of a node in a circular linked list:

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

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

In this code, we define a Node structure that contains an integer data to store the actual value and a pointer next that points to the next node in the list.

Creating a Circular Linked List

To create a circular linked list, we first need to create individual nodes and then link them together in a circular fashion. Here is an example of creating a circular linked list with three nodes:

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

// Function to create a circular linked list
Node* createCircularList() {
    Node* head = createNode(1);
    Node* second = createNode(2);
    Node* third = createNode(3);

    head->next = second;
    second->next = third;
    third->next = head; // Make it circular

    return head;
}

In this code, the createNode function is used to allocate memory for a new node and initialize its data. The createCircularList function creates three nodes and links them together, with the last node pointing back to the first node to form a circular list.

Traversing a Circular Linked List

Traversing a circular linked list is similar to traversing a regular linked list, but we need to be careful not to get stuck in an infinite loop. We can use a temporary pointer to traverse the list until we reach the starting point again.

// Function to traverse a circular linked list
void traverseCircularList(Node* head) {
    if (head == NULL) return;

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

In this code, we use a do - while loop to traverse the list. The loop continues until we reach the starting node again.

Inserting a Node in a Circular Linked List

There are different ways to insert a node in a circular linked list, such as inserting at the beginning, end, or in the middle. Here is an example of inserting a node at the beginning of the list:

// Function to insert a node at the beginning of the circular linked list
Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = createNode(data);
    if (head == NULL) {
        newNode->next = newNode;
        return newNode;
    }

    Node* temp = head;
    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = head;
    return newNode;
}

In this code, we first create a new node. If the list is empty, the new node points to itself. Otherwise, we find the last node, make it point to the new node, and the new node points to the original head.

Deleting a Node from a Circular Linked List

Deleting a node from a circular linked list also requires special handling. Here is an example of deleting a node with a given key:

// Function to delete a node with a given key from the circular linked list
Node* deleteNode(Node* head, int key) {
    if (head == NULL) return NULL;

    Node* current = head;
    Node* prev;

    // If the head node is to be deleted
    if (current->data == key) {
        if (current->next == current) {
            free(current);
            return NULL;
        }
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = current->next;
        free(current);
        head = temp->next;
        return head;
    }

    do {
        prev = current;
        current = current->next;
        if (current->data == key) {
            prev->next = current->next;
            free(current);
            return head;
        }
    } while (current != head);

    return head;
}

In this code, we handle different cases such as deleting the head node and deleting a non - head node.

Common Practices and Best Practices

• Memory Management: Always free the memory allocated for nodes when they are no longer needed to avoid memory leaks. Use the free function in C.
• Error Handling: Check for NULL pointers before performing operations on them to avoid segmentation faults.
• Code Readability: Use meaningful variable names and add comments to your code to make it easier to understand and maintain.

Conclusion

Circular linked lists are a powerful and versatile data structure in C. They offer unique advantages such as continuous traversal and can be used in a variety of applications. By understanding the fundamental concepts, basic operations, and best practices associated with circular linked lists, you can effectively use them in your C programs.

References

• “Data Structures and Algorithms in C” by Adam Drozdek
• GeeksforGeeks: https://www.geeksforgeeks.org/circular-linked-list/
• TutorialsPoint: https://www.tutorialspoint.com/data_structures_algorithms/circular_linked_list_algorithm.htm