Implement a Stack Using a Singly Linked List
Solve this Problempush(v), pop(), top(), isEmpty(), and size(). Same as before, this version takes a fixed sequence of operations (each with an argument, ignored when unused) and replays them in order, returning the result of every pop, top, isEmpty, and size call as an array.
A linked list is a natural fit for a stack: keep a single pointer to the "head" node, push by creating a new node that points at the old head and becomes the new one, and pop by reading the head's value and moving the pointer to whatever comes next. Every operation touches exactly one pointer near the front — nothing shifts, and nothing needs to be pre-sized or resized. That's the core advantage over an array-backed version: a stack conceptually only ever cares about its most recent element, and a linked list's head is exactly that, reachable in true O(1) regardless of how many elements came before it.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of operations ≤ 12 - ◆
Each operation is one of push, pop, top, isEmpty, or size - ◆
0 ≤ pushed value ≤ 1000 - ◆
pop and top return -1 when the stack is empty - ◆
This version replays a fixed sequence of operations and reports the result of every pop, top, isEmpty, and size call, in order (push has no return value)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Array With Front Insertion
BruteKeep the elements in a plain dynamic array, always inserting new values at index 0 so the most recently pushed value sits at the front. push and pop both operate on index 0 — but inserting or removing at the front of an array means shifting every other element over by one slot. For a stack holding n elements, that's O(n) work per push or pop, even though conceptually a stack only ever touches its most recent element.
O(n) per push and popO(n)1class Solution {
2 public int[] stackOpsLinkedList(String[] ops, int[] args) {
3 List<Integer> arr = new ArrayList<>();
4 List<Integer> results = new ArrayList<>();
5 for (int i = 0; i < ops.length; i++) {
6 String op = ops[i];
7 if (op.equals("push")) {
8 arr.add(0, args[i]);
9 } else if (op.equals("pop")) {
10 results.add(arr.isEmpty() ? -1 : arr.remove(0));
11 } else if (op.equals("top")) {
12 results.add(arr.isEmpty() ? -1 : arr.get(0));
13 } else if (op.equals("isEmpty")) {
14 results.add(arr.isEmpty() ? 1 : 0);
15 } else {
16 results.add(arr.size());
17 }
18 }
19 int[] output = new int[results.size()];
20 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
21 return output;
22 }
23}Optimal — Singly Linked List of Nodes
OptimalRepresent the stack as a chain of nodes, each pointing to the node beneath it, with a single "head" pointer marking the top. push creates a new node whose next pointer is the current head, then moves head to point at it — no shifting anything else. pop reads head's value, then moves head to head.next, discarding the old top. Every operation touches exactly one node's pointer, giving true O(1) time regardless of how many elements are stored — this is what "stack using a linked list" is actually testing.
O(1) per push and popO(n)1class Solution {
2 static class StackNode {
3 int val;
4 StackNode next;
5 StackNode(int val) { this.val = val; }
6 }
7
8 public int[] stackOpsLinkedList(String[] ops, int[] args) {
9 StackNode head = null;
10 int size = 0;
11 List<Integer> results = new ArrayList<>();
12 for (int i = 0; i < ops.length; i++) {
13 String op = ops[i];
14 if (op.equals("push")) {
15 StackNode node = new StackNode(args[i]);
16 node.next = head;
17 head = node;
18 size++;
19 } else if (op.equals("pop")) {
20 if (head == null) {
21 results.add(-1);
22 } else {
23 results.add(head.val);
24 head = head.next;
25 size--;
26 }
27 } else if (op.equals("top")) {
28 results.add(head == null ? -1 : head.val);
29 } else if (op.equals("isEmpty")) {
30 results.add(head == null ? 1 : 0);
31 } else {
32 results.add(size);
33 }
34 }
35 int[] output = new int[results.size()];
36 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
37 return output;
38 }
39}