Circular Singly Linked List

A Circular Singly Linked List is a special type of linked list in which the last node points back to the first node instead of pointing to NULL.

In a normal singly linked list, traversal ends when the next pointer becomes NULL. However, in a circular singly linked list, the nodes form a continuous loop.

This structure is useful in applications where repeated traversal is required.

Structure of Circular Singly Linked List

Each node in a circular singly linked list contains:

• Data Field – Stores the actual value.
• Next Pointer – Stores the address of the next node.

The difference is that the last node connects again to the first node.

Example:

---------─────────────────────┐
|        ↓                    |
[10] → [20] → [30] → [40] ────┘

Here:

• 10 is the first node.
• 40 is the last node.
• The last node points back to 10.

Memory Representation

Nodes are stored at different memory locations.

Example:

Address    Data    Next
1000        10     2000
2000        20     3000
3000        30     4000
4000        40     1000

The last node stores the address of the first node.

Features of Circular Singly Linked List

• The last node does not contain NULL.
• Traversal can begin from any node.
• Nodes form a circular structure.
• Efficient for cyclic operations.

Traversal in Circular Singly Linked List

Traversal in CSLL is different because the list has no NULL ending.

Steps for Traversal

1. Start from the head node.
2. Print the current node.
3. Move to the next node.
4. Stop when the traversal reaches the head node again.

Example

        ┌──────────────┐
        ↓              │
HEAD → [10] → [20] → [30]

Traversal order: 10 → 20 → 30

Insertion Operations

1. Insert at Beginning

A new node is added before the current head.

Steps

1. Create a new node.
2. Set its next pointer to the current head.
3. Traverse to the last node.
4. Update the last node's next pointer to the new node.
5. Move head to the new node.

Example

Before insertion: 

[20] → [30] → back to [20]

Insert 10

After insertion:

[10] → [20] → [30] → back to [10]

2. Insert at End

A new node is inserted after the last node.

Steps

1. Create a new node.
2. Traverse to the last node.
3. Connect the last node to the new node.
4. Set the new node's next pointer to the head.

Example

Before insertion:

[10] → [20] → back to [10]

Insert 30

After insertion:

[10] → [20] → [30] → back to [10]

3. Insert at Specific Position

A node can also be inserted between two nodes.

Example

Before insertion:

[10] → [30] → back to [10]

Insert 20 at position 2.

After insertion:

[10] → [20] → [30] → back to [10]

Deletion Operations

1. Delete from Beginning

The first node is removed and the second node becomes the new head.

Example

Before deletion:

[10] → [20] → [30] → back to [10]

After deletion:

[20] → [30] → back to [20]

2. Delete from End

The last node is removed from the list.

Example

Before deletion:

[10] → [20] → [30] → back to [10]

After deletion:

[10] → [20] → back to [10]

3. Delete from Specific Position

A node located at a particular position can be removed.

Example

Before deletion:

[10] → [20] → [30] → back to [10]

Delete 20

After deletion:

[10] → [30] → back to [10]

Searching

Searching means finding a node containing a specific value.

Steps

1. Start from the head node.
2. Compare each node value with the target value.
3. Continue traversal until the head node is reached again.
4. If found, return the position.

Example

[10] → [20] → [30] → back to [10]

Search 30

Result: Found at position 3

Advantages of Circular Singly Linked List

1. Continuous Traversal

Traversal can continue repeatedly without restarting from the head.

2. Efficient for Circular Processes

Useful in applications that run in cycles.

3. Easy Implementation of Queue

Queues can be implemented efficiently using circular linked lists.

4. Better Memory Utilization

No memory is wasted for storing NULL in the last node.

Disadvantages of Circular Singly Linked List

1. Complex Traversal

Special care is needed to avoid infinite loops.

2. Difficult Debugging

Circular connections can make debugging harder.

3. No Backward Traversal

Traversal is possible only in the forward direction.

Applications of Circular Singly Linked List

Circular singly linked lists are commonly used in:

• Round-robin CPU scheduling
• Music playlist systems
• Multiplayer games
• Circular queues
• Time-sharing systems
• Repeated task scheduling

Time Complexity

If a tail pointer is maintained, insertion at the beginning and end can become more efficient.

Space Complexity

Each node contains:

• Data field
• One pointer (next)

For n nodes, the total space complexity is: O(n)

C Program for Circular Singly Linked List

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

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

struct Node* head = NULL;

void insertAtEnd(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;

    if(head == NULL) {
        head = newNode;
        newNode->next = head;
        return;
    }

    struct Node* temp = head;

    while(temp->next != head) {
        temp = temp->next;
    }

    temp->next = newNode;
    newNode->next = head;
}

void display() {
    if(head == NULL)
        return;

    struct Node* temp = head;

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

int main() {
    insertAtEnd(10);
    insertAtEnd(20);
    insertAtEnd(30);

    display();

    return 0;
}

Difference Between Singly Linked List and Circular Singly Linked List

Conclusion

A Circular Singly Linked List is an advanced form of linked list where the last node connects back to the first node. This circular connection makes it highly useful for repetitive and cyclic operations. Although traversal requires careful handling to avoid infinite loops, CSLL provides efficient solutions for scheduling systems, queues, and continuous processing applications.