Implement Queue Using Linked List

Source: GeeksForGeeks

We have to implement a queue using a linked list. We’re given two pointers front and rear of the linked list.

Our strategy is to append new elements at the end of linked list (push operation) and delete elements from the start of the linked list (pop operation).

For pop operation, if front is a null pointer, then we’ll return -1 as the linked list (or queue) is empty.

Initially, front and rear both pointers are empty. So if a enqueue operation occurs, then we’ll initialize both the front and rear pointer. Then it’ll look something like the following:

For subsequent push/enqueue operations, we just need to update the rear pointer. The situation will look something like this after a few push/enqueue operation:

Now if a pop/dequeue operation occurs, we need to advance the front pointer. There is a special case here. If after several updates, the front pointer becomes null, then it means that the queue or linked list has become empty. If that happens, then we need to set the rear pointer to null as well.

Here’s the final implementation:

Time and Space Complexity: $\mathcal{O(1)}$