Queues as Doubly Linked Lists

Because doubly linked lists have immediate access to both the front and end of the list, they can insert data on either side at O(1) as well as delete data on either side at O(1).

Because doubly linked lists can insert data at the end in O(1) time and delete data from the front in O(1) time, they make the perfect underlying data structure for a queue.

We looked at , and you’ll recall that they are lists of items in which data can only be inserted at the end and removed from the beginning. You learned there that queues are an example of an abstract data type and that we were able to use an array to implement them under the hood.

Now, since queues insert at the end and delete from the beginning, arrays are only so good as the underlying data structure. While arrays are O(1) for insertions at the end, they’re O(N) for deleting from the beginning.

A doubly linked list, on the other hand, is O(1) for both inserting at the end and for deleting from the beginning. That’s what makes it a perfect fit for serving as the queue’s underlying data structure.

Code Implementation: Queue Built upon a Doubly Linked List

Before implementing the queue itself, we’ll first add one more method to our DoublyLinkedList class. This pop_head method removes the head from the list and returns it:

	def pop_head(self):
	popped_node = self.first_node
	self.first_node = self.first_node.next_node
	self.first_node.previous_node = None
	return popped_node

As you can see, we effectively delete the first node by changing the list’s self.first_node to be what is currently the second node. We also make sure that the new head doesn’t link to any previous node. Finally, we return the node we just deleted.

With this in place, we can now create a queue implementation that is built upon a doubly linked list:

	import doubly_linked_list


	class Queue:
	def __init__(self):
	self.data = doubly_linked_list.DoublyLinkedList()

	def enqueue(self, element):
	self.data.append(element)

	def dequeue(self):
	dequeued_node = self.data.pop_head()
	return dequeued_node.data

	def read(self):
	if not self.data.first_node:
	return None
	return self.data.first_node.data

The Queue class implements its methods on top of our DoublyLinkedList. The enqueue method relies on the append method of our DoublyLinkedList:

	def enqueue(self, element):
	self.data.append(element)

Similarly, the dequeue method takes advantage of the linked list’s ability to delete from the front of the list:

	def dequeue(self):
	dequeued_node = self.data.pop_head()
	return dequeued_node.data

By implementing our queue with a doubly linked list, we can now both insert and delete from the queue at a speedy O(1). And that’s doubly awesome.