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)}$
Sharing is caring. Share this story in...
Share: Twitter Facebook LinkedIn