Easy difficulty · Algorithm · Topics: stack, design, linked-list, lifo
A stack is a LIFO (last in, first out) collection. This version stores the elements in a singly linked list where the head is the top of the stack. Push and pop both work at the head, so every operation is O(1), and the stack never overflows until memory runs out.
A linked list gives cheap insertion and removal at its front: you only change one pointer. A stack only ever needs that one end, so the head of a list is a perfect "top". Instead of an index into an array, the top is a reference to a node, and each node remembers the one underneath it.
The invariant: head is the newest element, head.next is the one pushed before it, and so on until null; length equals the number of nodes.
head = null, length = 0.next is the current head, then make it the head.head is null return null. Otherwise remember , move to , and return the value.head.valheadhead.nexthead.val without moving anything (or null if empty).head === null.length counter (walking the list would cost O(n)).Test case 0 (the list is written top first):
| Operation | List after (top first) | Result |
|---|---|---|
push(1) | 1 | - |
push(2) | 2 -> 1 | - |
push(3) | 3 -> 2 -> 1 | - |
peek() | 3 -> 2 -> 1 | 3 |
pop() | 2 -> 1 | 3 |
size() | 2 -> 1 | 2 |
pop() | 1 | 2 |
pop() | empty | 1 |
pop() | empty | null |
isEmpty() | empty | true |
| Operation | Time | Why |
|---|---|---|
| Push, Pop, Peek | O(1) | only the head pointer changes |
| Is Empty, Size | O(1) | a null check or a stored counter |
| Space | O(n) | one node per element, plus the pointer in each node |
head loses the whole stack.head.val on null throws. Check for null first.length on every push and pop makes size() wrong.this.head is drawn as a linked list; the first node is the top of the stack.head moves one node on.length increase and decrease in step with the nodes.this.head is null, and peek / pop return null.Input
["LinkedListStack", "push", "push", "push", "peek", "pop", "size", "pop", "pop", "pop", "isEmpty"]
[[], [1], [2], [3], [], [], [], [], [], [], []]
Output
[null, null, null, null, 3, 3, 2, 2, 1, null, true]
class LinkedListStack {
constructor() {
this.head = null; // the top of the stack
this.length = 0;
}
// Push: the new node becomes the head and points at the old head.
push(x) {
this.head = new ListNode(x, this.head);
this.length++;
}
// Pop: unlink the head and return its value, or null if empty.
pop() {
if (this.head === null) {
return null;
}
const value = this.head.val;
this.head = this.head.next;
this.length--;
return value;
}
peek() {
if (this.head === null) {
return null;
}
return this.head.val;
}
isEmpty() {
return this.head === null;
}
size() {
return this.length;
}
}