Ufdjrw

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.

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.