Circular Singly Linked List is a form of Singly Linked List and is connected in circular form. The last node has the link to the first node to form the circle. So, It is possible to traverse the circular list starting from any node. However, reversing the list is not simple.
See Circular Doubly Linked List for bidirectional communication.
1. Representation
- Node: A node consists of the data element and the pointer to the Next node
- Element: The actual data
- Next: Pointer to the next node
- Last: Pointer to the last node of the linked list. This is required to perform the insert operation at the front in O(1) time. The Head pointer is not required since the last node contains the pointer to the head node.
- Circular: Note the last node points to the first node and forms the circle.
Applications
- Circular Singly Linked List is useful for applications that require circular / loop operations.
- Music Player can use to play the songs in a loop.
- Round Robin CPU scheduling is another application that uses Circular Linked List.
- Multi-player gaming applications can use a circular list to keep the players.
2. Insertion on Circular Linked List
An element can be inserted into the linked list in any of the following three methods.
- InsertFront – at the beginning of the List
- InsertBack – at the end of the List
- InsertAfter – after the specific Node
2.1. Insert Front
In a circular list, the last node is connected to the first node. So, we Insert the new node after the last node which is considered the front node.
Algorithm
- Create the new node
- Check if the list is empty. If true, make the new node the last and point itself to form the one-node circle.
- Connect the new node at the front.
Code
Node* CircularList::insert_front(int element) { // Step 1. Create the new node Node* new_node = new Node(); new_node->element = element; // Step 2. Check if the list is empty. If true, make the new node // as last and point itself to form the one node circle. if (last == NULL) { new_node->next = new_node; last = new_node; return new_node; } // Step 3. Connect the new node at front. // The last->next is the front node of circular linked list new_node->next = last->next; last->next = new_node; return new_node; }
2.2. Insert Back
This is similar to Insert Front where we Insert the new node after the last node. In addition, change the “Last” pointer to the new node so that it is on the backside.
Algorithm
- Create the new node
- Check if the list is empty. If true, make the new node the last and point itself to form the one-node circle.
- Link the new node after the last node
- Make the new node the last node
Code
Node* CircularList::insert_back(int element) { // Step 1. Create the new node Node *new_node = new Node(); new_node->element = element; // Step 2. Check if the list is empty. If true, make the new node // as last and point itself to form the one node circle. if (last == NULL) { new_node->next = new_node; last = new_node; return new_node; } // Step 3. Link the new node after the last node new_node->next = last->next; last->next = new_node; // Step 4. Make the new node as last node last = new_node; return new_node; }
2.3. Insert After
Here, we Insert the new node (20) after the specific node (10).
Algorithm
- Create the new node
- Link the new node after the given node
Code
Node* CircularList::insert_after(Node* prev, int element) { // Step 1. Create the new node Node *new_node = new Node(); new_node->element = element; // Step 2. Link the new node after the given node new_node->next = prev->next; prev->next = new_node; return new_node; }
3. Deletion on Circular Linked List
An element can be deleted from the circular linked list in any of the following methods.
- Delete Front – Delete from the beginning of the List
- Delete After – Delete after the specific node
- Remove – Search the specific element and remove the node
3.1. Delete Front
Link the last node (30) directly with the second node (20), so that the first node (10) can be removed from the list.
Algorithm
- Check if the list is empty. If true, return.
- Check if the list has only a single node. If true, delete the node, reset the last to NULL, and return.
- Otherwise, store the reference to the front node as the target.
- Disconnect the front node by directly connecting the last node and the next node.
- Delete the target node
Code
Node* CircularList::delete_front() { // Step 1. Check if the list is empty. If true, return. if (last == NULL) { return NULL; } // Step 2. Check if the list has single node. If true, delete the node, // reset the last to NULL, and return. if (last->next == last) { delete last; last = NULL; return NULL; } // Step 3. Otherwise, store the reference to front node as target Node* target = last->next; // Step 4. Disconnect the front node by directly connecting the last node and the next node. last->next = last->next->next; // Step 5. Delete the target node delete target; return last->next; }
3.2. Delete After
Delete a node after the node (20). Disconnect the target node (30) by directly linking its previous and next node. In this case, both the previous and next nodes are the same.
Algorithm
- Initialize the target with the reference to the target node
- Check if the list has only a single node and return if true because the delete after is not applicable.
- Disconnect the target node by directly linking its previous and next node.
- Check if the target node is the last node. If true, move the last pointer to the previous node.
- Delete the target node.
Code
bool CircularList::delete_after(Node* prev) { // Step 1. Initialize target with the reference to the target node Node* target = prev->next; // Step 2. Check if the list has only a single node and return if true // because the delete after is not applicable. if (prev == target) { return false; } // Step 3. Disconnect the target node by directly linking its // previous and next node. prev->next = target->next; // Step 4. Check if the target node is the last node. If true, // move the last pointer to the previous node if (target == last) { last = prev; } // Step 4. Delete the target node delete target; return true; }
3.3. Remove
Remove the node by the specific element (20). Traverse the list to search the given element and delete the node. This can take O(n) time to search the element.
Algorithm
- Check if the list is empty and return if true.
- Check if the list contains a only node. If true, check if the element matches and delete the node.
- Otherwise, Iterate the linked list from start to end, and search if the element is found.
- If found, set the node as the target node and disconnect it by directly linking its previous and next node.
- Check if the target node is the last node. If true, move the last pointer to the previous node.
- Delete the target node.
Code
bool CircularList::remove(int element) { // Step 1. Check if the list is empty and return if true. if (last == NULL) { return false; } // Step 2. Check if the list contains only node if (last == last->next) { if (last->element == element) { delete last; last = NULL; return true; } return false; } // Step 3. Iterate the linked list from start to end, // and search if the element is found. for (Node* node = last; node->next != last; node = node->next) { if (node->next->element == element) { // Step 4. If found, set the node as target node and disconnect // it by directly linking its previous and next node. Node* target = node->next; node->next = node->next->next; // Step 5. Check if the target node is the last node. If true, // move the last pointer to the previous node if (target == last) { last = node; } // Step 6. Delete the target node delete target; return true; } } return false; }
4. Search on Circular Linked List
The list is traversed from start to end to search for an element in the Linked List. The last node of the circular list always points to the Head. This must be checked to identify the end of the list.
Algorithm
- Check if the list is empty
- Iterate the linked list from start to end and search element
- Return the node if found, NULL otherwise.
Code
Node* CircularList::search(int element) { // Check if the list is empty if (last == NULL) { return NULL; } // Iterate the linked list from start to end and search element Node* node = last->next; do { if (node->element == element) { return node; // Found element } node = node->next; } while (node != last->next); return NULL; // Not found }
5. The Complete Example in C++
/** * C++ example to demonstrate the circular linked list */ #include <iostream> using namespace std; // Linked list node representation struct Node { int element; Node* next; }; /** * Circular linked list implementation */ class CircularList { // The last node of the list // The last->next contains the address of head node Node* last; public: // Constructor CircularList() : last(NULL) {} // Insert an element in front of the list // Returns the new node inserted Node* insert_front(int element); // Insert an element at the end of the list // Returns the new node inserted Node* insert_back(int element); // Insert an element after the given node // Returns the new node inserted Node* insert_after(Node* prev, int element); // Delete the front element // Returns the next node if available, NULL otherwise. Node* delete_front(); // Delete the node after the given node // Returns true on success, false otherwise. bool delete_after(Node* prev); // Search and delete the given element // Returns true on success, false otherwise. bool remove(int element); // Search an element from the list // Returns the matching node if found, NULL otherwise. Node* search(int element); // Traverse the list and print the elements void traverse(const std::string& msg); }; Node* CircularList::insert_front(int element) { // Step 1. Create the new node Node* new_node = new Node(); new_node->element = element; // Step 2. Check if the list is empty. If true, make the new node // as last and point itself to form the one node circle. if (last == NULL) { new_node->next = new_node; last = new_node; return new_node; } // Step 3. Connect the new node at front. // The last->next is the front node of circular linked list new_node->next = last->next; last->next = new_node; return new_node; } Node* CircularList::insert_back(int element) { // Step 1. Create the new node Node *new_node = new Node(); new_node->element = element; // Step 2. Check if the list is empty. If true, make the new node // as last and point itself to form the one node circle. if (last == NULL) { new_node->next = new_node; last = new_node; return new_node; } // Step 3. Link the new node after the last node new_node->next = last->next; last->next = new_node; // Step 4. Make the new node as last node last = new_node; return new_node; } Node* CircularList::insert_after(Node* prev, int element) { // Step 1. Create the new node Node *new_node = new Node(); new_node->element = element; // Step 2. Link the new node after the given node new_node->next = prev->next; prev->next = new_node; return new_node; } Node* CircularList::delete_front() { // Step 1. Check if the list is empty. If true, return. if (last == NULL) { return NULL; } // Step 2. Check if the list has single node. If true, delete the node, // reset the last to NULL, and return. if (last->next == last) { delete last; last = NULL; return NULL; } // Step 3. Otherwise, store the reference to front node as target Node* target = last->next; // Step 4. Disconnect the front node by directly connecting the last node and the next node. last->next = last->next->next; // Step 5. Delete the target node delete target; return last->next; } bool CircularList::delete_after(Node* prev) { // Step 1. Initialize target with the reference to the target node Node* target = prev->next; // Step 2. Check if the list has only a single node and return if true // because the delete after is not applicable. if (prev == target) { return false; } // Step 3. Disconnect the target node by directly linking its // previous and next node. prev->next = target->next; // Step 4. Check if the target node is the last node. If true, // move the last pointer to the previous node if (target == last) { last = prev; } // Step 4. Delete the target node delete target; return true; } bool CircularList::remove(int element) { // Step 1. Check if the list is empty and return if true. if (last == NULL) { return false; } // Step 2. Check if the list contains only node if (last == last->next) { if (last->element == element) { delete last; last = NULL; return true; } return false; } // Step 3. Iterate the linked list from start to end, // and search if the element is found. for (Node* node = last; node->next != last; node = node->next) { if (node->next->element == element) { // Step 4. If found, set the node as target node and disconnect // it by directly linking its previous and next node. Node* target = node->next; node->next = node->next->next; // Step 5. Check if the target node is the last node. If true, // move the last pointer to the previous node if (target == last) { last = node; } // Step 6. Delete the target node delete target; return true; } } return false; } Node* CircularList::search(int element) { // Check if the list is empty if (last == NULL) { return NULL; } // Iterate the linked list from start to end and search element Node* node = last->next; do { if (node->element == element) { return node; // Found element } node = node->next; } while (node != last->next); return NULL; // Not found } // Traverse and print the linked list void CircularList::traverse(const std::string& msg) { cout << msg << endl; if (last == NULL ) { cout << "NULL" << endl << endl; return; } // Iterate the linked list from start to end Node* node = last->next; do { cout << " --> " << node->element ; node = node->next; } while (node != last->next); cout << " --> " << endl << endl; } int main() { // Create a linked list CircularList list; list.traverse("initial list"); // Insert elements Node* node_10 = list.insert_front(10); list.traverse("insert_front(10)"); list.insert_back(30); list.traverse("insert_back(30)"); list.insert_after(node_10, 20); list.traverse("insert_after(node_10, 20)"); // Search an element Node* node_20 = list.search(20); cout << "search(20) matches node " << node_20->element << endl << endl; // Delete elements list.delete_front(); list.traverse("delete_front()"); list.delete_after(node_20); list.traverse("delete_after(node_20)"); list.remove(20); list.traverse("remove(20)"); }
Output
initial list
NULL
insert_front(10)
--> 10 -->
insert_back(30)
--> 10 --> 30 -->
insert_after(node_10, 20)
--> 10 --> 20 --> 30 -->
search(20) matches node 20
delete_front()
--> 20 --> 30 -->
delete_after(node_20)
--> 20 -->
remove(20)
NULL