Circular Singly Linked List

A Circular Singly Linked List is a variation of the singly linked list where the last node’s next pointer points back to the first node, forming a circular structure.

This allows the list to be traversed infinitely in a loop, and you can start from any node and reach back to it eventually.

Structure Circular Singly Linked List

Each node in a Circular Singly Linked List has.

• Data: The value stored in the node.
• Next: A pointer to the next node.

But unlike a normal singly linked list.

• The last node does not point to NULL, it points to the head of the list.

Characteristics

• Circularity: There’s no NULL at the end. The last node connects back to the first.
• Traversal: You can traverse from any node and eventually return to it.
• No definite end: You must check for the starting node during traversal to stop correctly.
• Single direction: Unlike doubly circular lists, it only goes forward (one pointer per node).

Memory Representation

In the accompanying picture, memory portrayal of a round connected rundown containing signs of an understudy in 4 subjects. Tthe picture shows a brief look at how the round rundown is being put away in the memory.

The beginning or top of the rundown is highlighting the component with the file 1 and containing 13 imprints in the information part and 4 in the following part.

Which implies that it is connected with the hub that is being put away at fourth list of the rundown. Notwithstanding, because of the way that we are thinking about roundabout connected rundown in the memory in this manner the last hub of the rundown contains the location of the primary hub of the rundown.

We can likewise have more than one number of connected rundown in the memory with the distinctive beginning pointers highlighting the diverse beginning hubs in the rundown.

The last hub is distinguished by its next part which contains the location of the beginning hub of the rundown. We should have the option to recognize the last hub of any connected rundown with the goal that we can discover the quantity of cycles which should be performed while navigating the rundown

Operations on Circular Singly Linked List

1. Insertion

Insertion at Beginning

Insert node and make its next point to the current head, then update the last node’s next to the new node.

• Create a new node.
• Make it point to the current head.
• Traverse to the last node and make its next point to the new node.
• Update head to the new node.

Example:

Original list: 20 → 30 → 20

Insert 10 at beginning → 10 → 20 → 30 → 10

Insertion at End

Insert after the last node and update the new node’s next to point to the head.

• Create a new node.
• Traverse to the last node (whose next is head).
• Update the last node’s next to the new node.
• Set the new node’s next to point to the head.

Example

Original list: 10 → 20 → 10

Insert 30 at end → 10 → 20 → 30 → 10

Insertion at Given Position

Traverse to the node after which the new node is to be inserted.

• Traverse to the node after which the new node is to be inserted.
• Adjust the next pointers:
  • New node's next = current node's next
  • Current node's next = new node

Example:

Insert 25 after 20 in 10 → 20 → 30 → 10

Result: 10 → 20 → 25 → 30 → 10

2. Deletion

Deletion from Beginning

Remove the head and update the last node’s next.

• Point head to head->next.
• Traverse to the last node and update its next to point to the new head.
• Free/delete the original head node.

Example

Delete 10 from 10 → 20 → 30 → 10

Result: 20 → 30 → 20

Deletion from From End

Traverse to the second last node and update its next to the head.

• Traverse to the second-last node.
• Make its next point to the head.
• Free/delete the last node.

Example

Delete 30 from 10 → 20 → 30 → 10

Result: 10 → 20 → 10

Deletion from Specific Position

Adjust the links and delete the target node.

• Traverse to the node before the one to be deleted.
• Change its next to skip the target node (point it to target->next).
• Free the target node.

Example

Delete node with value 20 from 10 → 20 → 30 → 10

Result: 10 → 30 → 10

3. Search

Search for a particular value by traversing from the head until either:

• You find the value.
• You come back to the head without finding it.

4. Traversal

Traversal in a CSLL starts from the head node and moves through each node using the next pointer until it circles back to the head.

• Start with the head node.
• Print or process each node's data.
• Continue moving to next until you reach the head again.
• Special care must be taken to avoid infinite loops.

Example

If the list is: 10 → 20 → 30 → (back to 10)

Traversal will output: 10 20 30

Time and Space Complexity of Circular Singly Linked List

Here is a detailed explanation of the Time and Space Complexity for various operations in a Circular Singly Linked List.

Time Complexity

Space Complexity

