INTRODUCTION OF CIRCULAR LINK LIST
A circular linked
list is a variation of a linear linked list in which the last node points back
to the first node instead of containing a null reference called a circular
structure.
Each node has a
link or a pointer to the next node in the sequence, and the last node points
back to the first node.
Key
characteristics of a circular linked list:
1. Circular
Structure:
- Unlike a linear linked list, where the
last node points to null, in a circular linked list, the last node's link
points back to the first node, creating a loop or cycle.
2. Traversal:
- Traversal in a circular linked list
involves starting from any node and moving through the nodes sequentially until
reaching the starting node again. The loop continues indefinitely.
3. Insertions and
Deletions:
- Insertions and deletions in a circular
linked list are similar to those in a linear linked list. However, special care
is needed to update the link of the last node when inserting or deleting nodes.
4. Representation:
- A circular linked list can be represented
using a structure or a class that contains a data field and a link or pointer
field pointing to the next node in the sequence.
5. Head Pointer:
- In a circular linked list, the concept of
a "head" is not as strictly defined as in a linear linked list. Any
node can serve as a starting point for traversal.
6. Applications:
- Circular linked lists are used in
applications where cyclic behavior is natural, such as in round-robin
scheduling algorithms, where tasks are performed in a circular sequence.
-----------------------------------------------------------------------
Structure of a Circular linked Node:
Algorithm: CircularLinkedListNode
1. Create a
structure/class for the node:
- Define a structure/class named Node.
- Include two fields: data (to store the
value of the node) and next (a reference to the next node).
2. Initialize a
node:
- Create a function/method named
createCircularNode(data) that takes the data for the node as a parameter.
- Inside the function:
- Create a new node.
- Set the data field of the node to the
provided data.
- Set the next field to point to the node
itself.
Example (in Python):
class Node:
def __init__(self, data):
self.data = data
self.next = self # Initialize next to point to itself
def createCircularNode(data):
return Node(data)
example:- (c++)
struct Node {
int data;
Node* next;
};
Operations on Circular Linked List:
Insertion: The insertion
operation can be performed in three ways.
·
Inserting
At the Beginning of the list
·
Inserting at the end of the list
·
Inserting a specific location in the list
Deletion: The deletion
operation can be performed in three ways.
They are as
follows…
·
Deleting
from the Beginning of the list
·
Deleting
from the End of the list
·
Deleting
a Specific Node
Search: It is a
process of determining and retrieving a specific node either from the front,
the end or anywhere in the list.
Display: This process displays the elements of a Single-linked list.
Updating: -
Detailed
Insertion
Algorithm of
Insertion at the beginning of the circular link list.
To insert a node
at the beginning of a circular linked list, you need to follow these steps:
1. Create a new
node with the given data.
2. If the circular
linked list is empty, set the next pointer of the new node to itself.
3. If the circular
linked list is not empty, find the last node in the list.
4. Set the next
pointer of the last node to the new node.
5. Set the next
pointer of the new node to the head of the circular linked list.
pseudocode:
Algorithm
insertAtBeginningCircularLinkedList(data):
1. Create a new node newNode with the given
data.
2. If the head is NULL (indicating an empty
circular linked list):
2.1 Set newNode.next to newNode
(pointing to itself).
2.2 Set head to newNode.
3. Else (circular linked list is not
empty):
3.1 Find the last node in the circular
linked list. Let's call it lastNode.
3.2 Set lastNode.next to newNode.
3.3 Set newNode.next to the head.
3.4 Set head to newNode.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
};
// Function to
insert at the beginning of a circular linked list
Node*
insertAtBeginning(Node* head, int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = newNode;
if (head == nullptr) {
head = newNode;
} else {
Node* lastNode = head;
while (lastNode->next != head) {
lastNode = lastNode->next;
}
lastNode->next = newNode;
newNode->next = head;
head = newNode;
}
return head;
}
// Function to
display the circular linked list
void
displayList(Node* head) {
if (head == nullptr) {
std::cout << "Circular
linked list is empty." << std::endl;
return;
}
Node* current = head;
do {
std::cout << current->data
<< " ";
current = current->next;
} while (current != head);
std::cout << std::endl;
}
int main() {
Node* head = nullptr;
// Insert at the beginning
head = insertAtBeginning(head, 3);
head = insertAtBeginning(head, 2);
head = insertAtBeginning(head, 1);
// Display the circular linked list
std::cout << "Circular Linked
List: ";
displayList(head);
return 0;
}
Output (C++):
Circular Linked
List: 1 2 3
----------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
insert at the beginning of a circular linked list
def
insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = new_node
if head is None:
head = new_node
else:
last_node = head
while last_node.next != head:
last_node = last_node.next
last_node.next = new_node
new_node.next = head
head = new_node
return head
# Function to
display the circular linked list
def
display_list(head):
if head is None:
print("Circular linked list is
empty.")
return
current = head
while True:
print(current.data, end=" ")
current = current.next
if current == head:
break
print()
# Main function
if __name__ ==
"__main__":
head = None
# Insert at the beginning
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# Display the circular linked list
print("Circular Linked List:",
end=" ")
display_list(head)
Output (Python):
Circular Linked
List: 1 2 3
------------------------------------------
Insert a node at
the end of a circular linked list:-
Follow these
steps:
1. Create a new
node with the given data.
2. If the circular
linked list is empty, set the next pointer of the new node to itself and update
the head.
3. If the circular
linked list is not empty, find the last node in the list.
4. Set the next
pointer of the last node to the new node.
5. Set the next
pointer of the new node to the head of the circular linked list.
pseudocode:
Algorithm
insertAtEndCircularLinkedList(data):
1. Create a new node newNode with the given
data.
2. If head is NULL (indicating an empty
circular linked list):
2.1 Set newNode.next to newNode
(pointing to itself).
2.2 Set head to newNode.
3. Else (circular linked list is not
empty):
3.1 Find the last node in the circular
linked list. Let's call it lastNode.
3.2 Set lastNode.next to newNode.
3.3 Set newNode.next to head.
C++ Example:cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
};
// Function to
insert at the end of a circular linked list
Node*
insertAtEnd(Node* head, int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = newNode;
if (head == nullptr) {
head = newNode;
} else {
Node* lastNode = head;
while (lastNode->next != head) {
lastNode = lastNode->next;
}
lastNode->next = newNode;
newNode->next = head;
}
return head;
}
// Function to
display the circular linked list
void
displayList(Node* head) {
if (head == nullptr) {
std::cout << "Circular
linked list is empty." << std::endl;
return;
}
Node* current = head;
do {
std::cout << current->data
<< " ";
current = current->next;
} while (current != head);
std::cout << std::endl;
}
int main() {
Node* head = nullptr;
// Insert at the end
head = insertAtEnd(head, 1);
head = insertAtEnd(head, 2);
head = insertAtEnd(head, 3);
// Display the circular linked list
std::cout << "Circular Linked
List: ";
displayList(head);
return 0;
}
Output (C++):
Circular Linked
List: 1 2 3
--------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
insert at the end of a circular linked list
def
insert_at_end(head, data):
new_node = Node(data)
new_node.next = new_node
if head is None:
head = new_node
else:
last_node = head
while last_node.next != head:
last_node = last_node.next
last_node.next = new_node
new_node.next = head
return head
# Function to
display the circular linked list
def
display_list(head):
if head is None:
print("Circular linked list is
empty.")
return
current = head
while True:
print(current.data, end=" ")
current = current.next
if current == head:
break
print()
# Main function
if __name__ ==
"__main__":
head = None
# Insert at the end
head = insert_at_end(head, 1)
head = insert_at_end(head, 2)
head = insert_at_end(head, 3)
# Display the circular linked list
print("Circular Linked List:",
end=" ")
display_list(head)
Output (Python):
Circular Linked
List: 1 2 3
--------------------------------------------------
Algorithm of Inserting at Specific location of the list of the circular link list:-
1. Create a new
node with the given data.
2. If the
specified position is the beginning (position = 1), follow the steps for
inserting at the beginning.
3. If the
specified position is not the beginning, traverse the list to the node at
position - 1.
4. Set the next
pointer of the new node to the next node of the current node.
5. Set the next
pointer of the current node to the new node.
pseudocode:
Algorithm
insertAtPositionCircularLinkedList(data, position):
1. Create a new node newNode with the given
data.
2. If the position is 1:
2.1 Follow the steps for inserting at
the beginning.
3. Else (position is not 1):
3.1 Create a variable current and set
it to the head of the circular linked list.
3.2 Traverse the list to the node at
position - 1.
3.3 Set newNode.next to the next node
of the current node.
3.4 Set the next pointer of the current
node to the new node.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
};
// Function to
insert at a specific position in a circular linked list
Node*
insertAtPosition(Node* head, int data, int position) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = newNode;
if (position == 1) {
// Insert at the beginning
newNode->next = head;
head = newNode;
} else {
// Insert at the specified position
Node* current = head;
for (int i = 1; i < position - 1;
++i) {
if (current == nullptr) {
std::cout <<
"Invalid position." << std::endl;
return head;
}
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
return head;
}
// Function to
display the circular linked list
void
displayList(Node* head) {
if (head == nullptr) {
std::cout << "Circular
linked list is empty." << std::endl;
return;
}
Node* current = head;
do {
std::cout << current->data
<< " ";
current = current->next;
} while (current != head);
std::cout << std::endl;
}
int main() {
Node* head = nullptr;
// Insert at specific positions
head = insertAtPosition(head, 1, 1); // Insert at the beginning
head = insertAtPosition(head, 3, 2); // Insert at position 2
head = insertAtPosition(head, 2, 2); // Insert at position 2
// Display the circular linked list
std::cout << "Circular Linked
List: ";
displayList(head);
return 0;
}
Output (C++):
Circular Linked
List: 1 2 3
-------------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
insert at a specific position in a circular linked list
def
insert_at_position(head, data, position):
new_node = Node(data)
new_node.next = new_node
if position == 1:
# Insert at the beginning
new_node.next = head
head = new_node
else:
# Insert at the specified position
current = head
for i in range(1, position - 1):
if current is None:
print("Invalid
position.")
return head
current = current.next
new_node.next = current.next
current.next = new_node
return head
# Function to
display the circular linked list
def
display_list(head):
if head is None:
print("Circular linked list is
empty.")
return
current = head
while True:
print(current.data, end=" ")
current = current.next
if current == head:
break
print()
# Main function
if __name__ ==
"__main__":
head = None
# Insert at specific positions
head = insert_at_position(head, 1, 1) # Insert at the beginning
head = insert_at_position(head, 3, 2) # Insert at position 2
head = insert_at_position(head, 2, 2) # Insert at position 2
# Display the circular linked list
print("Circular Linked List:",
end=" ")
display_list(head)
Output (Python):
Circular Linked
List: 1 2 3
---------------------------------------------------------------
Deletion
To delete a node
at the beginning of a circular linked list:-
follow these
steps:
1. If the circular
linked list is empty (head is `nullptr` or `None`), print an error message or
handle the empty list case.
2. If the circular
linked list is not empty, check if it has only one node. If yes, set head to
`nullptr` (for C++) or `None` (for Python).
3. If the circular
linked list has more than one node, find the last node and update its `next`
pointer to skip the first node.
4. Free the memory
of the node to be deleted (optional in some languages like Python).
pseudocode:
Algorithm
deleteAtBeginningCircularLinkedList():
1. If head is NULL (indicating an empty
circular linked list):
1.1 Print an error message or handle
the empty list case.
2. Else (circular linked list is not
empty):
2.1 If head.next is equal to head
(indicating only one node in the list):
2.1.1 Set head to NULL (for C++) or
None (for Python).
2.2 Else (more than one node in the
list):
2.2.1 Find the last node in the
circular linked list. Let's call it lastNode.
2.2.2 Set lastNode.next to
head.next.
2.2.3 Free the memory of the node
pointed to by head (optional in some languages).
2.2.4 Set head to head.next.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
};
// Function to
delete at the beginning of a circular linked list
Node*
deleteAtBeginning(Node* head) {
if (head == nullptr) {
std::cout << "Cannot delete
from an empty circular linked list." << std::endl;
} else {
if (head->next == head) {
// Only one node in the list
delete head;
head = nullptr;
} else {
// More than one node in the list
Node* lastNode = head;
while (lastNode->next != head) {
lastNode = lastNode->next;
}
lastNode->next = head->next;
Node* temp = head;
head = head->next;
delete temp;
}
}
return head;
}
// Function to
display the circular linked list
void
displayList(Node* head) {
if (head == nullptr) {
std::cout << "Circular
linked list is empty." << std::endl;
return;
}
Node* current = head;
do {
std::cout << current->data
<< " ";
current = current->next;
} while (current != head);
std::cout << std::endl;
}
int main() {
Node* head = nullptr;
// Delete at the beginning
head = deleteAtBeginning(head);
// Insert some nodes
head = new Node{1, nullptr};
head->next = head;
head = new Node{2, head};
head = new Node{3, head};
// Display the circular linked list
std::cout << "Circular Linked
List: ";
displayList(head);
// Delete at the beginning
head = deleteAtBeginning(head);
// Display the circular linked list after
deletion
std::cout << "Circular Linked
List after deletion: ";
displayList(head);
return 0;
}
Output (C++):
Cannot delete from
an empty circular linked list.
Circular Linked
List: 3 2 1
Circular Linked
List after deletion: 2 1
------------------------------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
delete at the beginning of a circular linked list
def
delete_at_beginning(head):
if head is None:
print("Cannot delete from an empty
circular linked list.")
else:
if head.next == head:
# Only one node in the list
del head
head = None
else:
# More than one node in the list
last_node = head
while last_node.next != head:
last_node = last_node.next
last_node.next = head.next
temp = head
head = head.next
del temp
return head
# Function to
display the circular linked list
def
display_list(head):
if head is None:
print("Circular linked list is
empty.")
return
current = head
while True:
print(current.data, end=" ")
current = current.next
if current == head:
break
print()
# Main function
if __name__ ==
"__main__":
head = None
# Delete at the beginning
delete_at_beginning(head)
# Insert some nodes
head = Node(1)
head.next = head
head = Node(2, head)
head = Node(3, head)
# Display the circular linked list
print("Circular Linked List:",
end=" ")
display_list(head)
# Delete at the beginning
head = delete_at_beginning(head)
# Display the circular linked list after
deletion
print("Circular Linked List after
deletion:", end=" ")
display_list(head)
Output (Python):
Cannot delete from
an empty circular linked list.
Circular Linked
List: 3 2 1
Circular Linked
List after deletion: 2 1
-------------------------------------------------------------
To delete a node at the end of a circular linked list:-
Follow these
steps:
1. If the circular
linked list is empty (head is `nullptr` or `None`), print an error message or
handle the empty list case.
2. If the circular
linked list is not empty, check if it has only one node. If yes, delete the
node and set head to `nullptr` (for C++) or `None` (for Python).
3. If the circular
linked list has more than one node, find the second-to-last node in the list.
4. Set the `next`
pointer of the second-to-last node to the head, making it the new last node.
5. Delete the last
node (optional in some languages).
pseudocode:
Algorithm
deleteAtEndCircularLinkedList():
1. If head is NULL (indicating an empty
circular linked list):
1.1 Print an error message or handle
the empty list case.
2. Else (circular linked list is not
empty):
2.1 If head.next is equal to head
(indicating only one node in the list):
2.1.1 Delete the node pointed to by
head.
2.1.2 Set head to NULL (for C++) or
None (for Python).
2.2 Else (more than one node in the
list):
2.2.1 Create a variable current and
set it to the head of the circular linked list.
2.2.2 Traverse the list to the
second-to-last node. Let's call it secondToLastNode.
2.2.3 Delete the last node
(optional in some languages).
2.2.4 Set secondToLastNode.next to
head.
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
};
// Function to
delete at the end of a circular linked list
Node*
deleteAtEnd(Node* head) {
if (head == nullptr) {
std::cout << "Cannot delete
from an empty circular linked list." << std::endl;
} else {
if (head->next == head) {
// Only one node in the list
delete head;
head = nullptr;
} else {
// More than one node in the list
Node* current = head;
Node* secondToLastNode = nullptr;
while (current->next != head) {
secondToLastNode = current;
current = current->next;
}
// Delete the last node (optional
in some languages)
delete current;
// Update the second-to-last node's
next pointer
secondToLastNode->next = head;
}
}
return head;
}
// Function to
display the circular linked list
void
displayList(Node* head) {
if (head == nullptr) {
std::cout << "Circular
linked list is empty." << std::endl;
return;
}
Node* current = head;
do {
std::cout << current->data
<< " ";
current = current->next;
} while (current != head);
std::cout << std::endl;
}
int main() {
Node* head = nullptr;
// Delete at the end
deleteAtEnd(head);
// Insert some nodes
head = new Node{1, nullptr};
head->next = head;
head = new Node{2, head};
head = new Node{3, head};
// Display the circular linked list
std::cout << "Circular Linked
List: ";
displayList(head);
// Delete at the end
head = deleteAtEnd(head);
// Display the circular linked list after
deletion
std::cout << "Circular Linked
List after deletion: ";
displayList(head);
return 0;
}
Output (C++):
Cannot delete from
an empty circular linked list.
Circular Linked
List: 3 2 1
Circular Linked
List after deletion: 3 2
---------------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
delete at the end of a circular linked list
def
delete_at_end(head):
if head is None:
print("Cannot delete from an empty
circular linked list.")
else:
if head.next == head:
# Only one node in the list
del head
head = None
else:
# More than one node in the list
current = head
second_to_last_node = None
while current.next != head:
second_to_last_node = current
current = current.next
# Delete the last node (optional in
some languages)
del current
# Update the second-to-last node's
next pointer
second_to_last_node.next = head
return head
# Function to
display the circular linked list
def
display_list(head):
if head is None:
print("Circular linked list is
empty.")
return
current = head
while True:
print(current.data, end=" ")
current = current.next
if current == head:
break
print()
# Main function
if __name__ == "__main__":
head = None
# Delete at the end
delete_at_end(head)
# Insert some nodes
head = Node(1)
head.next = head
head = Node(2, head)
head = Node(3, head)
# Display the circular linked list
print("Circular Linked List:",
end=" ")
display_list(head)
# Delete at the end
head = delete_at_end(head)
# Display the circular linked list after
deletion
print("Circular Linked List after
deletion:", end=" ")
display_list(head)
Output (Python):
Cannot delete from
an empty circular linked list.
Circular Linked
List: 3 2 1
Circular Linked
List after deletion: 3 2
---------------------------------------------------------
To delete a node at a specific position in a circular linked list,
Follow these
steps:
1. If the circular
linked list is empty (head is `nullptr` or `None`), print an error message or
handle the empty list case.
2. If the circular
linked list is not empty, check if the specified position is valid (greater
than 0 and less than or equal to the length of the list).
3. If the
specified position is 1, it is equivalent to deleting at the beginning, so
follow the steps for deleting at the beginning.
4. If the
specified position is not 1, traverse the list to the node at position - 1.
5. Save the
reference to the node to be deleted (current->next).
6. Set the next
pointer of the current node to skip the node to be deleted.
7. Free the memory
of the node to be deleted (optional in some languages).
pseudocode:
Algorithm
deleteAtPositionCircularLinkedList(position):
1. If head is NULL (indicating an empty
circular linked list):
1.1 Print an error message or handle
the empty list case.
2. Else (circular linked list is not
empty):
2.1 Check if the specified position is
valid (greater than 0 and less than or equal to the length of the list).
2.2 If position is 1:
2.2.1 Follow the steps for deleting
at the beginning.
2.3 Else (position is not 1):
2.3.1 Create a variable current and
set it to the head of the circular linked list.
2.3.2 Traverse the list to the node
at position - 1. Let's call it currentNode.
2.3.3 Save the reference to the
node to be deleted (tempNode = currentNode.next).
2.3.4 Set currentNode.next to
tempNode.next.
2.3.5 Free the memory of the node
pointed to by tempNode (optional in some languages).
C++ Example: cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
};
// Function to
delete at a specific position in a circular linked list
Node*
deleteAtPosition(Node* head, int position) {
if (head == nullptr) {
std::cout << "Cannot delete
from an empty circular linked list." << std::endl;
} else {
int length = 1;
Node* current = head;
while (current->next != head) {
length++;
current = current->next;
}
if (position < 1 || position >
length) {
std::cout << "Invalid
position." << std::endl;
} else {
if (position == 1) {
// Deleting at the beginning
Node* lastNode = head;
while (lastNode->next !=
head) {
lastNode =
lastNode->next;
}
Node* temp = head;
head = head->next;
lastNode->next = head;
delete temp;
} else {
// Deleting at the specified
position
Node* currentNode = head;
for (int i = 1; i < position
- 1; ++i) {
currentNode =
currentNode->next;
}
Node* tempNode =
currentNode->next;
currentNode->next =
tempNode->next;
delete tempNode;
}
}
}
return head;
}
// Function to
display the circular linked list
void
displayList(Node* head) {
if (head == nullptr) {
std::cout << "Circular
linked list is empty." << std::endl;
return;
}
Node* current = head;
do {
std::cout << current->data
<< " ";
current = current->next;
} while (current != head);
std::cout << std::endl;
}
int main() {
Node* head = nullptr;
// Delete at a specific position
deleteAtPosition(head, 3);
// Insert some nodes
head = new Node{1, nullptr};
head->next = head;
head = new Node{2, head};
head = new Node{3, head};
// Display the circular linked list
std::cout << "Circular Linked
List: ";
displayList(head);
// Delete at a specific position
head = deleteAtPosition(head, 2);
// Display the circular linked list after
deletion
std::cout << "Circular Linked
List after deletion: ";
displayList(head);
return 0;
}
Output (C++):
Cannot delete from
an empty circular linked list.
Circular Linked
List: 3 2 1
Circular Linked
List after deletion: 3 1
-------------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
insert a node at the end of a circular linked list
def
insert_at_end_circular_linked_list(head, data):
new_node = Node(data)
if head is None:
head = new_node
new_node.next = head
else:
current = head
while current.next != head:
current = current.next
current.next = new_node
new_node.next = head
return head
# Function to
delete a node at a specific location in a circular linked list
def
delete_at_specific_location_circular_linked_list(head, position):
if head is None:
print("Circular linked list is
empty.")
return None
if position < 1:
print("Invalid position.")
return head
current = head
if position == 1:
last_node = head
while last_node.next != head:
last_node = last_node.next
last_node.next = current.next
if current.next == head:
head = last_node.next
del current
else:
for _ in range(position - 2):
current = current.next
temp_node = current.next
current.next = temp_node.next
del temp_node
return head
# Function to
display the circular linked list
def
display_circular_linked_list(head):
if head is None:
print("Circular linked list is
empty.")
return
current = head
while True:
print(current.data, end=" ")
current = current.next
if current == head:
break
print()
# Main function
if __name__ ==
"__main__":
head = None
# Insert some nodes into the circular
linked list
head =
insert_at_end_circular_linked_list(head, 1)
head =
insert_at_end_circular_linked_list(head, 2)
head =
insert_at_end_circular_linked_list(head, 3)
head =
insert_at_end_circular_linked_list(head, 4)
# Display the circular linked list before
deletion
print("Circular Linked List before
deletion:")
display_circular_linked_list(head)
# Delete a node at a specific location
position_to_delete = 2
head =
delete_at_specific_location_circular_linked_list(head, position_to_delete)
# Display the circular linked list after
deletion
print("\nCircular Linked List after
deletion at position", position_to_delete, ":")
display_circular_linked_list(head)
output:-
Circular Linked
List before deletion:
1 2 3 4
Circular Linked
List after deletion at position 2 :
1 3 4
--------------------------------------------------------------------------
To traverse a circular linked list:-
Use a loop to
iterate through the nodes, starting from the head, until you reach the head
again.
pseudocode:
Algorithm
traverseCircularLinkedList():
1. If head is NULL (indicating an empty
circular linked list):
1.1 Print a message indicating that the
circular linked list is empty.
2. Else (circular linked list is not
empty):
2.1 Create a variable current and set
it to the head of the circular linked list.
2.2 Repeat the following steps until
current reaches the head again:
2.2.1 Process the data of the
current node.
2.2.2 Move to the next node
(current = current.next).
C++ Example:cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
};
// Function to
traverse a circular linked list
void
traverseCircularLinkedList(Node* head) {
if (head == nullptr) {
std::cout << "Circular
linked list is empty." << std::endl;
} else {
Node* current = head;
do {
// Process the data of the current
node
std::cout << current->data
<< " ";
// Move to the next node
current = current->next;
} while (current != head);
std::cout << std::endl;
}
}
int main() {
Node* head = nullptr;
// Insert some nodes
head = new Node{1, nullptr};
head->next = head;
head = new Node{2, head};
head = new Node{3, head};
// Display the circular linked list by
traversing it
std::cout << "Traversing
Circular Linked List: ";
traverseCircularLinkedList(head);
return 0;
}
Output (C++):
Traversing
Circular Linked List: 3 2 1
----------------------------
Python Example: python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
traverse a circular linked list
def
traverse_circular_linked_list(head):
if head is None:
print("Circular linked list is
empty.")
else:
current = head
while True:
# Process the data of the current
node
print(current.data, end="
")
# Move to the next node
current = current.next
# Check if we have traversed the
entire circular linked list
if current == head:
break
print()
# Main function
if __name__ ==
"__main__":
head = None
# Insert some nodes
head = Node(1)
head.next = head
head = Node(2, head)
head = Node(3, head)
# Display the circular linked list by
traversing it
print("Traversing Circular Linked
List:", end=" ")
traverse_circular_linked_list(head)
Output (Python):
Traversing
Circular Linked List: 3 2 1
============================================
Updating in the
circular link list:-
To update a node
in a circular linked list, you need to traverse the list and find the node with
the target value. Once found, you can update its data.
pseudocode:
Algorithm
updateCircularLinkedList(target, newData):
1. If head is NULL (indicating an empty
circular linked list):
1.1 Print a message indicating that the
circular linked list is empty.
2. Create a variable current and set it to
the head of the circular linked list.
3. Repeat the following steps until current
reaches the head again:
3.1 If the data of the current node is
equal to the target:
3.1.1 Update the data of the
current node to newData.
3.1.2 Print a message indicating
that the update is successful.
3.1.3 Return true or an appropriate
indication that the update is successful.
3.2 Move to the next node (current =
current.next).
4. Print a message indicating that the
target is not found.
5. Return false or an appropriate
indication that the update is unsuccessful.
C++ Example:cpp
#include
<iostream>
// Node structure
struct Node {
int data;
Node* next;
};
// Function to
update a node in a circular linked list
bool
updateCircularLinkedList(Node* head, int target, int newData) {
if (head == nullptr) {
std::cout << "Circular
linked list is empty. Update unsuccessful." << std::endl;
return false;
}
Node* current = head;
do {
if (current->data == target) {
// Update the data of the current
node to newData
current->data = newData;
std::cout << "Update
successful. New data at target: " << newData << std::endl;
return true;
}
current = current->next;
} while (current != head);
std::cout << "Target "
<< target << " not found. Update unsuccessful." <<
std::endl;
return false;
}
int main() {
Node* head = nullptr;
// Insert some nodes
head = new Node{1, nullptr};
head->next = head;
head = new Node{2, head};
head = new Node{3, head};
// Update a node in the circular linked
list
updateCircularLinkedList(head, 2, 4); // Update successful
updateCircularLinkedList(head, 5, 6); // Target not found, update unsuccessful
return 0;
}
Output (C++):
Update successful.
New data at target: 4
Target 5 not
found. Update unsuccessful.
----------------------------
Python Example: python
Update successful.
New data at target: 4
Target 5 not
found. Update unsuccessful.
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
insert a node at the end of a circular linked list
def
insert_at_end_circular_linked_list(head, data):
new_node = Node(data)
if head is None:
head = new_node
new_node.next = head
else:
current = head
while current.next != head:
current = current.next
current.next = new_node
new_node.next = head
return head
# Function to
update a node at a specific location in a circular linked list
def
update_at_specific_location_circular_linked_list(head, position, new_data):
if head is None:
print("Circular linked list is
empty.")
return None
if position < 1:
print("Invalid position.")
return head
current = head
for _ in range(position - 1):
current = current.next
current.data = new_data
return head
# Function to
display the circular linked list
def
display_circular_linked_list(head):
if head is None:
print("Circular linked list is
empty.")
return
current = head
while True:
print(current.data, end=" ")
current = current.next
if current == head:
break
print()
# Main function
if __name__ ==
"__main__":
head = None
# Insert some nodes into the circular
linked list
head =
insert_at_end_circular_linked_list(head, 1)
head =
insert_at_end_circular_linked_list(head, 2)
head =
insert_at_end_circular_linked_list(head, 3)
head =
insert_at_end_circular_linked_list(head, 4)
# Display the circular linked list before
update
print("Circular Linked List before
update:")
display_circular_linked_list(head)
# Update a node at a specific location
position_to_update = 2
new_data = 10
head = update_at_specific_location_circular_linked_list(head,
position_to_update, new_data)
# Display the circular linked list after
update
print("\nCircular Linked List after
updating at position", position_to_update, ":")
display_circular_linked_list(head)
output:-
Circular Linked
List before update:
1 2 3 4
Circular Linked
List after updating at position 2 :
1 10 3 4
Both examples
demonstrate updating a node in a circular linked list and print whether the
update is successful or not.
--------------------------------------------------------------------------------
Complete operation
example:-
examples to
include insertion, deletion, traversing, searching, and updating operations.
C++ Example:
#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 insert(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
head->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
void deleteNode(int value) {
if (!head) {
cout << "List is empty.
Cannot delete.\n";
return;
}
Node* temp = head;
Node* prev = nullptr;
while (temp->data != value
&& temp->next != head) {
prev = temp;
temp = temp->next;
}
if (temp->data != value) {
cout << "Node with value
" << value << " not found.\n";
return;
}
if (temp == head &&
temp->next == head) {
delete temp;
head = nullptr;
} else if (temp == head) {
prev = head;
while (prev->next != head) {
prev = prev->next;
}
prev->next = head->next;
delete head;
head = prev->next;
} else {
prev->next = temp->next;
delete temp;
}
}
void traverse() {
if (!head) {
cout << "List is
empty.\n";
return;
}
Node* temp = head;
do {
cout << temp->data
<< " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
bool search(int value) {
if (!head) {
cout << "List is
empty.\n";
return false;
}
Node* temp = head;
do {
if (temp->data == value) {
cout << "Node with
value " << value << " found.\n";
return true;
}
temp = temp->next;
} while (temp != head);
cout << "Node with value
" << value << " not found.\n";
return false;
}
void update(int oldValue, int newValue) {
if (!head) {
cout << "List is
empty.\n";
return;
}
Node* temp = head;
do {
if (temp->data == oldValue) {
temp->data = newValue;
cout << "Node
updated successfully.\n";
return;
}
temp = temp->next;
} while (temp != head);
cout << "Node with value
" << oldValue << " not found. Update failed.\n";
}
};
int main() {
CircularLinkedList myList;
myList.insert(1);
myList.insert(2);
myList.insert(3);
cout << "Circular Linked List:
";
myList.traverse();
myList.search(2);
myList.update(2, 4);
cout << "After updating node
with value 2 to 4: ";
myList.traverse();
myList.deleteNode(4);
cout << "After deleting node
with value 4: ";
myList.traverse();
return 0;
}
---------------------------------------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class
CircularLinkedList:
def __init__(self):
self.head = None
def insert(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
self.head.next = self.head
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
new_node.next = self.head
def delete_node(self, value):
if not self.head:
print("List is empty. Cannot
delete.")
return
temp = self.head
prev = None
while temp.data != value and temp.next
!= self.head:
prev = temp
temp = temp.next
if temp.data != value:
print(f"Node with value
{value} not found.")
return
if temp == self.head and temp.next ==
self.head:
del temp
self.head = None
elif temp == self.head:
prev = self.head
while prev.next != self.head:
prev = prev.next
prev.next = self.head.next
del self.head
self.head = prev.next
else:
prev.next = temp.next
del temp
def traverse(self):
if not self.head:
print("List is empty.")
return
temp = self.head
while True:
print(temp.data, end=" ")
temp = temp.next
if temp == self.head:
break
print()
def search(self, value):
if not self.head:
print("List is empty.")
return False
temp = self.head
while True:
if temp.data == value:
print(f"Node with value
{value} found.")
return True
temp = temp.next
if temp == self.head:
break
print(f"Node with value {value}
not found.")
return False
def update(self, old_value, new_value):
if not self.head:
print("List is empty.")
return
temp = self.head
while True:
if temp.data == old_value:
temp.data = new_value
print("Node updated
successfully.")
return
temp = temp.next
if temp == self.head:
break
print(f"Node with value
{old_value} not found. Update failed.")
# Example usage
my_list =
CircularLinkedList()
my_list.insert(1)
my_list.insert(2)
my_list.insert(3)
print("Circular
Linked List:", end=" ")
my_list.traverse()
my_list.search(2)
my_list.update(2,
4)
print("After
updating node with value 2 to 4:", end=" ")
my_list.traverse()
my_list.delete_node(4)
print("After
deleting node with value 4:", end=" ")
my_list.traverse()
Output:-
Circular Linked
List: 1 2 3
Node with value 2
found.
Node updated
successfully.
After updating
node with value 2 to 4: 1 4 3
After deleting
node with value 4: 1 3
------------------------------------------------------------------------------
Advantage of
circular link list
Circular linked
lists offer several advantages in certain scenarios, and their characteristics
make them suitable for specific applications.
Some advantages of
circular linked lists:
1. Efficient
Insertion and Deletion at the Beginning:
- Insertion and deletion at the beginning of
a circular linked list can be done in constant time. This makes circular linked
lists efficient for operations that involve frequent insertions and deletions
at the front.
2. Circular
Nature:
- The circular structure naturally supports
operations that involve cycling through a set of elements. For example, in
applications like round-robin scheduling, a circular linked list can be used to
represent a queue of tasks.
3. Memory
Utilization:
- Circular linked lists can be more
memory-efficient than arrays or linear linked lists in certain scenarios. They
allow for dynamic memory allocation and deallocation as elements are added or
removed.
4. Implementation
of Circular Buffers:
- Circular linked lists can be used to
implement circular buffers, which are useful in scenarios where data needs to
be continuously cycled and overwritten.
5. Support for
Circular Operations:
- Algorithms or applications that involve
circular operations, such as cyclic rotations or circular lists, can be
naturally represented using circular linked lists.
6. Implementation
of Circular Navigation:
- Circular linked lists are suitable for
implementing circular navigation structures, like menus or slideshows, where
the navigation loops back to the beginning after reaching the end.
7. Simplifies
Certain Algorithms:
- Some algorithms, especially those that
involve cyclic patterns or periodic behavior, can be simplified and more
elegantly expressed using circular linked lists.
8. Dynamic Size
Adjustment:
- Circular linked lists can easily
accommodate dynamic changes in size. Elements can be added or removed without
the need to resize the data structure, which is particularly beneficial in
scenarios where the size is unpredictable.
9. Implementation
of Circular Queues:
- Circular linked lists can be used to
implement circular queues, where elements are enqueued at one end and dequeued
at the other end. This is common in scenarios like task scheduling.
10. Applications
with Natural Circular Behaviour:
- In certain applications, the nature of
the data or the operations naturally exhibits circular behavior. Circular
linked lists provide a more intuitive representation in such cases.
---------------------------
Disadvantage of
circular link list
Some disadvantages
of circular linked lists:
1. Complexity in
Traversal:
- Traversal of a circular linked list can be
more complex than that of a linear linked list. It requires careful handling to
avoid infinite loops, especially if there are errors in the logic of traversal.
2. Difficulty in
Detecting the End:
- Determining the end of a circular linked
list can be challenging. Unlike linear linked lists where a `nullptr` (null
reference) signifies the end, circular linked lists do not have a clear
termination point. Special techniques or sentinel nodes may be required.
3. Increased
Complexity in Operations:
- Certain operations, such as finding the
middle element or reversing the list, can be more complex in a circular linked
list compared to a linear linked list.
4. Additional
Memory Overhead:
- The circular nature of the list requires
an extra link or pointer field in each node to form the loop. This additional
memory overhead can be a consideration when memory usage is a critical factor.
5. Complex
Initialization and Termination:
- Initializing and terminating a circular
linked list requires special attention to ensure that the last node correctly
points back to the first node during initialization and is properly
disconnected during termination.
6. Increased Code
Complexity:
- Implementing operations on a circular
linked list often involves more intricate code compared to linear linked lists.
This increased complexity can lead to a higher likelihood of errors and may
make the code harder to maintain.
7. Limited Support
for Random Access:
- Circular linked lists do not support
direct random access to elements based on an index, as indexing is not
straightforward in a circular structure. Accessing elements in a circular
linked list may require traversing the list, leading to higher time complexity.
8. Difficulty in
Reversing:
- Reversing a circular linked list is a
non-trivial task and typically requires special handling to maintain the
circular structure while reversing the direction of links.
9. Algorithmic
Challenges:
- Some algorithms that work efficiently on
linear structures may require modification to work correctly on circular linked
lists. Adapting standard algorithms to circular structures may introduce
additional complexity.
10. Limited Use
Cases:
- Circular linked lists are not suitable
for all scenarios. In many cases, linear linked lists or arrays may be more
straightforward to use and better meet the requirements of the application.
----------------------------
Applications of circular link list
Circular linked
lists find applications in various scenarios where their unique properties are
advantageous. Some common applications of circular linked lists:
1. Round-Robin Scheduling:
- Circular linked lists are used in
operating systems for implementing round-robin scheduling algorithms. In
round-robin scheduling, tasks are assigned a fixed time slice, and the
scheduler cycles through the tasks in a circular manner.
2. Music Player Playlist:
- Circular linked lists can be used to
implement playlists in music players. The last song in the playlist points to
the first, creating a loop that allows continuous playback.
3. Image Slideshow:
- Circular linked lists are suitable for
implementing image slideshows or presentations where the display loops back to
the beginning after reaching the last image.
4. Game Development:
- In game development, circular linked lists
can be employed to represent cycles or loops in the game logic, such as the
movement of characters or the rotation of objects.
5. Managing Resources in a Circular Manner:
- Circular linked lists are used in resource
management scenarios where resources are allocated in a circular manner. For
example, in a pool of resources, once the last resource is reached, the
allocation cycles back to the first resource.
6. Circular Queues:
- Circular linked lists are employed in the
implementation of circular queues. In data structures, circular queues
efficiently handle scenarios where elements need to be enqueued and dequeued in
a circular fashion.
7. Cyclic Structures in Algorithms:
- Algorithms that involve cyclic or periodic
behavior can be naturally represented using circular linked lists. Examples
include algorithms that perform cyclic rotations or maintain cyclic patterns.
8. Simulation Systems:
- In simulations, circular linked lists can
model cyclic processes or events. For instance, in a simulation of a traffic
signal, the states of the signal lights can be organized in a circular linked
list.
9. Clockwise and Anticlockwise Navigation:
- Circular linked lists are used in
applications that involve navigation in a circular manner. This can include
clockwise or anticlockwise navigation through a set of elements.
10. Implementing Circular Buffers:
- Circular linked lists can be employed to
implement circular buffers, which are useful in scenarios where data needs to
be continuously cycled and overwritten, such as in streaming applications.
11. Data Structures with Wrap-Around Behaviour:
- Circular linked lists are suitable for
scenarios where a data structure needs to exhibit wrap-around behavior, such
as in cyclic buffer implementations or circular stacks.
12. Managing
System Resources:
- Circular linked lists can be used in
resource management systems where a set of resources needs to be allocated cyclically, ensuring fair usage.
=======================================================
0 Comments