How to Implement a Queue Using Linked List
One of the most important concepts in Computer Science is definitely data structures and algorithms. However, I personally feel that the data structure courses in college are mostly too strong on theory but weak on practice. So today, we will try to gain hands-on practice by implementing a queue data structure from scratch.
What is a Queue?
As its name implies, a queue is a collection of elements that are maintained in the “first in, first out” order (FIFO). You can think of a queue in cases like a supermarket checkout line, a college class waitlist, etc. In such cases, the person who gets in the “queue” first is also the one to be served first.
In computer science, queue is an important linear data structure that is used in many applications such as implementing breadth-first search algorithm, level-order traversal, CPU scheduling, etc.
In this article, I am using Python programming language to implement our queue. I chose Python since its syntax is fairly easy to understand.
How Are We Going to Implement a Queue?
Due to the FIFO characteristic, there are 2 basic operations of a queue: adding a new element to one end of the queue (enqueue), and removing the element at the other end of the queue (dequeue). Hence, we will focus mainly on these 2 operations in this article.
Because queue is a linear data structure, it is usually implemented using an array list or a linked list. In either case, the characteristics of the queue require us to work with both ends of the list.
An array list implementation can be convenient since array list is built-in in most languages. However, it is not optimal. Consider the case when the dequeue operation will remove the first element of the list, this will leave the first index empty. But an array list cannot start at index 1, so we have to shift every element in the list to the left, which will raise the time complexity to O(n) with n being the size of the list.
So what if we use the front of the queue to add and use the end for removing instead? Removing at the end means we don’t have to shift, right? Well, in that case, since the front of the list is already occupied, to add a new element at the front, you also need to shift each element to its right in order to create an empty space at the front for the new element to go in. Hence, the time complexity is still O(n).
This is when a linked list becomes useful. Since a linked list is just a chain of nodes where the previous node links to the next one, we can simply remove a node by “cutting off” the link between 2 nodes, or add a new node by adding a new link between the nodes.
As demonstrated above, as long as we keep track of the head and the tail of the linked list, we can perform the queue’s 2 basic operations in constant time since there is no looping needed. So, let’s start coding!
Singly Linked List Node
As we are implementing our queue from a linked list, a Nodeclass is essential. Each Node will store a data field and a reference to the next node in the list.
Queue Class Constructor
As mentioned above, we need access to both ends of the list to implement a queue. Therefore, we will need 2 pointers to keep track of the head and the tail of our linked list. Along with that, we will need an integer to store the number of elements in the queue.
Adding New Element to the Queue (enqueue)
As mentioned above, when adding to the queue, we will add the new element to the end of the list.
When adding a new node, we must check if the list is empty. if it is, then we simply assign the new node to both head and tail. Otherwise, we will let tail.next be the new node in order to make the new node become tail.
Removing Element from the Queue (dequeue)
When removing, we need to check whether the list is empty. If it is, we will throw an exception. Otherwise, we remove head by making head.next become the new head. We will then return the value of the removed node.
Get the Element at the Front of the Queue (peek)
peek means getting the element at the front of the queue without removing it. Hence, we can just simply return head.value. This function will also throw an exception if the queue is empty.
A Complete Implementation
From the code above, we have implemented a basic queue with 2 core functionalities: enqueue and dequeue. This queue should be good enough to support algorithms such as breadth-first search, level-order traversal, etc. For a more complete and pythonic linked queue implementation, please see the link below.
I hope that this article has given you a more in-depth understanding of queue data structure and its implementation. For any recommendations, please leave a comment below!
Happy coding!
