What will we cover?
Think about the following challenge. Given a circular linked. Create a queue with constant time operations for enqueue and dequeue. Also, you can only have one pointer to the Circular Linked List.
Consider the above diagram. How will you insert a new element? Okay, that seems easy. But how do you remove the oldest element from it? With constant time!
Yes, that is not that trivial.
Step 1: Create the node class used to represent the circular linked list
There are of course many ways to go about how to create a linked list, and more specifically a circular linked list.
Some implement the classes together, that is both the node and the linked list together. I like to split them from each other. That way, you keep things simple.
Hence, to represent the circular linked list, I suggest the following simple class for a node. Then have the logic of the circular linked list in a different class.
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
Notice, that the above Node could also be used in a linked list alone. It is a simple building block, which can be used as you please.
Step 2: Create the Queue using a circular linked list
You could create a class for a circular linked list, but we will use it closely from the queue.
The art is to create a queue with only one pointer to the circular linked list structure. The circular linked list can be represented with the Node class above.
The first operation we need is to enqueue an element in the queue. That is to insert an element in the queue.
The special case of inserting the first element, would result in a circular linked list with only one Node, which points at itself.
It is first when we insert the second element it becomes tricky. Which Node should the Queue pointer point at?
This is interesting. We need to be able to insert the element in constant time. Hence, if the queue has more element, it should not need to go all the way around the circular linked list. That makes it necessary, for us to be able to find the last element added with constant number of operations.
Also, the element in the circular linked list point in the direction the were inserted.
This results to that we need to point at the last inserted element.
Assuming in the above that the elements are inserted in the order 1, 2, 3, and 4.
Then we can insert the the elements with the following code.
class Queue:
def __init__(self):
self.pointer = None
def enqueue(self, element):
if self.pointer is None:
node = Node(element)
self.pointer = node
self.pointer.next_node = node
else:
node = Node(element, self.pointer.next_node)
self.pointer.next_node = node
self.pointer = node
The code of enqueue shows first the base case, where the circular linked list is empty. Then the case where minimum one Node already exists.
Let’s follow the code of above. Before we call enqueue let’s assume it looks as follows.
First thing is to create a new Node (with the new element, below we use 5) and point it at the queues pointer next_node.
Point the queue pointers next_node at the new Node we created.
Then we update the queue pointer to point at the new Node.
That is it. We still have a circular linked list and only one pointer from the Queue. Notice, that this all happens in constant number of operations. That is, it is independent of how many Nodes are in the circular linked list. If we have 6,000 Nodes, we still only use the 3 operations described above. Hence, enqueue has a O(1) worst case run time.
Next step will see if we can dequeue correctly from the structure, while keeping it intact.
Step 3: How to dequeue from the circular linked list
This seems tricky at first.
But look at the following diagram, where we have 4 elements. They have been inserted by the enqueue function given in Step 2. The first element was 1, then 2, then 3, and finally element 4.
Hence, when we dequeue, we want to return and remove element 1. And the circular linked list should look like this afterwards.
Also, the dequeue operation should be done in constant number of operations.
Obviously, there is a special case, when we only have one element in the queue. Then we remove it and make the queue pointer point at None.
class Queue:
# Continued...
def dequeue(self):
if self.pointer is None:
return None
if self.pointer.next_node == self.pointer:
element = self.pointer.element
self.pointer = None
return element
element = self.pointer.next_node.element
self.pointer.next_node = self.pointer.next_node.next_node
return element
Otherwise, we get the element from the queue pointers next_node.
Then we update the queue pointers node to point at next_node.next_node. Notice, that this will keep the structure intact. Also, we keep the dequeue function at a constant number of operations, hence, O(1).
The full code with a print queue function
Here is the full code including a representation to print the queue.
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
class Queue:
def __init__(self):
self.pointer = None
def enqueue(self, element):
if self.pointer is None:
node = Node(element)
self.pointer = node
self.pointer.next_node = node
else:
node = Node(element, self.pointer.next_node)
self.pointer.next_node = node
self.pointer = node
def dequeue(self):
if self.pointer is None:
return None
if self.pointer.next_node == self.pointer:
element = self.pointer.element
self.pointer = None
return element
element = self.pointer.next_node.element
self.pointer.next_node = self.pointer.next_node.next_node
return element
def __str__(self):
if self.pointer is None:
return "empty"
first = self.pointer
node = first.next_node
result = "["
while node != first:
result += str(node.element) + '->'
node = node.next_node
return result + str(node.element) + '->...]'
queue = Queue()
for i in range(20):
queue.enqueue(i)
print(queue)
for _ in range(21):
queue.dequeue()
print(queue)
for i in range(5):
queue.enqueue(i)
print(queue)
The beginning of the output will be as follows.
[0->...] [0->1->...] [0->1->2->...] [0->1->2->3->...] [0->1->2->3->4->...] [0->1->2->3->4->5->...]
