Table of contents
Introduction
Circular linked lists are a variant of linked lists where the last node points back to the first node, forming a closed loop. This article aims to provide a comprehensive understanding of circular linked lists, including their operations, implementation in Python, and a real-time example to illustrate their usefulness. We will also discuss the time complexities associated with each operation.
Implementation
Insertion
Insertion at the Beginning
To insert a node at the beginning of a circular linked list, we need to create a new node, update its next pointer to the current first node, and update the last node's next pointer to the newly inserted node.
def insert_at_beginning(self, data): new_node = Node(data) if not self.head: self.head = new_node self.last = new_node new_node.next = self.head else: new_node.next = self.head self.last.next = new_node self.head = new_nodeInsertion at the End
To insert a node at the end of a circular linked list, we create a new node, update the last node's next pointer to the new node, and update the new node's next pointer to the first node.
def insert_at_end(self, data): new_node = Node(data) if not self.head: self.head = new_node self.last = new_node new_node.next = self.head else: new_node.next = self.head self.last.next = new_node self.last = new_nodeInsertion at a Specific Position
Inserting a node at a specific position involves traversing the circular linked list until we reach the desired position. We update the next pointers accordingly to insert the new node.
def insert_at_specific_position(self, data, position): new_node = Node(data) if position < 1: print("Invalid position.") return if not self.head: if position == 1: self.head = new_node self.last = new_node new_node.next = self.head else: print("Invalid position.") else: current = self.head count = 1 while count < position - 1 and current.next != self.head: current = current.next count += 1 if count == position - 1: new_node.next = current.next current.next = new_node if current == self.last: self.last = new_node else: print("Invalid position.")
Deletion
Deletion from the Beginning
Deleting the first node requires updating the last node's next pointer to the second node and updating the first node to the next node.
def delete_from_beginning(self): if not self.head: print("Circular linked list is empty.") return if self.head == self.last: self.head = None self.last = None else: self.last.next = self.head.next self.head = self.head.nextDeletion from the End
Deleting the last node involves updating the second-to-last node's next pointer to the first node and updating the last node's previous pointer.
def delete_from_end(self): if not self.head: print("Circular linked list is empty.") return if self.head == self.last: self.head = None self.last = None else: current = self.head while current.next != self.last: current = current.next current.next = self.head self.last = currentDeletion from a Specific Position
Similar to insertion, deletion at a specific position requires traversing the circular linked list to find the node to be deleted. We update the next pointers to bypass the node to be deleted.
def delete_at_specific_data(self, data): if not self.head: print("Circular linked list is empty.") return current = self.head previous = None while True: if current.data == data: if current == self.head: if self.head == self.last: self.head = None self.last = None else: self.head = current.next self.last.next = self.head elif current == self.last: previous.next = self.head self.last = previous else: previous.next = current.next break previous = current current = current.next if current == self.head: break
Traversal
Traversing a circular linked list involves starting from any node and visiting each node in the list until we reach the starting node again.
def traverse(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
Time Complexities
Insertion at the Beginning: O(1)
- Inserting a new node at the beginning of a circular linked list involves updating a few references. It requires creating a new node, updating the next reference of the new node to point to the current first node, updating the next reference of the last node to point to the new node, and updating the head reference to the new node. Since these operations are constant time, the time complexity is O(1).
Insertion at the End: O(n)
- Inserting a new node at the end of a circular linked list requires traversing the entire list to reach the last node. After reaching the last node, we update its next reference to point to the new node and update the new node's next reference to point back to the first node. As a result, the time complexity is linear, O(n), where n is the number of nodes in the circular linked list.
Deletion of the First Node: O(1)
- Deleting the first node in a circular linked list involves updating references to remove the node from the list. We update the next reference of the last node to point to the second node, and update the head reference to the second node. These operations take constant time, resulting in a time complexity of O(1).
Deletion of the Last Node: O(n)
- Deleting the last node in a circular linked list requires traversing the entire list to reach the second-to-last node. Once we reach the second-to-last node, we update its next reference to point to the first node and update the last node's next reference to None. As a result, the time complexity is O(n) since we need to traverse the list to find the second-to-last node.
Traversal: O(n)
- Traversing a circular linked list involves visiting each node once. Starting from the head, we iterate through the list until we reach the first node again. Since we need to visit each node once, the time complexity is O(n), where n is the number of nodes in the circular linked list.
Searching: O(n)
- Searching for a specific value in a circular linked list requires traversing the entire list to check the value of each node. We start from the head and compare the data of each node until we find a match or reach the first node again without finding the desired value. Therefore, the time complexity is O(n), as we may need to check each node in the worst case.
Real-Time Example
A real-time example where a circular linked list can be used is in scheduling algorithms. Consider a scheduling algorithm for round-robin scheduling, where each process gets a fixed amount of time to execute before the CPU switches to the next process. The circular linked list can be used to represent the list of processes in the ready queue.
class Process:
def __init__(self, process_id):
self.process_id = process_id
self.next_process = None
class RoundRobinScheduler:
def __init__(self):
self.head = None
self.tail = None
def add_process(self, process_id):
new_process = Process(process_id)
if self.head is None:
self.head = new_process
self.tail = new_process
new_process.next_process = self.head
else:
new_process.next_process = self.head
self.tail.next_process = new_process
self.tail = new_process
def remove_process(self, process_id):
if self.head is None:
return
elif self.head == self.tail and self.head.process_id == process_id:
self.head = None
self.tail = None
elif self.head.process_id == process_id:
self.head = self.head.next_process
self.tail.next_process = self.head
else:
current = self.head
while current.next_process != self.head:
if current.next_process.process_id == process_id:
current.next_process = current.next_process.next_process
return
current = current.next_process
def execute_next_process(self):
if self.head is None:
return
current_process = self.head
print("Executing Process:", current_process.process_id)
self.head = self.head.next_process
self.tail = current_process
def display_processes(self):
if self.head is None:
return
current = self.head
while True:
print("Process ID:", current.process_id)
current = current.next_process
if current == self.head:
break
# Example usage
scheduler = RoundRobinScheduler()
scheduler.add_process(1)
scheduler.add_process(2)
scheduler.add_process(3)
scheduler.add_process(4)
scheduler.display_processes()
scheduler.execute_next_process()
scheduler.remove_process(3)
scheduler.display_processes()
In this example, the circular linked list is used to maintain the list of processes in the round-robin scheduler. Processes are added to the end of the list and executed cyclically, moving from one process to the next until all processes have been executed or the scheduler is stopped.