Circular Linked List in C++
What is a circular linked list in C++?
Circular linked list in C++ is another data structure, which is an enhancement of the linked list data structure. As we have studied that the linked list is a data structure in which every node in the list has the link of its next node and the last node is pointing to null.
Similarly, in the circular linked list, every node has the link to its next node and the last node does not point to null like a linked list rather it points to the head of the list.
Why Circular Linked List?
1. Traversing the list becomes easy
- In a circular linked list, each node is connected to the next node, and the last node points back to the first node, forming a continuous loop.
- This structure makes it easy to traverse the entire list starting from any node without needing to go back to the head node.
- Moving from the last node to the first node is just a single step, unlike a singly linked list, where you would have to start over from the head.
- This looping structure is particularly useful when implementing repetitive or circular tasks.
2. Implementation of advance data structure
- Circular linked lists provide a convenient way to implement advanced data structures like queues, priority queues, and buffering systems.
- In a circular queue, for instance, the last position is connected back to the first position, allowing data to be processed in a continuous loop without needing additional memory management.
- This makes circular linked lists ideal for implementing such structures effectively and efficiently.
3. Useful in applications that go around in a loop
- Applications that operate in a continuous loop, such as round robin scheduling, real time systems, and buffering mechanisms, can be effectively implemented using circular linked lists.
- Since the last node points back to the first node, the list can keep cycling through the data without requiring a reset or reinitialization.
- This looping structure makes it easier to handle tasks that repeat indefinitely or follow a cyclical pattern.
Structure of circular linked list
Circular linked can be of both singly and doubly type. So they can be defined in a program by using following set of code.
- Singly circular linked list is :-
struct node { int data; struct node *next; } - Doubly circular linked list is:-
struct node
{
struct node *prev;
int data;
struct node *next;
}
Operation on circular linked list in C++
We can perform following operations on a circular linked list.
- Counting the nodes
- Insertion
- Inserting at Beginning of the list.
- Inserting at End of the list.
- Inserting at Specific location in the list.
- Deletion
- Deleting from Beginning of the list.
- Deleting from End of the list.
- Deleting a Specific Node from the list
- Splitting a list into two halves
- Sorted insertion in the list
About Basic Operations in Circular Linked List:
| Operation | Operation Type | Description | Time Complexity | Space Complexity |
|---|---|---|---|---|
| Insert | insertAtFirst | Adds a new node at the beginning of the list. | O(N) | O(1) |
| Insert | InsertAt | Adds a new node at the specified position. | O(N) | O(1) |
| Insert | insertAtEnd | Adds a new node at the end and points its next pointer to the head. | O(N) | O(1) |
| Delete | deleteFromFirst | Removes the first node and updates the current head of the list. | O(N) | O(1) |
| Delete | Delete | Deletes the node with a given key value. | O(N) | O(1) |
| Delete | deleteFromEnd | Removes the last node and updates the next pointer of the second last node. | O(N) | O(1) |
| Display | Iterates through the list and prints the data of each node. | O(N) | O(1) |
C++ programming code for creating a circular linked list:
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
class CircularLinkedList {
private:
Node* head;
public:
CircularLinkedList() : head(nullptr) {}
void create(int n) {
Node* last = nullptr;
int value;
for (int i = 1; i <= n; i++) {
cout << "Enter data for node " << i << ": "; cin >> value;
Node* newNode = new Node(value);
if (!head) {
head = newNode;
last = newNode;
last->next = head; // Circular link
} else {
last->next = newNode;
last = newNode;
last->next = head; // Maintain circular link
}
}
}
void display() {
if (!head) {
cout << "List is empty" << endl;
return;
}
Node* temp = head;
int i = 1;
cout << "\nData in the circular linked list:" << endl;
do {
cout << "Node " << i++ << ": " << temp->data << endl; temp = temp->next;
} while (temp != head);
}
};
int main() {
CircularLinkedList list;
int n;
cout << "Enter the number of nodes: "; cin >> n;
list.create(n);
list.display();
return 0;
}
Space Complexity = O(n)
Time Complexity = O(n)
Advantages and Disadvantages of Circular Linked List
Advantages of Circular Linked List in C++:
- Efficient Traversal: You can start at any node and reach every other node without resetting to the head.
- Useful for Queues: Makes it easy to implement circular queues.
- Continuous Looping: Enables repetitive tasks without needing to restart from the head.
Disadvantages of Circular Linked List in C++:
Complex Implementation: More challenging to manage pointers and avoid infinite loops.
Risk of Infinite Loop: If not handled carefully, traversal can keep looping endlessly.
Linear Access Time: Searching for a specific node still takes O(N) time.
FAQ's Related Circular Linked List
Answer:
A circular linked list is a linked list where the last node points back to the first node, forming a circular structure.
Answer:
The main operations are insertion, deletion, and traversal. Insertion and deletion can occur at the beginning, end, or a specific position.
Answer:
It is useful for implementing circular data structures like round robin scheduling, buffering, and continuous loops.
Answer:
Traversal has a time complexity of O(N), where N is the number of nodes.
Answer:
If not managed properly, it can result in infinite loops during traversal.
Login/Signup to comment