Implement stack using Linkedlist
EasyPush and pop at the head
Problem
Implement a stack using a singly linked list (push/pop at the head).
Add and remove at the front of a chain of nodes.
The idea
Insert and remove at the head, where both operations are pure pointer rewrites. That gives true O(1) worst case with no resizing, at the cost of a pointer per element.
The trick
- Always operate at the head; the tail would require a full traversal.
- No capacity limit, but more memory per element than an array.
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 — push 1,2; pop Values: 1, 2.
1/2
Optimal
timeO(1)spaceO(n)
1push(x): node.next=head; head=node2pop(): 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:
- push 1,2; pop
- Output:
- returns 2
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.