Circular Singly Linked List in C

A Circular Singly Linked List (CSLL) is a type of linked list where the last node points back to the first node, forming a circle. This data structure is particularly useful for applications where you need a circular traversal, such as buffering and task scheduling.

In this article, we will explore the structure, advantages, and operations of a Circular Singly Linked List in C, along with examples to guide your understanding.

Key Features of a Circular Singly Linked List

  1. Cyclic Structure: The last node connects back to the first node.
  2. Dynamic Size: Nodes can be added or removed as needed.
  3. Efficient Traversal: Allows circular iteration without additional logic.

Structure of a Circular Singly Linked List in C

In C, a Circular Singly Linked List is typically implemented using a node structure

#include <stdio.h>
#include <stdlib.h>struct Node {
int data;
struct Node* next;
};

Each node in singly linked list contains two parts:

  • data: The value stored in the node.
  • next: A pointer which holds the address to the next node.

circular singly link list node structure

Basic Operations in Circular Singly Linked List

1. Creating a Node in Circular Singly Linked List

To create a new node, the code in C programming  is given below

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf(“Memory allocation failed.\n”);
exit(1);
}
newNode->data = value;
newNode->next = NULL;
return newNode;
}

The code Explanation is given below

  • Function Purpose: The function createNode creates a new node for a linked list with a specified value.
  • Memory Allocation: It uses malloc to allocate memory for a new node dynamically.
  • Error Check: If malloc fails (returns NULL), it prints an error message and exits the program.
  • Node Initialization: It sets the data field of the node to the given value and the next pointer to NULL.
  • Return Value: The function returns a pointer to the newly created node.

2. Inserting Nodes in Circular Singly Linked List

a. Insertion at the Beginning

The insertAtBeginning function inserts a new node at the start of a circular linked list. It creates a new node using createNode. If the list is empty, the new node points to itself, making it circular. Otherwise, it traverses to the last node, links the new node to the head, updates the last node’s next pointer to the new node, and sets the new node as the head.

To insert at beginning in singly circular linked list, The code in C programming  is given below

struct Node* insertAtBeginning(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
newNode->next = newNode;
return newNode;
} else {
struct Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
return newNode;
}
}

b. Insertion at the End

The insertAtEnd function adds a new node at the end of a circular linked list. If the list is empty, the new node points to itself, making it circular. Otherwise, it traverses to the last node, updates its next pointer to the new node, and sets the new node’s next to the head, maintaining the circular structure.

To insert at end in singly circular linked list, The code in C programming  is given below

struct Node* insertAtEnd(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
newNode->next = newNode;
return newNode;
} else {
struct Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
return head;
}
}

3. Deleting Nodes in Circular Singly Linked List

a. Deletion from the Beginning

The deleteFromBeginning function removes the first node from a circular linked list. If the list is empty, it prints a message and exits. If the list has only one node, it frees the node and sets the head to NULL. Otherwise, it finds the last node, updates the head to the next node, adjusts the last node’s next pointer to the new head, and frees the original first node.

To delete at beginning in singly circular linked list, The code in C programming  is given below

struct Node* deleteFromBeginning(struct Node* head) {
if (head == NULL) {
printf(“List is empty.\n”);
return NULL;
}
struct Node* temp = head;
if (temp->next == head) {
free(temp);
return NULL;
} else {
struct Node* last = head;
while (last->next != head) {
last = last->next;
}
head = temp->next;
last->next = head;
free(temp);
return head;
}
}

b. Deletion from the End

The deleteFromEnd function removes the last node from a circular linked list. If the list is empty, it prints a message and exits. If the list has only one node, it frees the node and sets the head to NULL. Otherwise, it traverses to the last node, updates the second-last node’s next pointer to the head, and frees the last node.

To delete at end position in singly circular linked list, The code in C programming  is given below

