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
- Cyclic Structure: The last node connects back to the first node.
- Dynamic Size: Nodes can be added or removed as needed.
- 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.
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 (returnsNULL
), it prints an error message and exits the program. - Node Initialization: It sets the
data
field of the node to the givenvalue
and thenext
pointer toNULL
. - 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.
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 // Function to create a singly circular linked list with 3 nodes // Linking nodes to form a circular linked list return first; // Return pointer to the head node // Function to display the circular linked list struct Node* temp = head; // Main function // Free memory 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:
- Easy Traversal: You can go through the list from any point without having to start over, making it great for repeated tasks.
- Flexible Size: The list can grow or shrink as needed without worrying about running out of space like in arrays.
- Great for Queues: It’s perfect for circular queues, where the last item loops back to the first for smooth operations.
- 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.
- 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:
- Round-Robin Scheduling: Used in operating systems to cycle through processes, ensuring fair CPU time allocation.
- Circular Queues: Efficiently implement circular queues for tasks like resource management in embedded systems.
- Multiplayer Games: Manages player turns in a loop for games where players take turns cyclically.
- Music or Video Playlists: Enables seamless looping of playlists without needing to restart manually.
- Traffic Light Management: Simulates traffic lights in a circular sequence to ensure smooth transitions.
- 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.