Implement Stack using Linked List

Implement a stack (last-in, first-out) backed by a singly linked list, supporting:

push(x) — add x to the top.
pop() — remove and return the top element; return -1 if the stack is empty.

Both operations must be O(1). The first operation names the class (its constructor).

Hints

· Stuck? Reveal one nudge at a time.

Which end of a singly linked list supports O(1) insertion and removal?

Keep a head pointer as the top: push prepends, pop unlinks the head.

Return -1 when the head is null.

Common doubts

Head operations are O(1) with no traversal. Tail operations on a singly linked list require walking to the end (O(n)) unless you also track a tail pointer.

A linked list never resizes and uses exactly one node per element, at the cost of a pointer per node and an allocation per push.

Interview follow-ups

· What an interviewer asks next.

peek() returns head's value without advancing; size() is maintained with a counter incremented on push and decremented on pop.

Yes — free popped nodes to avoid leaks (managed languages garbage-collect them automatically).

Fun facts

A linked-list stack is the textbook example of why 'insert at head' is the linked list's superpower.
Persistent (immutable) stacks share tails between versions — pushing returns a new head pointing at the old list, leaving it intact.

Asked at

AmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: push(5), push(10), pop(), pop(), pop()
Output: 10, 5, -1
LIFO: the last pushed (10) is popped first, then 5, then -1.

Example 2

Input: push(7), pop()
Output: 7
Push 7, pop returns 7.

Constraints

- 1 <= number of operations <= 100 - 1 <= x <= 10^5 - pop() returns -1 if the stack is empty.

A linked list gives O(1) insertion and removal at the head — which is exactly what a stack needs. Keep a head pointer that always points at the top: push prepends a new node, pop unlinks the head.

Prerequisites

Before you start

· Concepts used directly in the solution.

Singly linked list. Nodes holding a value and a next pointer, chained together.

Head insertion. Prepending a node to the front of a list is O(1) — no traversal.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The contract

“Which end is the top?”

The head of the list — both push and pop happen there.

“What does pop return when empty?”

-1, and the head is null.

The ideal opening — say it like this

I'll keep a head pointer that always points at the top of the stack.

Push creates a node whose next is the current head, then makes it the new head.

Pop reads the head's value and moves head to head.next, returning -1 if head is null.

Understand the problem

Worked example — push 5, push 10, pop, pop, pop

push 5   -> head -> [5]                (null)
push 10  -> head -> [10] -> [5]        (null)
pop      -> head -> [5]                returns 10
pop      -> head -> null               returns 5
pop      -> head is null               returns -1

Key observations

1Aha

Head insertion and removal are O(1)

Prepending and unlinking at the head of a singly linked list need no traversal, giving O(1) push and pop.

2Aha

No capacity to manage

Unlike an array-backed stack, a linked list grows one node at a time — there's no resizing and no wasted capacity.

Summary

Key takeaway

Keep a head that points at the top. push prepends a node (new head); pop returns the head's value and advances head, or -1 when the list is empty. Every operation is O(1) with no resizing.

push(x): head = Node(x, next=head)
pop():   return -1 if head is null; val = head.val; head = head.next; return val