Introduction to Circular Linked Lists in C

A Circular Linked List is a variation of a linked list where the last node points back to the first node, creating a circular structure. This data structure is often used in applications like real-time scheduling, buffer management, and more.

In this blog, we’ll walk through the implementation of a Circular Linked List in C, including insertion and traversal of nodes.

What is a Circular Linked List?

A Circular Linked List has the following characteristics:

• The last node of the list points back to the first node, forming a circular connection.

• Unlike singly linked lists, circular linked lists have no NULL pointer at the end.

Advantages of circular linked lists include:

• Efficient traversal from any node.

• Useful in implementing circular buffers, scheduling algorithms, etc.

Code Walkthrough

Below is the implementation of a Circular Linked List in C. It demonstrates how to:

• Insert nodes at the end.

• Traverse and print the list.

1. Node Structure

    typedef struct Node Node;
    struct Node {
        int data;
        Node* next;
    };
   

   Explanation:

   • Each node contains:

     • data: The value stored in the node.

     • next: A pointer to the next node in the list.

2. Appending Nodes

    Node* append(Node* head, int data) {
        Node *node = (struct Node*)malloc(sizeof(struct Node*));
        node->data = data;
        if (head == NULL) {
            node->next = node;
            head = node;
            return head;
        }
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = node;
        node->next = head;
        return head;
    }
   

   Explanation:

   • Creating a New Node:

     • Allocate memory for a new node and set its data field.

   • Empty List:

     • If the list is empty (head == NULL), the new node points to itself, forming a single-node circular list.

   • Appending at the End:

     • Traverse the list to the last node and update its next pointer to point to the new node.

     • Set the next pointer of the new node to the head.

3. Printing the List

    void print(Node* head) {
        if (head == NULL) {
            return;
        }
        Node* temp = head;
        while (temp->next != head) {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        printf("%d ", temp->data);
    }
   

   Explanation:

   • Check for Empty List:

     • If the list is empty, exit the function.

   • Traverse and Print:

     • Start at the head and traverse the list until the next pointer points back to the head.

     • Print the data of each node.

4. Main Function

    int main() {
        Node *head = NULL;
        int n;
        scanf("%d", &n);
        while (n--) {
            int t;
            scanf("%d", &t);
            head = append(head, t);
        }
        print(head);
        return 0;
    }
   

   Steps:

   1. Input the Number of Nodes:

      • Read the number of elements (n) to be added to the list.

   2. Add Nodes:

      • Use the append function to insert each value into the list.

   3. Print the List:

      • Call the print function to display the elements in the list.

Example Input and Output

Input:

5
10 20 30 40 50

Output:

10 20 30 40 50

Explanation:

1. Create a circular linked list with the elements 10, 20, 30, 40, and 50.

2. Traverse the list starting from the head and print each node’s data.

Advantages of Circular Linked Lists

1. Traversal from Any Node:

   • You can start traversal from any node, not just the head.

2. Efficient Use of Memory:

   • No NULL pointers at the end of the list.

3. Cyclic Operations:

   • Useful in round-robin scheduling, buffers, and multiplayer gaming.

Extending the Implementation

You can enhance this implementation by adding features like:

• Insertion at Specific Positions: Add nodes at arbitrary positions in the list.

• Deletion of Nodes: Remove nodes by value or position.

• Search Operation: Search for specific values in the list.

Conclusion

Circular Linked Lists provide an efficient way to manage data in applications that require continuous traversal. By mastering their implementation, you can handle cyclic data structures and algorithms effectively.

Understanding the fundamentals of linked lists is crucial for software developers. So, start practicing and extend this implementation to solve more complex problems.

Happy coding! 😊

References

1. Find the code for the above explanation here.