A linked list is a data structure that is made up of nodes. Basically, each node contains two elements: a value and a reference to the next node in the list.
The first node in the list is called the head, and the last node is called the tail. If the tail points to head as the next node, we get a circular linked list.
A circular linked list has no end and can therefore be traversed infinitely in a circular manner.
Circular linked lists are useful for applications where data needs to be continuously cycled or accessed in a circular way. One example of such use case could be be in a playlist for music or videos, where the list is played in a continuous loop.
Circularly Linked Queues
One of the most practical use of a circular linked list is in the implementation of circularly linked queues.
In a circularly linked queue, we can move back to the front of the queue after reaching the end.
The CircularQueue
class supports the following operations:
enqueue(e) |
Add element e at the end of the queue. |
dequeue() |
Remove and return the last element in the queue. |
rotate() |
Rotate the elements in the queue so that the first element becomes the last and the next element after it becomes the first. |
first() |
Return the first element in the queue, without removing it. |
is_empty() |
Return True if the queue is empty, otherwise False . |
len() |
Return the number of elements in the queue. |
All the operations listed above are native to all queues except the rotate()
operation.
In a CircularQueue
, the rotate()
method allows us to rotate the elements so that the first element moves at the back of the queue, and the next element after it becomes the first. This is important when we want to perform operations on the elements of the queue without actually dequeueing them.
Implementing the CircularQueue
class
In this section, we will implement the CircularLinked
Queue class as described in the previous section. We will use a step by step approach starting with the simplest steps.
In the above snippet, we defined the basic structure of the CircularQueue
class. The _Node
class is implemented as a non-public subclass. We will use the class internally to represent nodes in the queue.
In the constructor of the CircularQueue
class, we defined the _tail
variable that will reference the last node in the structure. Note that we did not implement _head
because it would be trivial as we can access the first node(head) by simply using _tail.next
.
In the above snippet, we implemented an exception class, Empty
. This exception is raised by the first()
method if it is called when the queue is empty.
As earlier said, using _tail._next
accesses the head node, whose element is returned by the first()
method.
From the above snippet, If the an element is added when the queue is empty, the new node is made to point to itself, as it is the only node in the structure.
The new node is added at the back of the linked structure and the _tail
variable is updated to reference it.
In the above implementation, we are dequeueing the element at the front of the queue, i.e the one in the head node(_tail._next
). We are bypassing the node by making the node after it to become the next node to the tail, this effectively disconnects the removed node from the linked structure.
The complete implementation
The following snippet shows the complete implementation of CircularQueue
after combining the previous fragments.