Hands-On Data Structures and Algorithms with Python - Second Edition

Node-based queues

Using a Python list to implement a queue is a good start to get a feel for how queues work. It is also possible for us to implement our own queue data structure by utilizing pointer structures.

A queue can be implemented using a doubly linked list, and insertion and deletion operations on this data structure, and that has a time complexity of O(1).

The definition for the node class remains the same as the Node we defined when we discussed in the doubly linked lists. A doubly linked list can be treated as a queue if it enables a FIFO kind of data access, where the first element added to the list is the first to be removed.