• All operations are linear in time O(n) in the worst case.
• Space complexity is O(n) due to dynamic allocation of nodes.
• Unlike arrays, CSLL does not waste memory on pre-allocation, but each node stores an extra pointer.

Advantages

• Efficient for circular tasks like round-robin scheduling, real-time games, etc.
• You can go back to the beginning without restarting the traversal manually.
• Insertion at the end or beginning is more convenient (especially when maintaining a tail pointer).

Disadvantages

• Slightly more complex to implement than a simple singly linked list.
• Care is needed during traversal to avoid infinite loops.
• No direct backward movement (unlike circular doubly linked lists).

Circular Singly Linked List implementation in C Programming

Here is a complete C program implementing all basic operations of a Circular Singly Linked List.

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

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

struct Node* head = NULL;

// 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;
}

// Insertion at the beginning
void insertAtBeginning(int value) {
    struct Node* newNode = createNode(value);
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
    } else {
        struct Node* temp = head;
        while (temp->next != head)
            temp = temp->next;
        newNode->next = head;
        temp->next = newNode;
        head = newNode;
    }
    printf("%d inserted at beginning\n", value);
}

// Insertion at the end
void insertAtEnd(int value) {
    struct Node* newNode = createNode(value);
    if (head == NULL) {
        head = newNode;
        newNode->next = head;
    } else {
        struct Node* temp = head;
        while (temp->next != head)
            temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
    }
    printf("%d inserted at end\n", value);
}

// Insertion at a specific position
void insertAtPosition(int value, int pos) {
    if (pos <= 0) {
        printf("Invalid position\n");
        return;
    }
    if (pos == 1) {
        insertAtBeginning(value);
        return;
    }
    struct Node* newNode = createNode(value);
    struct Node* temp = head;
    for (int i = 1; i < pos - 1 && temp->next != head; i++)
        temp = temp->next;

    newNode->next = temp->next;
    temp->next = newNode;
    printf("%d inserted at position %d\n", value, pos);
}

// Deletion from beginning
void deleteFromBeginning() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = head;
    struct Node* last = head;

    while (last->next != head)
        last = last->next;

    if (head->next == head) {
        free(head);
        head = NULL;
    } else {
        last->next = head->next;
        head = head->next;
        free(temp);
    }
    printf("Deleted from beginning\n");
}

// Deletion from end
void deleteFromEnd() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = head;
    struct Node* prev = NULL;

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

    if (head->next == head) {
        free(head);
        head = NULL;
    } else {
        prev->next = head;
        free(temp);
    }
    printf("Deleted from end\n");
}

// Deletion from a specific position
void deleteFromPosition(int pos) {
    if (head == NULL || pos <= 0) {
        printf("Invalid operation\n");
        return;
    }

    if (pos == 1) {
        deleteFromBeginning();
        return;
    }

    struct Node* temp = head;
    struct Node* prev = NULL;

    for (int i = 1; i < pos && temp->next != head; i++) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == head) {
        printf("Position out of range\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
    printf("Deleted node from position %d\n", pos);
}

// Display list
void display() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = head;
    printf("List: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

// Search operation
void search(int key) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = head;
    int pos = 1;
    do {
        if (temp->data == key) {
            printf("Found %d at position %d\n", key, pos);
            return;
        }
        temp = temp->next;
        pos++;
    } while (temp != head);
    printf("%d not found in the list\n", key);
}

// Main function to test the operations
int main() {
    insertAtEnd(10);
    insertAtEnd(20);
    insertAtEnd(30);
    display();

    insertAtBeginning(5);
    display();

    insertAtPosition(25, 3);
    display();

    deleteFromBeginning();
    display();

    deleteFromEnd();
    display();

    deleteFromPosition(2);
    display();

    search(20);
    search(100);

    return 0;
}

Output

10 inserted at end
20 inserted at end
30 inserted at end
List: 10 20 30
5 inserted at beginning
List: 5 10 20 30
25 inserted at position 3
List: 5 10 25 20 30
Deleted from beginning
List: 10 25 20 30
Deleted from end
List: 10 25 20
Deleted node from position 2
List: 10 20
Found 20 at position 2
100 not found in the list