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.

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