Implement queue using Linkedlist
EasyHead to dequeue, tail to enqueue
Problem
Implement a queue using a singly linked list with head and tail pointers.
Add at the tail, remove from the head of the chain.
The idea
Keep pointers to both ends: enqueue appends at the tail and dequeue removes at the head, each in O(1). Without the tail pointer, enqueue would be an O(n) walk.
The trick
- Maintain both head and tail, and reset both when the queue empties.
- Removing at the tail would need the predecessor — that is what a deque is for.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
1
2
0
1
Step 1 of 2. Here's the example — enqueue 1,2; dequeue Values: 1, 2.
1/2
Optimal
timeO(1)spaceO(n)
1enqueue(x): tail.next=node; tail=node2dequeue(): x=head.val; head=head.next; return xInput
- array
- [1, 2]
Output
- answer
- —
Check yourself
2 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- enqueue 1,2; dequeue
- Output:
- returns 1
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.