C++ Code for Circular Linked List
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* next;
};
// Insert a node at the beginning
void insertAtHead(Node*& head, int value) {
Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) { // If the list is empty
newNode->next = newNode; // Points to itself
head = newNode;
} else {
Node* temp = head;
while (temp->next != head) { // Find the last node
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
head = newNode; // Update the head to the new node
}
}
// Insert a node at the end
void insertAtTail(Node*& head, int value) {
Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) {
newNode->next = newNode; // First node points to itself
head = newNode;
} else {
Node* temp = head;
while (temp->next != head) { // Traverse to the last node
temp = temp->next;
}
temp->next = newNode;
newNode->next = head; // Maintain circular property
}
}
// Delete a node with a given key
void deleteNode(Node*& head, int key) {
if (head == nullptr) return; // Empty list
Node* temp = head;
Node* prev = nullptr;
// If the node to be deleted is the head
if (temp->data == key && temp->next == head) {
head = nullptr;
delete temp;
return;
}
// Traverse the list to find the node
do {
if (temp->data == key) {
if (prev == nullptr) { // Deleting head node with multiple elements
Node* last = head;
while (last->next != head) { // Find last node
last = last->next;
}
last->next = head->next;
head = head->next;
} else {
prev->next = temp->next;
}
delete temp;
return;
}
prev = temp;
temp = temp->next;
} while (temp != head);
}
// Display the circular linked list
void display(Node* head) {
if (head == nullptr) {
cout << "List is empty!" << endl;
return;
}
Node* temp = head;
do {
cout << temp->data << " -> ";
temp = temp->next;
} while (temp != head);
cout << "(head)" << endl;
}
// Search for an element in the circular linked list
bool search(Node* head, int key) {
if (head == nullptr) return false;
Node* temp = head;
do {
if (temp->data == key) return true;
temp = temp->next;
} while (temp != head);
return false;
}
// Main function to test the operations
int main() {
Node* head = nullptr;
insertAtTail(head, 10);
insertAtTail(head, 20);
insertAtTail(head, 30);
insertAtHead(head, 5);
cout << "Circular Linked List: ";
display(head);
cout << "Deleting node with value 20..." << endl;
deleteNode(head, 20);
display(head);
cout << "Searching for value 30: "
<< (search(head, 30) ? "Found" : "Not Found") << endl;
cout << "Searching for value 50: "
<< (search(head, 50) ? "Found" : "Not Found") << endl;
return 0;
}
Explanation of the Code
1. Node Structure:
o Each Node contains data and a pointer to the next node.
o For a circular linked list, the last node’s next pointer points back to the head node.
2. Insert at Head:
o Adds a new node at the beginning of the list.
o If the list is empty, the node points to itself.
o If the list is non-empty, we update the pointers to maintain the circular property.
3. Insert at Tail:
o Adds a new node at the end of the list.
o Handles both the empty and non-empty list cases, ensuring the new node points to the
head.
4. Delete a Node:
o Searches for a node with the given value and deletes it.
o Special care is taken for deleting the head node or when the list has only one element.
5. Display Function:
o Traverses the circular linked list, printing all elements until it circles back to the head.
6. Search Function:
o Searches for a specific value in the list, returning true if found, false otherwise.
7. Main Function:
o Demonstrates how to use the above operations by creating a list, displaying it, and
performing insertions, deletions, and searches.
Sample Output:
Circular Linked List: 5 -> 10 -> 20 -> 30 -> (head)
Deleting node with value 20...
5 -> 10 -> 30 -> (head)
Searching for value 30: Found
Searching for value 50: Not Found
