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 class represents a single node in the circular linked list, and the
CircularLinkedList class contains the logic for creating and traversing the list.
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.
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