Write a program to implement Circular Singly Linked List in C.
Circular Linked List is a kind of singly linked list in which the last node of a list is pointing to the first node. Let us understand it by the following example.
In a circular linked list, every node points to the next node. The Last node of the last point back to the head node.
- Type Declaration of a Linked List
- Implementation of Circular Singly Linked List
- Traversing the Circular Singly Linked List
- Insertion of a Node at the Beginning of the List
- Insertion of a Node at the End of the List
- Insertion of a New Node at the Given Position
- Deletion of a Node from the Beginning of the List
- Deletion of a Node from the End of the List
- Deletion of a Node from the Given Position
- Search a Node Data in the List
- Update a Node Data
We have defined the type declaration of a node in the circular singly linked list.
Node Syntax:
struct node { int data; struct node* next; };
Every node contains the data and the reference of the next node.
Here is source code of the C program to implement the circular singly linked list. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/* * C program to Implement the Circular Singly Linked List */ #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *next; }; struct node *head; // function prototyping struct node *create(int); void insert_at_begin(int); void insert_at_end(int); void insert_at_position(int, int); void delete_at_begin(); void delete_at_end(); void delete_at_position(int); void search(int); void update(int, int); void print_list(); void print_list_reverse(); int size_of_list(); int getData(); int getPosition(); int main() { char user_active = 'Y'; int user_choice; int data, position; while(user_active == 'Y' || user_active == 'y') { printf("\n\n------ Circular Singly Linked List -------\n"); printf("\n1. Insert a node at beginning"); printf("\n2. Insert a node at end"); printf("\n3. Insert a node at given position"); printf("\n\n4. Delete a node from beginning"); printf("\n5. Delete a node from end"); printf("\n6. Delete a node from given position"); printf("\n\n7. Print list from beginning"); printf("\n8. Print list from end"); printf("\n9. Search a node data"); printf("\n10. Update a node data"); printf("\n11. Exit"); printf("\n\n------------------------------\n"); printf("\nEnter your choice: "); scanf("%d", &user_choice); printf("\n------------------------------\n"); switch(user_choice) { case 1: printf("\nInserting a node at beginning"); data = getData(); insert_at_begin(data); break; case 2: printf("\nInserting a node at end"); data = getData(); insert_at_end(data); break; case 3: printf("\nInserting a node at the given position"); data = getData(); position = getPosition(); insert_at_position(data, position); break; case 4: printf("\nDeleting a node from beginning\n"); delete_at_begin(); break; case 5: printf("\nDeleting a node from end\n"); delete_at_end(); break; case 6: printf("\nDelete a node from given position\n"); position = getPosition(); delete_at_position(position); break; case 7: printf("\nPrinting the list from beginning\n\n"); print_list(); break; case 8: printf("\nPrinting the list from end\n\n"); if (head == NULL) { printf("\n\tList is Empty!\n"); } else { print_list_reverse(head); } break; case 9: printf("\nSearching the node data"); data = getData(); search(data); break; case 10: printf("\nUpdating the node data"); data = getData(); position = getPosition(); update(position, data); break; case 11: printf("\nProgram was terminated\n\n"); return 0; default: printf("\n\t Invalid Choice\n"); } printf("\n...............................\n"); printf("\nDo you want to continue? (Y/N) : "); fflush(stdin); scanf(" %c", &user_active); } return 0; } struct node *create(int data) { struct node *new_node = (struct node *)malloc(sizeof(struct node)); if (new_node == NULL) { printf("\nMemory can't be allocated.\n"); return NULL; } new_node->data = data; new_node->next = NULL; return new_node; } // function to insert a new node at the beginning of the list void insert_at_begin(int data) { struct node *new_node = create(data); if (new_node != NULL) { struct node *last = head; // if the list is empty if (head == NULL) { head = new_node; new_node->next = head; return; } // traverse to the end node while (last->next != head) { last = last->next; } // update the last node to the new node last->next = new_node; // update the next pointer of the new node to the head node new_node->next = head; // update the head of the list to new node head = new_node; } } // function to insert a new node at the end of the list void insert_at_end(int data) { struct node *new_node = create(data); if (new_node != NULL) { // if the list is empty if (head == NULL) { head = new_node; new_node->next = head; return; } struct node *last = head; // traverse to the end node while (last->next != head) { last = last->next; } // update the last node to the new node last->next = new_node; // update the next pointer of the new node to the head node new_node->next = head; } } // function to insert a new node at the given position void insert_at_position(int position, int data) { // checking if the position is valid or not if (position <= 0) { printf("\nInvalid Position\n"); } else if (head == NULL && position > 1) { printf("\nInvalid Position\n"); } else if (head != NULL && position > size_of_list()) { printf("\nInvalid Position\n"); } else if (position == 1) { insert_at_begin(data); } else { struct node *new_node = create(data); if (new_node != NULL) { struct node *temp = head, *prev = NULL; // Since, temp is already pointing to first node // then count will be start at second node int i = 1; // traverse the list to the given position while (++i <= position) { prev = temp; temp = temp->next; } // update the prev node to the new noe prev->next = new_node; // update the new node to the temp (position node) new_node->next = temp; } } } // function to delete a node from the beginning of the list void delete_at_begin() { // check where the list is empty or not if (head == NULL) { printf("\n List is Empty! \n"); return; } // traverse to the end of the list struct node *last = head; struct node *temp = head; // if only one node in the list if (last->next == head) { free(last); head = NULL; return; } // traverse to the last node while (last->next != head) { last = last->next; } head = head->next; last->next = head; free(temp); temp = NULL; } // function to delete a node from the end of the list void delete_at_end() { // check where the list is empty or not if (head == NULL) { printf("\n List is Empty! \n"); return; } // traverse to the end of the list struct node *prev = head; struct node *temp = head->next; // if only one node in the list if (prev->next == head) { free(prev); head = NULL; return; } while (temp->next != head) { prev = temp; temp = temp->next; } prev->next = head; free(temp); temp = NULL; } // function to delete a node from the given position void delete_at_position(int position) { if (position <= 0) { printf("\n Invalid Position \n"); } else if (position > size_of_list()) { printf("\n Invalid position \n"); } else if (position == 1) { delete_at_begin(); } else if (position == size_of_list()) { delete_at_end(); } else { struct node *temp = head; struct node *prev = NULL; int i = 1; while (i < position) { prev = temp; temp = temp->next; i += 1; } prev->next = temp->next; free(temp); temp = NULL; } } // print the node values void print_list() { struct node *temp = head; if (head == NULL) { printf("\n List is Empty! \n"); return; } printf("\n"); do { printf("%d ", temp->data); temp = temp->next; } while (temp != head); printf("\n"); } // print the node values recursively void print_list_reverse(struct node* temp) { if (temp->next == head) { printf("%d ", temp->data); return; } print_list_reverse(temp->next); printf("%d ", temp->data); } // search a data into the list void search(int key) { struct node* temp = head; do { if (temp->data == key) { printf("\n\t Data Found\n"); return; } temp = temp->next; }while (temp->next != head); printf("\n\tData not Found\n"); } // function to update a node void update(int position, int new_data) { if (position <= 0 || position > size_of_list()) { printf("\n Invalid position\n"); return; } struct node* temp = head; int i = 0; while (i <= position) { temp = temp->next; i += 1; } temp->data = new_data; } // function to calculate the size of the list int size_of_list() { if (head == NULL) { return 0; } struct node *temp = head; int count = 1; while (temp->next != head) { count += 1; temp = temp->next; } return count; } int getData() { int data; printf("\n\nEnter Data: "); scanf("%d", &data); return data; } int getPosition() { int pos; printf("\n\nEnter Position: "); scanf("%d", &pos); return pos; }
Some functions are performing the different operations on the list. We are discussing these functions and understanding how they are working.
Traversing is the process of visiting the nodes one time from start to end of the list. Following are the steps required to traverse the list.
- Start iterating from beginning to end of the list using a temporary variable that stores the address of the first node.
- Iterate through the list until the head node comes again.
- Print the data that every node contains.
Time Complexity: O(n)
The time complexity of circular singly linked list is O(n), here we are traversing the list from the beginning to the end. Here, n is the size of the list.
Space Complexity: O(1)
Space is constant due to only the temporary variables taken to traverse the list.
Inserting a new node in the list increases the size of the list by one. These are the following steps to insert the new node at the beginning of the list:
- Traverse the list to the last node.
- Update the next pointer of the last node to the new node.
- Update the next pointer of the new node to the head node.
- Update the head node to the new node.
Example: Insert a new node with data 99 at the beginning of the list.
Step 1: Traverse the list to the last node.
Step 2: Update the next pointer of the last node to the new node.
Step 3: Update the next pointer of the new node to the head node.
Step 4: Update the head node to the new node.
Time Complexity: O(n)
The time complexity of circular singly linked list in C is O(n), since we are traversing from the beginning to end, time depends on the size of the list.
Space Complexity: O(1)
Constant amount of space is taken to insert the new node at the beginning. So, the space complexity is constant i.e. O(1).
In this case, we are inserting the nodes from the beginning of the circular singly linked list.
------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 1 ------------------------------ Inserting a node at beginning Enter Data: 90 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 1 ------------------------------ Inserting a node at beginning Enter Data: 78 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 1 ------------------------------ Inserting a node at beginning Enter Data: 99 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 99 78 90 ............................... Do you want to continue? (Y/N) : n
The size of the list increased by one on the insertion of a new node. We have to follow the given steps to insert a new node at the end of the list.
- Traverse the list to the last node.
- Update the next pointer of the last node to the new node.
- Update the next pointer of the new node to the head node.
Example: Insert a new node with data 35 at the end of the list.
Step 1: Traverse the list to the last node.
Step 2: Update the next pointer of the last node to the new node.
Step 3: Update the next pointer of the new node to the head node.
Time Complexity: O(n)
Since we need to go to the last node by traversing the list. Time is linearly dependent on the size of the list which is n.
Space Complexity: O(1)
Space is constant due to only the temporary variables taken to traverse the list.
In this case, we are inserting the nodes from the end of the circular singly linked list.
------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 99 78 90 ............................... Do you want to continue? (Y/N) : Y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 2 ------------------------------ Inserting a node at end Enter Data: 35 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 99 78 90 35 ............................... Do you want to continue? (Y/N) : n
Inserting a new node at the given position needs to follow the given steps:
- Traverse the list to the given position K.
- Update the next pointer of the K-1th node to the new node.
- Update the next pointer of the new node to the Kth node.
Example: Insert a new node with data 35 at position 2.
Step 1: Traverse the list to the given position K = 3. (1-based index)
Step 2: Update the next pointer of the K-1th node to the new node.
Step 3: Update the next pointer of the new node to the Kth node.
Time Complexity: O(n)
There is a need for traversal to reach the given position. In the worst case, we need to traverse the entire list so that the time complexity is linear.
Space Complexity: O(1)
Only the temporary variables are taken for this operation so space is constant.
In this case, we are inserting the nodes at the particular position in the list.
------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 99 78 90 35 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 3 ------------------------------ Inserting a node at the given position Enter Data: 65 Enter Position: 2 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 99 12 78 90 35 ............................... Do you want to continue? (Y/N) : n
Deletion of a node reduces the size of the list by one. Deletion requires the following steps:
- Traverse the list to the end node.
- Update the next pointer of the last node to the next of the head node.
- Update the head to the next of the head node.
- Free the last head node.
Example: Deleting a node with data 56 from the beginning of the list.
Step 1: Traverse the list to the node.
Step 2: Update the next pointer of the last node to the next of the head node.
Step 3: Update the head to the next of the head node.
Step 4: Free the last head node.
Time Complexity: O(n)
To change the last node reference we have to traverse the list and it makes this operation linearly dependent on the size of the list.
Space Complexity: O(1)
Space is constant due to temporary variables being taken.
In this case, we are deleting the nodes from the beginning of the circular singly linked list.
------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 99 12 78 90 35 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 4 ------------------------------ Deleting a node from beginning * Node with data 99 was Deleted .............................. Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 12 78 90 35 ............................... Do you want to continue? (Y/N) : n
Deletion of a node from the end of the circular singly linked list takes the following steps:
- Traverse the list to the N-1th node, where N is the number of nodes.
- Update the next pointer of the N-1th node to the head node.
- Free the Nth node.
Example: Deleting the last node having data 35.
Step 1: Traverse the list to the N-1th node, where N is the number of nodes.
Step 2: Update the next pointer of the N-1th node to the head node.
Step 3: Free the Nth node.
Time Complexity: O(n)
Traversing is needed to reach the last node so the complexity becomes linearly dependent on the size of the list.
Space Complexity: O(1)
Space is constant due to only the temporary variables taken to traverse the list.
In this case, we are deleting the nodes from the end of the circular singly linked list.
------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 12 78 90 35 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 5 ------------------------------ Deleting a node from end * Node with data 35 was Deleted ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 12 78 90 ............................... Do you want to continue? (Y/N) : n
To delete a node from the given position, we have to follow the given steps:
- Traverse the list upto the given position K.
- Update the next pointer of the K-1th node to the K+1th node.
- Free the Kth node.
Example: Deleting the 3rd node of the given list.
Step 1: Traverse the list upto the given position.
Step 2: Update the next pointer of the K-1th node to the K+1th node.
Step 3: Free the temp node.
Time Complexity: O(n)
Traversing is needed to reach the given position so the complexity becomes linearly dependent on the size of the list in the worst case.
Space Complexity: O(1)
Space is constant due to only the temporary variables taken to traverse the list.
In this case, we are deleting the node from the particular position of the list.
------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 12 78 90 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 6 ------------------------------ Enter Position: 1 * Node with data 12 was Deleted ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from beginning 78 90 ............................... Do you want to continue? (Y/N) : n
Searching is the process to find a value in the linked list. We have to follow the given steps to search the value in the list.
- Traverse from start to end of the list.
- Match the node data with the given key.
Time Complexity: O(n)
Since we are traversing the list from beginning to end, the complexity depends on the size of the list which is n.
Space Complexity: O(1)
It takes a constant amount of space to find the key in the list.
In this case, we are searching for a node in the list.
------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 8 ------------------------------ Printing the list from end 90 78 12 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 9 ------------------------------ Searching the node data Enter Data: 78 Found data at 2 position ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 9 ------------------------------ Searching the node data Enter Data: 74 Data not Found ............................... Do you want to continue? (Y/N) : n
Updation is the process to change the current node value with the new value. It needs to follow the given steps:
- Traverse the list upto the given position.
- Update the value of the node with the new given value.
Time Complexity: O(n)
In the worst case, the complexity to update the node takes linear time which is the size of the list.
Space Complexity: O(1)
Since we are using only temporary variables, space is constant.
In this case, we are updating a node data at a particular position.
------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 8 ------------------------------ Printing the list from end 90 78 12 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 10 ------------------------------ Updating the node data Entert Data: 40 Enter Position: 1 Updated node data is 40 ............................... Do you want to continue? (Y/N) : y ------ Circular Singly Linked List ------- 1. Insert a node at beginning 2. Insert a node at end 3. Insert a node at given position 4. Delete a node from beginning 5. Delete a node from end 6. Delete a node from given position 7. Print list from beginning 8. Print list from end 9. Search a node data 10. Update a node data 11. Exit ------------------------------ Enter your choice: 7 ------------------------------ Printing the list from end 40 12 78 90 ............................... Do you want to continue? (Y/N) : n
To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.
If you find any mistake above, kindly email to [email protected]- Apply for Computer Science Internship
- Practice Design & Analysis of Algorithms MCQ
- Check Computer Science Books
- Check Data Structure Books
- Practice Computer Science MCQs