Circular Linked List in Python
Last Updated :
04 Apr, 2024
A Circular Linked List is a variation of the standard linked list. In a standard linked list, the last element points to null, indicating the end of the list. However, in a circular linked list, the last element points back to the first element, forming a loop. In this article, we will discuss the circular linked list in Python.
Circular Linked List in Python
A circular linked list is a type of linked list in which the last node of the list points back to the first node (head), forming a loop or circle. Unlike a linear linked list, where the last node points to NULL, in a circular linked list, the next pointer of the last node points back to the first node.
Circular linked lists can be singly linked or doubly linked, meaning each node may have one or two pointers respectively (one pointing to the next node and, in the case of doubly linked lists, another pointing to the previous node). They can be used in various scenarios, such as representing circular buffers, round-robin scheduling algorithms, and as an alternative to linear linked lists when operations involve wrapping around from the end to the beginning of the list.
Representation of Circular linked list in Python:
class Node:
def __init__(self, data=None):
# Data stored in the node
self.data = data
# Reference to the next node in the circular linked list
self.next = None
Traversal of Circular Linked List in Python:
Traversing a circular linked list involves visiting each node of the list starting from the head node and continuing until the head node is encountered again.
Python3
# Python Program of Traversal of Circular Linked List
class Node:
def __init__(self, data):
# Initialize a node with data and next pointer
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
# Initialize an empty circular linked list with head pointer pointing to None
self.head = None
def append(self, data):
# Append a new node with data to the end of the circular linked list
new_node = Node(data)
if not self.head:
# If the list is empty, make the new node point to itself
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
# Traverse the list until the last node
current = current.next
# Make the last node point to the new node
current.next = new_node
# Make the new node point back to the head
new_node.next = self.head
def traverse(self):
# Traverse and display the elements of the circular linked list
if not self.head:
print("Circular Linked List is empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
# Break the loop when we reach the head again
break
# Driver Code
circular_list = CircularLinkedList()
circular_list.append(1)
circular_list.append(2)
circular_list.append(3)
print("Traversing Circular Linked List:")
circular_list.traverse()
OutputTraversing Circular Linked List:
1 -> 2 -> 3 ->
Time Complexity: O(N), where N is the number of nodes in the list.
Auxiliary Space: O(1)
Insertion in Circular Linked List in Python:
1. Insertion at the Beginning:
To insert a node at the beginning of a circular linked list, you need to follow these steps:
- Create a new node with the given data.
- If the list is empty, make the new node the head and point it to itself.
- Otherwise, set the next pointer of the new node to point to the current head.
- Update the head to point to the new node.
- Update the next pointer of the last node to point to the new head (to maintain the circular structure).
Below is the implementation of the above idea:
Python3
# Python Program for the Insertion at the Beginning
class Node:
def __init__(self, data):
# Initialize a node with data and next pointer
self.data = data
self.next = None
class LinkedList:
def __init__(self):
# Initialize an empty linked list with head pointer pointing to None
self.head = None
def insert_at_beginning(self, data):
# Insert a new node with data at the beginning of the linked list
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def display(self):
# Display the elements of the linked list
current = self.head
while current:
# Traverse through each node and print its data
print(current.data, end=" -> ")
current = current.next
# Print None to indicate the end of the linked list
print("None")
# Driver Code
linked_list = LinkedList()
linked_list.insert_at_beginning(3)
linked_list.insert_at_beginning(2)
linked_list.insert_at_beginning(1)
print("Linked List after insertion at the beginning:")
linked_list.display()
OutputLinked List after insertion at the beginning:
1 -> 2 -> 3 -> None
Time Complexity: O(1)
Auxiliary Space: O(1)
2. Insertion at a Particular Position:
To insert a node at a particular position (index) in a circular linked list, you need to follow these steps:
- Create a new node with the given data.
- Traverse the list to find the node at the desired position (index – 1).
- Update the next pointer of the new node to point to the next node of the current node.
- Update the next pointer of the current node to point to the new node.
Below is the implementation of the above idea:
Python3
# Python Program for Insertion at a Particular Position
class Node:
def __init__(self, data):
# Initialize a node with data and next pointer
self.data = data
self.next = None
class LinkedList:
def __init__(self):
# Initialize an empty linked list with head pointer pointing to None
self.head = None
def insert_at_position(self, position, data):
# Insert a new node with data at the specified position in the linked list
new_node = Node(data)
if position < 0:
# Check if the position is valid
print("Invalid position")
return
if position == 0:
# If the position is 0, insert the new node at the beginning of the linked list
new_node.next = self.head
self.head = new_node
return
current = self.head
count = 0
while count < position - 1 and current:
# Traverse the linked list until the node before the specified position
current = current.next
count += 1
if not current:
# If the position is out of range, print an error message
print("Position out of range")
return
# Insert the new node at the specified position
new_node.next = current.next
current.next = new_node
def display(self):
# Display the elements of the linked list
current = self.head
while current:
# Traverse through each node and print its data
print(current.data, end=" -> ")
current = current.next
# Print None to indicate the end of the linked list
print("None")
# Driver Code
linked_list = LinkedList()
linked_list.insert_at_position(0, 1)
# Insertion at the end
linked_list.insert_at_position(1, 3)
# Insertion at position 1
linked_list.insert_at_position(1, 2)
print("Linked List after insertion at position:")
linked_list.display()
OutputLinked List after insertion at position:
1 -> 2 -> 3 -> None
Time Complexity: O(N), where N is the number of nodes in the linked list
Auxiliary Space: O(1)
3. Insertion at the End:
To insert a node at the end of a circular linked list, you need to follow these steps:
- Create a new node with the given data.
- If the list is empty, make the new node the head and point it to itself.
- Otherwise, traverse the list to find the last node.
- Set the next pointer of the last node to point to the new node.
- Set the next pointer of the new node to point back to the head (to maintain the circular structure).
Below is the implementation of the above idea:
Python3
# Python Program for Insertion at the End
class Node:
def __init__(self, data):
# Initialize a node with data and next pointer
self.data = data
self.next = None
class LinkedList:
def __init__(self):
# Initialize an empty linked list with head pointer pointing to None
self.head = None
def append(self, data):
# Append a new node with data to the end of the linked list
new_node = Node(data)
if not self.head:
# If the linked list is empty, make the new node the head
self.head = new_node
return
current = self.head
while current.next:
# Traverse the linked list until the last node
current = current.next
# Assign the new node as the next node of the last node
current.next = new_node
def display(self):
# Display the elements of the linked list
current = self.head
while current:
# Traverse through each node and print its data
print(current.data, end=" -> ")
current = current.next
# Print None to indicate the end of the linked list
print("None")
# Driver Code
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
print("Linked List after insertion at the end:")
linked_list.display()
OutputLinked List after insertion at the end:
1 -> 2 -> 3 -> None
Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1)
Deletion in Circular Linked List in Python:
1. Deletion at the beginning of the circular linked list:
To delete the node at the beginning of a circular linked list in Python, you need to follow these steps:
- Check if the list is empty. If it is empty, there is nothing to delete.
- If the list has only one node, set the head to None to delete the node.
- Otherwise, find the last node of the list (the node whose next pointer points to the head).
- Update the next pointer of the last node to point to the second node (head’s next).
- Update the head to point to the second node.
- Optionally, free the memory allocated to the deleted node.
Below is the implementation of the above idea:
Python3
# Python Program of Deletion at the beginning of the circular linked 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):
new_node = Node(data)
if not self.head:
# If the list is empty, make the new node point to itself
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
# Make the new node point back to the head
new_node.next = self.head
def delete_at_beginning(self):
if not self.head:
print("Circular Linked List is empty")
return
# If there is only one node in the list
if self.head.next == self.head:
self.head = None
return
current = self.head
while current.next != self.head:
current = current.next
# Update the last node to point to the second node
current.next = self.head.next
# Update the head to point to the second node
self.head = self.head.next
def display(self):
if not self.head:
print("Circular Linked List is empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("", end="")
# Driver Code
circular_list = CircularLinkedList()
circular_list.append(1)
circular_list.append(2)
circular_list.append(3)
print("Circular Linked List before deletion:")
circular_list.display()
print()
circular_list.delete_at_beginning()
print("Circular Linked List after deletion at the beginning:")
circular_list.display()
OutputCircular Linked List before deletion:
1 -> 2 -> 3 ->
Circular Linked List after deletion at the beginning:
2 -> 3 ->
Time Complexity: O(1)
Auxiliary Space: O(1)
2. Deletion at a particular position in Circular Linked List:
To delete a node at a particular position of a circular linked list in Python, you need to follow these steps:
- Check if the list is empty. If it is empty, there is nothing to delete.
- If the position is 0, it means deleting the head node. In this case, update the next pointer of the last node to point to the second node and update the head.
- Traverse the list to find the node at the desired position (index – 1).
- Update the next pointer of the current node to skip the node to be deleted (pointing to the next node of the node to be deleted).
- Optionally, free the memory allocated to the deleted node.
Below is the implementation of the above idea:
Python3
# Python Program for Deletion at a particular position in Circular Linked 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):
new_node = Node(data)
if not self.head:
# Pointing back to itself
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
# Pointing back to the head
new_node.next = self.head
def delete_at_position(self, position):
if not self.head:
print("Circular Linked List is empty")
return
if position < 0:
print("Invalid position")
return
# Deleting the head node
if position == 0:
# Only one node in the list
if self.head.next == self.head:
self.head = None
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
return
current = self.head
count = 0
while count < position - 1 and current.next != self.head:
current = current.next
count += 1
if count < position - 1:
print("Position out of range")
return
current.next = current.next.next
def display(self):
if not self.head:
print("Circular Linked List is empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("", end="")
# Driver Code
circular_list = CircularLinkedList()
circular_list.append(1)
circular_list.append(2)
circular_list.append(3)
print("Circular Linked List before deletion:")
circular_list.display()
print()
circular_list.delete_at_position(1)
print("Circular Linked List after deletion at position 1:")
circular_list.display()
OutputCircular Linked List before deletion:
1 -> 2 -> 3 ->
Circular Linked List after deletion at position 1:
1 -> 3 ->
Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1)
3. Deletion at the end of a Circular Linked List:
To delete the node at the beginning of a circular linked list in Python, you need to follow these steps:
- Check if the list is empty. If it is empty, there is nothing to delete.
- If the list has only one node, set the head to None to delete the node.
- Otherwise, find the last node of the list (the node whose next pointer points to the head).
- Update the next pointer of the last node to point to the second node (head’s next).
- Update the head to point to the second node.
- Optionally, free the memory allocated to the deleted node.
Below is the implementation of the above idea:
Python3
# Python Program for Deletion at the end of a Circular Linked 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):
new_node = Node(data)
if not self.head:
# Pointing back to itself
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
# Pointing back to the head
new_node.next = self.head
def delete_at_beginning(self):
if not self.head:
print("Circular Linked List is empty")
return
# Only one node in the list
if self.head.next == self.head:
self.head = None
return
current = self.head
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
def display(self):
if not self.head:
print("Circular Linked List is empty")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("", end="")
# Driver Code
circular_list = CircularLinkedList()
circular_list.append(1)
circular_list.append(2)
circular_list.append(3)
print("Circular Linked List before deletion:")
circular_list.display()
print()
circular_list.delete_at_beginning()
print("Circular Linked List after deletion at the beginning:")
circular_list.display()
OutputCircular Linked List before deletion:
1 -> 2 -> 3 ->
Circular Linked List after deletion at the beginning:
2 -> 3 ->
Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1)
Please Login to comment...