A circular linked list is a linked list type data structure similar to a doubly linked list that consists of a set of nodes, each of which contains some data and a pointer to the next node in the list. Unlike a regular linked list, the last node in a circular linked list points back to the first node, creating a loop. This means that you can traverse the list indefinitely, starting from any node.
In a circular linked list, each node contains two components: the data component, which holds the actual data being stored, and the next component, which holds a reference to the next node in the list. Unlike a regular linked list, where the last node’s next component is set to None to indicate the end of the list, the last node in a circular linked list points back to the first node.
To create a circular linked list, you first create a new node and set its next component to point to itself. This node becomes the head of the list. Then, as you add new nodes to the list, you set each node’s next component to point to the next node in the list. When you reach the end of the list, you set the last node’s next component to point back to the head of the list.
To traverse a circular linked list, you start at any node and repeatedly move to the next node using the next component. You can continue this process indefinitely, since the last node in the list points back to the first node.
One advantage of using a circular linked list is that it allows you to easily implement certain algorithms that require looping over a list multiple times. For example, if you’re implementing a game that involves a circular playing board, you could represent the board as a circular linked list and move game pieces around the board by traversing the list.
However, one potential downside of using a circular linked list is that it can be more difficult to insert and delete nodes from the list compared to a regular linked list. This is because you have to be careful to update the next pointers correctly to maintain the circular structure of the list.
Here’s an example of how to traverse a circular linked list in Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
# insert new node at the end of the list
def insert(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = self.head
else:
curr_node = self.head
while curr_node.next != self.head:
curr_node = curr_node.next
curr_node.next = new_node
new_node.next = self.head
# traverse the list
def traverse(self):
if self.head is None:
print("List is empty")
else:
curr_node = self.head
while True:
print(curr_node.data)
curr_node = curr_node.next
if curr_node == self.head:
break
In this example, we define two classes: Node and CircularLinkedList. The Node class represents a single node in the circular linked list, and the CircularLinkedList class contains the logic for creating and traversing the list.
The insert method in the CircularLinkedList class inserts a new node at the end of the list. If the list is empty, the new node becomes the head of the list and points to itself. If the list is not empty, we iterate through the list until we reach the last node, then set its next pointer to the new node and set the new node’s next pointer to the head of the list.
The traverse method in the CircularLinkedList class traverses the list by starting at the head node and repeatedly moving to the next node until we reach the head node again. During each iteration of the loop, we print the data attribute of the current node. We use a while True loop to ensure that we keep iterating until we reach the head node again, at which point we break out of the loop.
Here’s an example of how to use this code to create and traverse a circular linked list:
# create a new circular linked list
clist = CircularLinkedList()
# insert some nodes into the list
clist.insert(1)
clist.insert(2)
clist.insert(3)
clist.insert(4)
# traverse the list and print the data in each node
clist.traverse()
This should output the following:
1
2
3
4