- A circular linked list has a circular structure, where the last node points to the beginning of the list.
- While traversing a circular linked list we can begin at any node and traverse the list until we reach the same node where we have started.
- Thus a circular linked list has no beginning and no end.
- The only drawback of the circular linked list is the complexity of iteration.
- No null values exist in the link part of any node in the list.
- A circular linked list is widely used in operating systems for task maintenance.
- In a circular linked list, the node containing the first node’s address is the list’s last node.
- Insertion and deletion are the primary operations performed on circular linked lists.
- Insertion is done in three ways. Those are the beginning, ending, and middle.
- Deletion is also done in three ways.
Circular Linked List Operations:
- Insertion Operation in CLL.
- Deletion Operation in CLL.
Table of Contents
Insertion Operation:
Three cases exist for an element to be added to the list:
- At the start of CLL
- At the end of the list in CLL
- At a specific location in CLL
Case 1. Insert an element at the Start
- Before inserting a new node at the beginning of a circular linked list, we must create the node and allocate memory for it.
- We set the new node to point to itself if the list is empty, as indicated by the last pointer being NULL.
- If the list already has nodes, we change the last node’s next pointer to link to the new node and set the new node’s next pointer to point to the current head of the list (last->next).
- This keeps the list’s circular form intact.
Code for Insertion of a Node at the Start Location of the List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def push(self, data):
"""Inserts a new node with 'data' at the beginning of the circular linked list."""
new_node = Node(data) # Create the new node
# If the list is empty
if self.head is None:
new_node.next = new_node # Make the new node point to itself
self.head = new_node
return
# Find the last node
temp = self.head
while temp.next != self.head:
temp = temp.next
# Insert the new node after the last node (before the head)
temp.next = new_node
new_node.next = self.head
# Update the head to the new node
self.head = new_node
def printList(self):
"""Prints the data of all nodes in the circular linked list."""
temp = self.head
if self.head is not None:
while True:
print(temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
print()
# Example usage
cllist = CircularLinkedList()
cllist.push(1)
cllist.push(2)
cllist.push(3)
cllist.push(4)
print("Circular Linked List: ")
cllist.printList() # Output: 4 3 2 1 #include <iostream>
using namespace std;
// Node structure for a circular linked list
struct Node {
int data;
Node* next;
};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {} // Constructor
void push(int data) {
// Create the new node
Node* newNode = new Node;
newNode->data = data;
// If the list is empty
if (head == nullptr) {
newNode->next = newNode; // Make the new node point to itself
head = newNode;
return;
}
// Find the last node
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
// Insert the new node after the last node (before the head)
temp->next = newNode;
newNode->next = head;
// Update the head to the new node
head = newNode;
}
void printList() {
Node* temp = head;
if (head != nullptr) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
};
// Example usage
int main() {
CircularLinkedList cllist;
cllist.push(1);
cllist.push(2);
cllist.push(3);
cllist.push(4);
cout << "Circular Linked List: ";
cllist.printList(); // Output: 4 3 2 1
return 0;
}class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head;
public CircularLinkedList() {
head = null;
}
public void push(int data) {
// Create the new node
Node newNode = new Node(data);
// If the list is empty
if (head == null) {
newNode.next = newNode; // Make the new node point to itself
head = newNode;
return;
}
// Find the last node
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
// Insert the new node after the last node (before the head)
temp.next = newNode;
newNode.next = head;
// Update the head to the new node
head = newNode;
}
public void printList() {
Node temp = head;
if (head != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList cllist = new CircularLinkedList();
cllist.push(1);
cllist.push(2);
cllist.push(3);
cllist.push(4);
System.out.print("Circular Linked List: ");
cllist.printList(); // Output: 4 3 2 1
}
}#include <stdio.h>
#include <stdlib.h>
// Structure for a node in a circular linked list
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the beginning of a circular linked list
void push(struct Node** head_ref, int data) {
// Create the new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
// If the list is empty
if (*head_ref == NULL) {
new_node->next = new_node; // Make the new node point to itself
*head_ref = new_node;
return;
}
// Find the last node
struct Node* temp = *head_ref;
while (temp->next != *head_ref) {
temp = temp->next;
}
// Insert the new node after the last node (before the head)
temp->next = new_node;
new_node->next = *head_ref;
// Update the head to the new node
*head_ref = new_node;
}
// Function to print the circular linked list
void printList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
// Example usage
int main() {
struct Node* head = NULL;
push(&head, 1);
push(&head, 2);
push(&head, 3);
push(&head, 4);
printf("Circular Linked List: ");
printList(head); // Output: 4 3 2 1
return 0;
}Case 2. Insert an element at the end of the list
- To insert a new node at the end of a circular linked list, we must first create the node and allocate memory for it.
- To create a circular structure, we begin the list with the new node and make it point to itself if it is empty (mean, last, or tail pointer being NULL).
- If the list is not empty, we make the new node’s next pointer point to the current head node (tail->next) and then modify the current tail node’s next pointer to point to the new node.
- The tail pointer is updated to the new node at the end.
- By doing this, the circular linkage will be preserved and the new node will be guaranteed to be the final node in the list.
Code for Insertion of a Node at the End of the List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
"""Inserts a new node with 'data' at the end of the circular linked list."""
new_node = Node(data) # Create the new node
# If the list is empty, make the new node the head and point to itself
if self.head is None:
new_node.next = new_node
self.head = new_node
return
# Find the last node
last = self.head
while last.next != self.head:
last = last.next
# Insert the new node after the last node
last.next = new_node
new_node.next = self.head
def printList(self):
"""Prints the data of all nodes in the circular linked list."""
temp = self.head
if self.head is not None:
while True:
print(temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
print()
# Example usage:
cllist = CircularLinkedList()
cllist.append(1)
cllist.append(2)
cllist.append(3)
cllist.append(4)
print("Circular Linked List: ")
cllist.printList() # Output: 1 2 3 4 #include <iostream>
using namespace std;
// Node structure for a circular linked list
struct Node {
int data;
Node* next;
};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {} // Constructor
void append(int data) {
// Create the new node
Node* newNode = new Node;
newNode->data = data;
// If the list is empty, make the new node the head and point to itself
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
return;
}
// Find the last node
Node* last = head;
while (last->next != head) {
last = last->next;
}
// Insert the new node after the last node
last->next = newNode;
newNode->next = head;
}
void printList() {
Node* temp = head;
if (head != nullptr) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
};
// Example usage:
int main() {
CircularLinkedList cllist;
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.append(4);
cout << "Circular Linked List: ";
cllist.printList(); // Output: 1 2 3 4
return 0;
}class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head;
public CircularLinkedList() {
head = null;
}
public void append(int data) {
// Create the new node
Node newNode = new Node(data);
// If the list is empty, make the new node the head and point to itself
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
// Find the last node
Node last = head;
while (last.next != head) {
last = last.next;
}
// Insert the new node after the last node
last.next = newNode;
newNode.next = head;
}
public void printList() {
Node temp = head;
if (head != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList cllist = new CircularLinkedList();
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.append(4);
System.out.print("Circular Linked List: ");
cllist.printList(); // Output: 1 2 3 4
}
}#include <stdio.h>
#include <stdlib.h>
// Structure for a node in a circular linked list
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the end of a circular linked list
void append(struct Node** head_ref, int data) {
// Create the new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
// If the list is empty, make the new node the head and point to itself
if (*head_ref == NULL) {
new_node->next = new_node;
*head_ref = new_node;
return;
}
// Find the last node
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// Insert the new node after the last node
last->next = new_node;
new_node->next = *head_ref;
}
// Function to print the circular linked list
void printList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
// Example usage
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
append(&head, 4);
printf("Circular Linked List: ");
printList(head); // Output: 1 2 3 4
return 0;
}Case 3. Insert an element at a specific location
- Before inserting a new node into a circular linked list at a designated position, we ensure the list is not empty.
- The position doesn’t exist in the list, therefore if it does and the position is not 1, we output an error message.
- The new node is created and set to point to itself if the position is 1.
- We build the new node and search the list for the appropriate insertion position if the list is not empty.
- We add the new node at the beginning by modifying the pointers if the position is 1.
- To add a new node in a particular place, we modify the pointers and iterate through the list until we find the correct spot.
- To preserve the list’s circular shape, if a new node is added at the end, we also change the last pointer to point to the new node.
Code for Insertion of a Node at the Specific Location of the List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
"""Inserts a new node with 'data' at the end of the circular linked list."""
new_node = Node(data) # Create the new node
# If the list is empty, make the new node the head and point to itself
if self.head is None:
new_node.next = new_node
self.head = new_node
return
# Find the last node
last = self.head
while last.next != self.head:
last = last.next
# Insert the new node after the last node
last.next = new_node
new_node.next = self.head
def insert_at_position(self, data, position):
"""Inserts a new node with 'data' at the specified 'position' in the circular linked list."""
# 1. Create the new node
new_node = Node(data)
# 2. If the list is empty, make the new node the head and point to itself
if self.head is None:
new_node.next = new_node
self.head = new_node
return
# 3. If inserting at position 0, handle it like inserting at the beginning
if position == 0:
# Find the last node
last = self.head
while last.next != self.head:
last = last.next
# Insert the new node before the head
new_node.next = self.head
last.next = new_node
self.head = new_node
return
# 4. Traverse to the node before the desired position
temp = self.head
count = 0
while count < position - 1 and temp.next != self.head:
temp = temp.next
count += 1
# 5. If the position is invalid (beyond the list length), do nothing
if count != position - 1:
print("Invalid position")
return
# 6. Insert the new node at the desired position
new_node.next = temp.next
temp.next = new_node
def printList(self):
"""Prints the data of all nodes in the circular linked list."""
temp = self.head
if self.head is not None:
while True:
print(temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
print()
# Example usage:
cllist = CircularLinkedList()
cllist.append(1)
cllist.append(2)
cllist.append(3)
cllist.insert_at_position(4, 2) # Insert 4 at position 2
cllist.printList() # Output: 1 2 4 3 #include <iostream>
using namespace std;
// Node structure for a circular linked list
struct Node {
int data;
Node* next;
};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {} // Constructor
void append(int data) {
// Create the new node
Node* newNode = new Node;
newNode->data = data;
// If the list is empty, make the new node the head and point to itself
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
return;
}
// Find the last node
Node* last = head;
while (last->next != head) {
last = last->next;
}
// Insert the new node after the last node
last->next = newNode;
newNode->next = head;
}
void insertAtPosition(int data, int position) {
// 1. Create the new node
Node* newNode = new Node;
newNode->data = data;
// 2. If the list is empty, make the new node the head and point to itself
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
return;
}
// 3. If inserting at position 0, handle it like inserting at the beginning
if (position == 0) {
// Find the last node
Node* last = head;
while (last->next != head) {
last = last->next;
}
// Insert the new node before the head
newNode->next = head;
last->next = newNode;
head = newNode;
return;
}
// 4. Traverse to the node before the desired position
Node* temp = head;
int count = 0;
while (count < position - 1 && temp->next != head) {
temp = temp->next;
count++;
}
// 5. If the position is invalid (beyond the list length), do nothing
if (count != position - 1) {
cout << "Invalid position" << endl;
return;
}
// 6. Insert the new node at the desired position
newNode->next = temp->next;
temp->next = newNode;
}
void printList() {
Node* temp = head;
if (head != nullptr) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
};
// Example usage:
int main() {
CircularLinkedList cllist;
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.insertAtPosition(4, 2); // Insert 4 at position 2
cllist.printList(); // Output: 1 2 4 3
return 0;
}class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head;
public CircularLinkedList() {
head = null;
}
// Function to insert a new node at the end of the circular linked list
public void append(int data) {
// Create the new node
Node newNode = new Node(data);
// If the list is empty, make the new node the head and point to itself
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
// Find the last node
Node last = head;
while (last.next != head) {
last = last.next;
}
// Insert the new node after the last node
last.next = newNode;
newNode.next = head;
}
// Function to insert a new node at a given position in the circular linked list
public void insertAtPosition(int data, int position) {
// 1. Create the new node
Node newNode = new Node(data);
// 2. If the list is empty, make the new node the head and point to itself
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
// 3. If inserting at position 0, handle it like inserting at the beginning
if (position == 0) {
// Find the last node
Node last = head;
while (last.next != head) {
last = last.next;
}
// Insert the new node before the head
newNode.next = head;
last.next = newNode;
head = newNode;
return;
}
// 4. Traverse to the node before the desired position
Node temp = head;
int count = 0;
while (count < position - 1 && temp.next != head) {
temp = temp.next;
count++;
}
// 5. If the position is invalid (beyond the list length), do nothing
if (count != position - 1) {
System.out.println("Invalid position");
return;
}
// 6. Insert the new node at the desired position
newNode.next = temp.next;
temp.next = newNode;
}
// Function to print the circular linked list
public void printList() {
Node temp = head;
if (head != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList cllist = new CircularLinkedList();
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.insertAtPosition(4, 2); // Insert 4 at position 2
cllist.printList(); // Output: 1 2 4 3
}
}#include <stdio.h>
#include <stdlib.h>
// Structure for a node in a circular linked list
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the end of a circular linked list
void append(struct Node** head_ref, int data) {
// Create the new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
// If the list is empty, make the new node the head and point to itself
if (*head_ref == NULL) {
new_node->next = new_node;
*head_ref = new_node;
return;
}
// Find the last node
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// Insert the new node after the last node
last->next = new_node;
new_node->next = *head_ref;
}
// Function to insert a new node at a given position in the circular linked list
void insertAtPosition(struct Node** head_ref, int data, int position) {
// 1. Create the new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
// 2. If the list is empty, make the new node the head and point to itself
if (*head_ref == NULL) {
new_node->next = new_node;
*head_ref = new_node;
return;
}
// 3. If inserting at position 0, handle it like inserting at the beginning
if (position == 0) {
// Find the last node
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// Insert the new node before the head
new_node->next = *head_ref;
last->next = new_node;
*head_ref = new_node;
return;
}
// 4. Traverse to the node before the desired position
struct Node* temp = *head_ref;
int count = 0;
while (count < position - 1 && temp->next != *head_ref) {
temp = temp->next;
count++;
}
// 5. If the position is invalid (beyond the list length), do nothing
if (count != position - 1) {
printf("Invalid position\n");
return;
}
// 6. Insert the new node at the desired position
new_node->next = temp->next;
temp->next = new_node;
}
// Function to print the circular linked list
void printList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
// Example usage
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
insertAtPosition(&head, 4, 2); // Insert 4 at position 2
printList(head); // Output: 1 2 4 3
return 0;
}Deletion Operation
Eliminating a component from the list without compromising the list’s integrity is called deleting the component.
Three scenarios exist for placing an element from the list:
- Remove the first node from the list in the CLL.
- Eliminate the last node in the list in the CLL.
- Remove a node from a specific location in the CLL.
Case 1: Delete a Node at the Start in the List
- A circular linked list’s initial node can be deleted by first determining if the list is empty.
- If so, we return NULL and display a notice. We remove the node and set the last pointer to NULL if the list only has one node (the head is the same as the final).
- If there is more than one node, the head node is skipped and essentially removed from the list by updating the last->next reference.
- Next, to release the memory allotted, we remove the head node.
- We conclude by returning the revised last pointer, which remains connected to the list’s final node.
Code for Delete a Node at the Start of the List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
"""Inserts a new node with 'data' at the end of the circular linked list."""
new_node = Node(data)
if self.head is None:
new_node.next = new_node
self.head = new_node
return
last = self.head
while last.next != self.head:
last = last.next
last.next = new_node
new_node.next = self.head
def delete_at_beginning(self):
"""Deletes the node at the beginning (head) of the circular linked list."""
# 1. If the list is empty, do nothing
if self.head is None:
return
# 2. If the list has only one node, set head to None
if self.head.next == self.head:
self.head = None
return
# 3. Find the last node
last = self.head
while last.next != self.head:
last = last.next
# 4. Update the head to the second node
self.head = self.head.next
# 5. Update the last node's next to point to the new head
last.next = self.head
def printList(self):
"""Prints the data of all nodes in the circular linked list."""
temp = self.head
if self.head is not None:
while True:
print(temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
print()
# Example usage:
cllist = CircularLinkedList()
cllist.append(1)
cllist.append(2)
cllist.append(3)
cllist.append(4)
print("Original Circular Linked List: ")
cllist.printList() # Output: 1 2 3 4
cllist.delete_at_beginning()
print("Modified Circular Linked List: ")
cllist.printList() # Output: 2 3 4#include <iostream>
using namespace std;
// Node structure for a circular linked list
struct Node {
int data;
Node* next;
};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {} // Constructor
// Function to insert a new node at the end of the circular linked list
void append(int data) {
// Create the new node
Node* newNode = new Node;
newNode->data = data;
// If the list is empty, make the new node the head and point to itself
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
return;
}
// Find the last node
Node* last = head;
while (last->next != head) {
last = last->next;
}
// Insert the new node after the last node
last->next = newNode;
newNode->next = head;
}
// Function to delete the node at the beginning of the circular linked list
void deleteAtBeginning() {
// 1. If the list is empty, do nothing
if (head == nullptr) {
return;
}
// 2. If the list has only one node, set head to NULL
if (head->next == head) {
delete head;
head = nullptr;
return;
}
// 3. Find the last node
Node* last = head;
while (last->next != head) {
last = last->next;
}
// 4. Store the head node to be deleted
Node* temp = head;
// 5. Update the head to the second node
head = head->next;
// 6. Update the last node's next to point to the new head
last->next = head;
// 7. Delete the old head node
delete temp;
}
// Function to print the circular linked list
void printList() {
Node* temp = head;
if (head != nullptr) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
};
// Example usage
int main() {
CircularLinkedList cllist;
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.append(4);
cout << "Original Circular Linked List: ";
cllist.printList(); // Output: 1 2 3 4
cllist.deleteAtBeginning();
cout << "Modified Circular Linked List: ";
cllist.printList(); // Output: 2 3 4
return 0;
}class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head;
public CircularLinkedList() {
head = null;
}
// Function to insert a new node at the end of the circular linked list
public void append(int data) {
// Create the new node
Node newNode = new Node(data);
// If the list is empty, make the new node the head and point to itself
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
// Find the last node
Node last = head;
while (last.next != head) {
last = last.next;
}
// Insert the new node after the last node
last.next = newNode;
newNode.next = head;
}
// Function to delete the node at the beginning of the circular linked list
public void deleteAtBeginning() {
// 1. If the list is empty, do nothing
if (head == null) {
return;
}
// 2. If the list has only one node, set head to null
if (head.next == head) {
head = null;
return;
}
// 3. Find the last node
Node last = head;
while (last.next != head) {
last = last.next;
}
// 4. Update the head to the second node
head = head.next;
// 5. Update the last node's next to point to the new head
last.next = head;
}
// Function to print the circular linked list
public void printList() {
Node temp = head;
if (head != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList cllist = new CircularLinkedList();
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.append(4);
System.out.print("Original Circular Linked List: ");
cllist.printList(); // Output: 1 2 3 4
cllist.deleteAtBeginning();
System.out.print("Modified Circular Linked List: ");
cllist.printList(); // Output: 2 3 4
}
}#include <stdio.h>
#include <stdlib.h>
// Structure for a node in a circular linked list
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the end of a circular linked list
void append(struct Node** head_ref, int data) {
// Create the new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
// If the list is empty, make the new node the head and point to itself
if (*head_ref == NULL) {
new_node->next = new_node;
*head_ref = new_node;
return;
}
// Find the last node
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// Insert the new node after the last node
last->next = new_node;
new_node->next = *head_ref;
}
// Function to delete the node at the beginning of the circular linked list
void deleteAtBeginning(struct Node** head_ref) {
// 1. If the list is empty, do nothing
if (*head_ref == NULL) {
return;
}
// 2. If the list has only one node, set head to NULL
if ((*head_ref)->next == *head_ref) {
free(*head_ref);
*head_ref = NULL;
return;
}
// 3. Find the last node
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// 4. Store the head node to be deleted
struct Node* temp = *head_ref;
// 5. Update the head to the second node
*head_ref = (*head_ref)->next;
// 6. Update the last node's next to point to the new head
last->next = *head_ref;
// 7. Free the memory occupied by the deleted node
free(temp);
}
// Function to print the circular linked list
void printList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
// Example usage:
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
append(&head, 4);
printf("Original Circular Linked List: ");
printList(head); // Output: 1 2 3 4
deleteAtBeginning(&head);
printf("Modified Circular Linked List: ");
printList(head); // Output: 2 3 4
return 0;
}Case 2: Delete a node at the end of the list
- In a circular linked list, we must first determine whether the list is empty before deleting the final node. If so, we return nullptr and display a message.
- We remove the node and set last to nullptr if the list only has one node (where the head and last are identical).
- In multi-node lists, we must search through the list to locate the second-to-last node.
- To do this, we go through the list beginning at the head and ending at the node whose next pointer points to the last.
- The final node is effectively detached from the list by locating the previous node and modifying its next pointer to connect to the head.
- To free up memory, we remove the final node and return the revised last pointer, which now links to the final node.
Code for Delete a Node at the End of the List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
"""Inserts a new node with 'data' at the end of the circular linked list."""
new_node = Node(data)
if self.head is None:
new_node.next = new_node
self.head = new_node
return
last = self.head
while last.next != self.head:
last = last.next
last.next = new_node
new_node.next = self.head
def delete_at_end(self):
"""Deletes the node at the end of the circular linked list."""
# 1. If the list is empty, do nothing
if self.head is None:
return
# 2. If the list has only one node, set head to None
if self.head.next == self.head:
self.head = None
return
# 3. Traverse to the second to last node
second_last = self.head
while second_last.next.next != self.head:
second_last = second_last.next
# 4. Set the next of the second to last node to head, effectively deleting the last node
second_last.next = self.head
def printList(self):
"""Prints the data of all nodes in the circular linked list."""
temp = self.head
if self.head is not None:
while True:
print(temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
print()
# Example usage:
cllist = CircularLinkedList()
cllist.append(1)
cllist.append(2)
cllist.append(3)
cllist.append(4)
print("Original Circular Linked List: ")
cllist.printList() # Output: 1 2 3 4
cllist.delete_at_end()
print("Modified Circular Linked List: ")
cllist.printList() # Output: 1 2 3 #include <iostream>
using namespace std;
// Node structure for a circular linked list
struct Node {
int data;
Node* next;
};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {} // Constructor
// Function to insert a new node at the end of the circular linked list
void append(int data) {
// Create the new node
Node* newNode = new Node;
newNode->data = data;
// If the list is empty, make the new node the head and point to itself
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
return;
}
// Find the last node
Node* last = head;
while (last->next != head) {
last = last->next;
}
// Insert the new node after the last node
last->next = newNode;
newNode->next = head;
}
// Function to delete the node at the end of the circular linked list
void deleteAtEnd() {
// 1. If the list is empty, do nothing
if (head == nullptr) {
return;
}
// 2. If the list has only one node, set head to NULL
if (head->next == head) {
delete head;
head = nullptr;
return;
}
// 3. Find the second to last node
Node* secondLast = head;
while (secondLast->next->next != head) {
secondLast = secondLast->next;
}
// 4. Store the last node to be deleted
Node* temp = secondLast->next;
// 5. Update the next of the second to last node to head
secondLast->next = head;
// 6. Delete the last node
delete temp;
}
// Function to print the circular linked list
void printList() {
Node* temp = head;
if (head != nullptr) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
};
// Example usage:
int main() {
CircularLinkedList cllist;
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.append(4);
cout << "Original Circular Linked List: ";
cllist.printList(); // Output: 1 2 3 4
cllist.deleteAtEnd();
cout << "Modified Circular Linked List: ";
cllist.printList(); // Output: 1 2 3
return 0;
}class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head;
public CircularLinkedList() {
head = null;
}
// Function to insert a new node at the end of the circular linked list
public void append(int data) {
// Create the new node
Node newNode = new Node(data);
// If the list is empty, make the new node the head and point to itself
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
// Find the last node
Node last = head;
while (last.next != head) {
last = last.next;
}
// Insert the new node after the last node
last.next = newNode;
newNode.next = head;
}
// Function to delete the node at the end of the circular linked list
public void deleteAtEnd() {
// 1. If the list is empty, do nothing
if (head == null) {
return;
}
// 2. If the list has only one node, set head to null
if (head.next == head) {
head = null;
return;
}
// 3. Find the second to last node
Node secondLast = head;
while (secondLast.next.next != head) {
secondLast = secondLast.next;
}
// 4. Set the next of the second to last node to head
secondLast.next = head;
}
// Function to print the circular linked list
public void printList() {
Node temp = head;
if (head != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList cllist = new CircularLinkedList();
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.append(4);
System.out.print("Original Circular Linked List: ");
cllist.printList(); // Output: 1 2 3 4
cllist.deleteAtEnd();
System.out.print("Modified Circular Linked List: ");
cllist.printList(); // Output: 1 2 3
}
}#include <stdio.h>
#include <stdlib.h>
// Structure for a node in a circular linked list
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the end of a circular linked list
void append(struct Node** head_ref, int data) {
// Create the new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
// If the list is empty, make the new node the head and point to itself
if (*head_ref == NULL) {
new_node->next = new_node;
*head_ref = new_node;
return;
}
// Find the last node
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// Insert the new node after the last node
last->next = new_node;
new_node->next = *head_ref;
}
// Function to delete the node at the end of the circular linked list
void deleteAtEnd(struct Node** head_ref) {
// 1. If the list is empty, do nothing
if (*head_ref == NULL) {
return;
}
// 2. If the list has only one node, set head to NULL
if ((*head_ref)->next == *head_ref) {
free(*head_ref);
*head_ref = NULL;
return;
}
// 3. Find the second to last node
struct Node* second_last = *head_ref;
while (second_last->next->next != *head_ref) {
second_last = second_last->next;
}
// 4. Free the last node
free(second_last->next);
// 5. Set the next of the second to last node to head
second_last->next = *head_ref;
}
// Function to print the circular linked list
void printList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
// Example usage:
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
append(&head, 4);
printf("Original Circular Linked List: ");
printList(head); // Output: 1 2 3 4
deleteAtEnd(&head);
printf("Modified Circular Linked List: ");
printList(head); // Output: 1 2 3
return 0;
}Case 3: Delete a node at a specific location in the List
- We first verify that the circular linked list is empty before deleting a particular node. If so, we return nullptr and display a message.
- If the list contains only one node and it matches the key, we remove the node and set the last pointer to null.
- We change the last node’s next pointer to skip the head node and remove it if the first node is the one that has to be erased.
- We use two pointers to navigate the list in search of additional nodes: curr to locate the node and prev to remember it before the node.
- If the node with the matching key is located, we change the previous node’s next pointer to bypass and remove the current node.
- We change the last pointer appropriately if the node is located and turns out to be the final node.
- Do nothing and either tail or continue as is if the node cannot be located.
- Lastly, we give back the most recent updated pointer.
Code for Delete a Node at a Specific Location in the List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def append(self, data):
"""Inserts a new node with 'data' at the end of the circular linked list."""
new_node = Node(data)
if self.head is None:
new_node.next = new_node
self.head = new_node
return
last = self.head
while last.next != self.head:
last = last.next
last.next = new_node
new_node.next = self.head
def delete_at_position(self, position):
"""Deletes the node at the specified 'position' in the circular linked list."""
# 1. If the list is empty, do nothing
if self.head is None:
return
# 2. If the position is 0, handle it like deleting at the beginning
if position == 0:
# If only one node, set head to None
if self.head.next == self.head:
self.head = None
return
# Find the last node
last = self.head
while last.next != self.head:
last = last.next
# Update head and last node's next
self.head = self.head.next
last.next = self.head
return
# 3. Traverse to the node before the node to be deleted
temp = self.head
count = 0
while count < position - 1 and temp.next != self.head:
temp = temp.next
count += 1
# 4. If the position is invalid, do nothing
if temp.next == self.head or count != position - 1:
print("Invalid position")
return
# 5. Store the node to be deleted
node_to_delete = temp.next
# 6. Update the next pointer of the previous node
temp.next = node_to_delete.next
# 7. Delete the node
del node_to_delete
def printList(self):
"""Prints the data of all nodes in the circular linked list."""
temp = self.head
if self.head is not None:
while True:
print(temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
print()
# Example usage:
cllist = CircularLinkedList()
cllist.append(1)
cllist.append(2)
cllist.append(3)
cllist.append(4)
print("Original Circular Linked List: ")
cllist.printList() # Output: 1 2 3 4
cllist.delete_at_position(2) # Delete node at position 2
print("Modified Circular Linked List: ")
cllist.printList() # Output: 1 2 4#include <iostream>
using namespace std;
// Node structure for a circular linked list
struct Node {
int data;
Node* next;
};
class CircularLinkedList {
public:
Node* head;
CircularLinkedList() : head(nullptr) {} // Constructor
// Function to insert a new node at the end of the circular linked list
void append(int data) {
// Create the new node
Node* newNode = new Node;
newNode->data = data;
// If the list is empty, make the new node the head and point to itself
if (head == nullptr) {
newNode->next = newNode;
head = newNode;
return;
}
// Find the last node
Node* last = head;
while (last->next != head) {
last = last->next;
}
// Insert the new node after the last node
last->next = newNode;
newNode->next = head;
}
// Function to delete the node at the specified position
void deleteAtPosition(int position) {
// 1. If the list is empty, do nothing
if (head == nullptr) {
return;
}
// 2. If the position is 0, handle it like deleting at the beginning
if (position == 0) {
// If only one node, set head to NULL
if (head->next == head) {
delete head;
head = nullptr;
return;
}
// Find the last node
Node* last = head;
while (last->next != head) {
last = last->next;
}
// Store the head node to be deleted
Node* temp = head;
// Update head to the second node
head = head->next;
// Update last node's next to point to the new head
last->next = head;
// Delete the old head node
delete temp;
return;
}
// 3. Traverse to the node before the node to be deleted
Node* temp = head;
int count = 0;
while (count < position - 1 && temp->next != head) {
temp = temp->next;
count++;
}
// 4. If the position is invalid, do nothing
if (temp->next == head || count != position - 1) {
cout << "Invalid position" << endl;
return;
}
// 5. Store the node to be deleted
Node* toDelete = temp->next;
// 6. Update the next pointer of the previous node
temp->next = toDelete->next;
// 7. Delete the node
delete toDelete;
}
// Function to print the circular linked list
void printList() {
Node* temp = head;
if (head != nullptr) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
cout << endl;
}
};
// Example usage:
int main() {
CircularLinkedList cllist;
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.append(4);
cout << "Original Circular Linked List: ";
cllist.printList(); // Output: 1 2 3 4
cllist.deleteAtPosition(2); // Delete node at position 2
cout << "Modified Circular Linked List: ";
cllist.printList(); // Output: 1 2 4
return 0;
}class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head;
public CircularLinkedList() {
head = null;
}
// Function to insert a new node at the end of the circular linked list
public void append(int data) {
// Create the new node
Node newNode = new Node(data);
// If the list is empty, make the new node the head and point to itself
if (head == null) {
newNode.next = newNode;
head = newNode;
return;
}
// Find the last node
Node last = head;
while (last.next != head) {
last = last.next;
}
// Insert the new node after the last node
last.next = newNode;
newNode.next = head;
}
// Function to delete the node at the specified position
public void deleteAtPosition(int position) {
// 1. If the list is empty, do nothing
if (head == null) {
return;
}
// 2. If the position is 0, handle it like deleting at the beginning
if (position == 0) {
// If only one node, set head to null
if (head.next == head) {
head = null;
return;
}
// Find the last node
Node last = head;
while (last.next != head) {
last = last.next;
}
// Update head to the second node
head = head.next;
// Update last node's next to point to the new head
last.next = head;
return;
}
// 3. Traverse to the node before the node to be deleted
Node temp = head;
int count = 0;
while (count < position - 1 && temp.next != head) {
temp = temp.next;
count++;
}
// 4. If the position is invalid, do nothing
if (temp.next == head || count != position - 1) {
System.out.println("Invalid position");
return;
}
// 5. Update the next pointer of the previous node to skip the node to be deleted
temp.next = temp.next.next;
}
// Function to print the circular linked list
public void printList() {
Node temp = head;
if (head != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList cllist = new CircularLinkedList();
cllist.append(1);
cllist.append(2);
cllist.append(3);
cllist.append(4);
System.out.print("Original Circular Linked List: ");
cllist.printList(); // Output: 1 2 3 4
cllist.deleteAtPosition(2); // Delete node at position 2
System.out.print("Modified Circular Linked List: ");
cllist.printList(); // Output: 1 2 4
}
}#include <stdio.h>
#include <stdlib.h>
// Structure for a node in a circular linked list
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the end of a circular linked list
void append(struct Node** head_ref, int data) {
// Create the new node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
// If the list is empty, make the new node the head and point to itself
if (*head_ref == NULL) {
new_node->next = new_node;
*head_ref = new_node;
return;
}
// Find the last node
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// Insert the new node after the last node
last->next = new_node;
new_node->next = *head_ref;
}
// Function to delete the node at the specified position in the circular linked list
void deleteAtPosition(struct Node** head_ref, int position) {
// 1. If the list is empty, do nothing
if (*head_ref == NULL) {
return;
}
// 2. If the position is 0, handle it like deleting at the beginning
if (position == 0) {
// If only one node, set head to NULL
if ((*head_ref)->next == *head_ref) {
free(*head_ref);
*head_ref = NULL;
return;
}
// Find the last node
struct Node* last = *head_ref;
while (last->next != *head_ref) {
last = last->next;
}
// Store the head node to be deleted
struct Node* temp = *head_ref;
// Update head to the second node
*head_ref = (*head_ref)->next;
// Update last node's next to point to the new head
last->next = *head_ref;
// Free the memory occupied by the deleted node
free(temp);
return;
}
// 3. Traverse to the node before the node to be deleted
struct Node* temp = *head_ref;
int count = 0;
while (count < position - 1 && temp->next != *head_ref) {
temp = temp->next;
count++;
}
// 4. If the position is invalid, do nothing
if (temp->next == *head_ref || count != position - 1) {
printf("Invalid position\n");
return;
}
// 5. Store the node to be deleted
struct Node* toDelete = temp->next;
// 6. Update the next pointer of the previous node
temp->next = toDelete->next;
// 7. Free the memory occupied by the deleted node
free(toDelete);
}
// Function to print the circular linked list
void printList(struct Node* head) {
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
printf("\n");
}
// Example usage:
int main() {
struct Node* head = NULL;
append(&head, 1);
append(&head, 2);
append(&head, 3);
append(&head, 4);
printf("Original Circular Linked List: ");
printList(head); // Output: 1 2 3 4
deleteAtPosition(&head, 2); // Delete node at position 2
printf("Modified Circular Linked List: ");
printList(head); // Output: 1 2 4
return 0;
}Complexity Analysis of Circular Linked List Operations
| Operation | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity |
| Insertion | |||
| – At Beginning | O(1) | O(1) | O(1) |
| – At End | O(n) | O(n) | O(1) |
| – After Given Node | O(1) | O(1) | O(1) |
| Deletion | |||
| – At Beginning | O(1) | O(1) | O(1) |
| – At End | O(n) | O(n) | O(1) |
| – At Given Position | O(n) | O(n) | O(1) |
| Traversal | O(n) | O(n) | O(1) |
| Search | O(n) | O(n) | O(1) |
| Space Used (Overall) | – | – | O(n) |
Related FAQs:
1. Why Use a Circular Linked List?
- Circular linked lists offer advantages in certain scenarios:
- Efficient Circular Traversal: You can traverse the entire list repeatedly without resetting the pointer.
- Resource Management: Round-robin scheduling can manage resources like CPUs, where processes cyclically take turns.
2. How is a Circular Linked List Implemented?
- Like a singly linked list, each node in this structure contains data and a “next” pointer.
- The key difference is that the “next” pointer of the last node points back to the head node.
3. What are the Advantages of a Circular Linked List Over a Singly Linked List?
- Circular Traversal: Traversing the entire list multiple times is more efficient and easier.
- Faster Deletion at the End: Deleting the last node in a circular linked list is usually an O(1) operation, compared to O(n) in a singly linked list.
4. What are Some Real-World Applications of Circular Linked Lists?
- Circular linked lists are used in
- CPU Scheduling: Implementing round-robin scheduling algorithms.
- Memory Management: Managing free blocks of memory.
- Multiplayer Games: Keeping track of player turns in a round-based game.
5. How Do You Detect a Loop in a Circular Linked List?
- Although circular linked lists are inherently cyclic, you might find it useful to identify any unintended loops within the list.
- Floyd’s Cycle Finding Algorithm (“tortoise and hare” algorithm) can be used to detect any unintended loops.
6. How Do You Insert a Node at the Beginning of a Circular Linked List?
- The process is similar to inserting at the beginning of a singly linked list, but you must ensure that the “next” pointer of the last node is updated to point to the new head.
7. How Do You Delete a Node from a Circular Linked List?
- Deleting a node requires careful handling of the “next” pointers, especially when deleting the head node.
- You need to ensure the circular structure is maintained.
8. What is the Time Complexity of Operations in a Circular Linked List?
- The time complexities for most operations, including insertion, deletion, and search, are similar to those of a singly linked list.
- Unlike singly linked lists, where deleting the last node requires O(n) time, deleting the final node in a circular linked list is typically an O(1) operation.
9. Are There Different Types of Circular Linked Lists?
- Yes, you can have:
- Circular Singly Linked List: The classic type where each node points to the next.
- Circular Doubly Linked List: Each node has pointers to the next and previous nodes, allowing for traversal in both directions.