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.

A node in a linked 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.

nodes in 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.

The basic structure.

class CircularQueue:
    #non-public _Node subclass for representing a Node.
    class _Node:
        def __init__(self, e, nxt):
            self._element = e #Nodes element
            self._next = nxt #a reference to the next node

    def __init__(self):
        self._tail = None # The last node.
        self._size = 0 #The number of elements in the queue

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

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.

Implement first() method

#an exception to be raised by an empty queue
class Empty(Exception):
   pass

class CircularQueue:
   #This part is ommitted refer to the previous section

   def first(self):
        if self.is_empty():
            raise Empty("The queue is empty.") #raise an exception if there are no elements in the queue
        head = self._tail._next #access the head node
        return head._element  #return the element of the head node

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.

Implement enqueue()

#Empty class omitted

class CircularQueue:
   #This part is ommitted refer to the previous sections
   def enqueue(self, e):
        newnode = CircularQueue._Node(e, None) #create a new node

        if self.is_empty():
            newnode._next = newnode #The node points to itself, if its the only node.
        else:
            oldhead = self._tail._next
            newnode._next = oldhead
            self._tail._next = newnode

        self._tail = newnode #update _tail
        self._size += 1

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.

implement dequeue() method

#Empty class omitted

class CircularQueue:
   #This part is ommitted refer to the previous sections

    def dequeue(self, e):
        if self.is_empty():
            raise Empty("The queue is empty.")

        oldhead = self._tail._next #The node with the element at the front of the queue

        if len(self) == 1:
            self._tail = None #The queue is now empty again.
        else:
            self._tail._next = oldhead._next #Ignore the node with the removed element

        self._size -= 1
        return oldhead._element

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.

Implement rotate() 

#Empty class omitted

class CircularQueue:
   #This part is ommitted refer to the previous sections

   def rotate(self):
       if not self.is_empty():
           self._tail = self._tail._next # The head becomes the tail

The complete implementation

The following snippet shows the complete implementation of CircularQueue after combining the previous fragments.

the complete CircularQueue class

class Empty(Exception):
    pass

class CircularQueue:
    class _Node:
        def __init__(self, e, nxt):
            self._element = e 
            self._next = nxt 

    def __init__(self):
        self._tail = None 
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty("The queue is empty.")
        head = self._tail._next
        return head._element

    def dequeue(self):
        if self.is_empty():
            raise Empty("The queue is empty.")

        oldhead = self._tail._next
        if len(self) == 1:
            self._tail = None 
        else:
            self._tail._next = oldhead._next

        self._size -= 1
        return oldhead._element

    def enqueue(self, e):
        newnode = CircularQueue._Node(e, None) 

        if self.is_empty():
            newnode._next = newnode 
        else:
            oldhead = self._tail._next
            newnode._next = oldhead
            self._tail._next = newnode

        self._tail = newnode
        self._size += 1

    def rotate(self):
        if not self.is_empty():
            self._tail = self._tail._next

Using the CircularQueue class

use enqueue()  and dequeue()

#implementation is ommitted

Q = CircularQueue()

#implementation is ommitted

Q = CircularQueue()
Q.enqueue(10)
Q.enqueue(20)
Q.enqueue(30)
Q.enqueue(40)
Q.enqueue(50)

print("Size before dequeue: ", len(Q))
while not Q.is_empty():
    print(Q.dequeue())

print("Size after dequeue: ", len(Q))

Size before dequeue:  5
10
20
30
40
50
Size after dequeue:  0

example with rotate()

#implementation is ommitted

Q = CircularQueue()
Q.enqueue(10)
Q.enqueue(20)
Q.enqueue(30)
Q.enqueue(40)
Q.enqueue(50)

print("Size before rotate: ", len(Q))
#print queue elements without dequeueing them
for _ in range(len(Q)):
    print(Q.first())
    Q.rotate()

print("Size after rotate: ", len(Q))

Size before rotate:  5
10
20
30
40
50
Size after rotate:  5