struct Node* deleteFromEnd(struct Node* head) {
if (head == NULL) {
printf(“List is empty.\n”);
return NULL;
}
struct Node* temp = head;
if (temp->next == head) {
free(temp);
return NULL;
} else {
struct Node* prev = NULL;
while (temp->next != head) {
prev = temp;
temp = temp->next;
}
prev->next = head;
free(temp);
return head;
}
}

4. Traversing the List

The traverseList function prints all the elements of a circular linked list. If the list is empty, it prints a message and exits. Otherwise, it starts from the head node and iterates through the list, printing the data of each node until it loops back to the head.

void traverseList(struct Node* head) {
if (head == NULL) {
printf(“List is empty.\n”);
return;
}
struct Node* temp = head;
do {
printf(“%d “, temp->data);
temp = temp->next;
} while (temp != head);
printf(“\n”);
}

Example of Circular Singly Linked List

Following is the example of singly circular linked list where list contains three nodes.

Circular Singly Linked List Example

The code in C programming for above given example of singly circular linked list is given under

#include <stdio.h>
#include <stdlib.h>// Define a node structure
struct Node {
int data;
struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf(“Memory allocation failed\n”);
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to create a singly circular linked list with 3 nodes
struct Node* createCircularList() {
struct Node* first = createNode(50); // First node
struct Node* second = createNode(60); // Second node
struct Node* third = createNode(70); // Third node

// Linking nodes to form a circular linked list
first->next = second;
second->next = third;
third->next = first;

return first; // Return pointer to the head node
}

// Function to display the circular linked list
void displayCircularList(struct Node* head) {
if (!head) {
printf(“The list is empty.\n”);
return;
}

struct Node* temp = head;
do {
printf(“%d -> “, temp->data);
temp = temp->next;
} while (temp != head);
printf(“(back to head)\n”);
}

// Main function
int main() {
struct Node* head = createCircularList();
printf(“Singly Circular Linked List:\n”);
displayCircularList(head);

// Free memory
struct Node* temp = head;
struct Node* nextNode;
do {
nextNode = temp->next;
free(temp);
temp = nextNode;
} while (temp != head);

return 0;
}

Output:

Singly Circular Linked List:
50 -> 60 -> 70 -> (back to head)

Explanation: This program creates and displays a singly circular linked list with three nodes containing values 10, 20, and 30. The createCircularList function constructs the circular linked list by linking the nodes so the last node points back to the first. The displayCircularList function traverses and prints the list in a loop until it returns to the head. Finally, the program frees the allocated memory to avoid memory leaks.

Advantages of Circular Singly Linked List

Here are the top 5 benefits of a circular singly linked list in simple terms:

  1. Easy Traversal: You can go through the list from any point without having to start over, making it great for repeated tasks.
  2. Flexible Size: The list can grow or shrink as needed without worrying about running out of space like in arrays.
  3. Great for Queues: It’s perfect for circular queues, where the last item loops back to the first for smooth operations.
  4. No End Point: The list has no clear end, making it ideal for tasks like scheduling where you need to repeat actions in a cycle.
  5. Quick Additions: Adding items is simple and doesn’t need shifting things around like in arrays.

Applications of Circular Singly Linked List

Here are the top applications of a circular singly linked list:

  1. Round-Robin Scheduling: Used in operating systems to cycle through processes, ensuring fair CPU time allocation.
  2. Circular Queues: Efficiently implement circular queues for tasks like resource management in embedded systems.
  3. Multiplayer Games: Manages player turns in a loop for games where players take turns cyclically.
  4. Music or Video Playlists: Enables seamless looping of playlists without needing to restart manually.
  5. Traffic Light Management: Simulates traffic lights in a circular sequence to ensure smooth transitions.
  6. Token Passing in Networks: Used in token ring networks to cycle tokens among nodes for communication.

Understanding and implementing Circular Singly Linked Lists in C can unlock powerful ways to handle circular data traversal efficiently. This guide provides a solid foundation for mastering this data structure in your programs.