dequeue in circularly linked list in python

Question

I am working on the implementation of Queue with a circularly linked list in python. Below is the pictorial representation of circularly LinkedList

I was able to implement most of the code except the dequeue routine. In dequeue routine, one has to keep track of the previous node reference as well as the next node reference with respect to current node. In double linked list, it's easy to implement. However, I have no idea how to implement this concept in single linked list.

class CircularQueue:

  ''' Queue implementation using a Circularly linked list for storage '''

  class _Node:

      __slots__ == '_element','_next'

      def __init__(self,element,next):            
        self._element = element 
        self._next = next 

  def __init__(self):
    '''Create an empty queue'''
    self._current = None 
    self._size = 0

  def __len__(self):
    return self._size

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

  def enqueue(self,e):

    node = self._Node(e,None)
    if self.is_empty():
        newest._next = newest
    else:
        curr_node = self._current._next 
        node._next = curr_node
    self._current = node 
    self._size += 1

  def dequeue(self):
    if self.is_empty():
        raise Empty('Stack is empty')

It would be more helpful if anyone can give me thoughts on how to move forward in dequeue routine.

Circular queues were invented to deal with fixed arrays; there is no reason to make a linked list implementation circular. — meowgoesthedog

Aarkon Aarkon · Accepted Answer · 2019-03-07T16:58:54

Since your linked list is unidirectional, an element does only have a reference to it's successor, but never to it's predecessor, which you would need both in order to easily close the hole in the list once you dequeue an element.

I see two possibilities: You could either make the linked list bidirectional, therefore adding a reference to the previous element. I cleaned up your implementation a bit, I hope you still can make something of this:

""" Queue implementation using a Circularly linked list for storage """


class _Node:
    def __init__(self, element, next=None, previous=None):
        self.element = element
        if next is None:
            next = self
        self.next = next
        if previous is None:
            previous = self
        self.previous = previous


class CircularQueue:
    def __init__(self):
        self._current = None
        self._size = 0

    def __len__(self):
        return self._size

    def get_head(self):
        return self._current.element

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

    def next(self):
        self._current = self._current.next
        return self._current.element

    def previous(self):
        self._current = self._current.pevious
        return self._current

    def enqueue(self, element):
        """ Adds an element at the current position, ahead of the current element """
        if self.is_empty():
            new_node = _Node(element)
        else:
            new_node = _Node(element, self._current.next, self._current)
            self._current.next = new_node
        self._current = new_node
        self._size += 1

We can now check if our code is correct:

cq = CircularQueue()
cq.enqueue("A")
cq.enqueue("B")
cq.enqueue("C")

print(cq.get_head())
print(cq.next())
print(cq.next())
print(cq.next())

And you will see C, A, B and C printed in succession.

A bilateral queue enables us to implement a dequeue method like this:

def dequeue(self, element_key=None):
    if self.is_empty():
        raise KeyError('Stack is empty')

    if element_key is None:
        self._current.next.previous = self._current.previous
        self._current.previous.next = self._current.next
        return self.next()
    else:
        current = self._current
        while self._current.element != element_key:
            self.next()
            if self._current == current:
                raise KeyError('Element not found')
        self.dequeue()

And if we test it...

print("dequeuing 'B'")
cq.dequeue("B")
print(cq.get_head())
print(cq.next())
print(cq.next())
print(cq.next())

... we should see that "dequeuing 'B'" and C, A, C & again A are printed, which makes us happy. :)

Using a unilateral approach is possible too; you might end up having less work handling references while you would have run through your entire circle (in the worst case). First, you'd skip to the next element in the queue until the next element of the current one's is the one you want to dequeue, then set the current's elements next reference to the dequeued one's next, and you are basically done.

dequeue in circularly linked list in python

1 Answers