How do you implement a stack, and what data structure backs it?

beginner

← All Linked Lists, Stacks & Queues questions

Re-explain

You can build a stack on an array or on a linked list. Both keep push and pop at O(1). The choice mostly changes memory behavior, not the contract callers see.

With an array, you track the top index. push writes at that index and bumps it. pop reads and steps back. The array grows when full, occasionally copying everything to a bigger block.

With a linked list, the head node is the top. push adds a new head, and pop unlinks it. No copying ever happens, but each node costs an extra pointer.

stack.push(4); // top is now 4
stack.pop();   // returns 4, top restored

Most languages hand you a ready stack through their dynamic array type. Reach for that first.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Linked Lists, Stacks & Queues One question at a time. Answer out loud, get graded, see what you missed.

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

When would you back a stack with a linked list instead of an array? Compares no resize copies against an extra pointer per node and scattered memory, and says the dynamic array is still the usual default.
Some array pushes copy every element. How can push still be called O(1)? Explains amortized cost. Growing capacity by a constant factor makes copies rare, so n pushes cost O(n) in total, though a single push can cost O(n).
What should pop or peek do when the stack is empty? Picks one clear contract, like throwing an error or returning an empty marker, and checks the top index or head before reading.
In a garbage-collected language, what should pop do with the array slot it leaves behind? Clears the slot. Otherwise the array still references the popped object and the collector can't free it.
How would you extend your stack to return its minimum in O(1)? Keeps a second stack, or a pair per entry, holding the minimum so far, so a pop brings back the previous minimum without a scan.

What you can say

A stack can sit on either an array or a linked list, and both give you push and pop in O(1).
With an array I track a top index, so push writes at that index and bumps it, and pop moves it back and returns the element.
When the array is full it grows, which means copying everything into a bigger block, but that happens only occasionally.
With a linked list the head node is the top, so push adds a new head and pop unlinks it, and nothing ever gets copied.
Callers see the same contract either way, so the choice is about memory, with occasional copies for the array and an extra pointer on every node for the list.
In real code I'd reach for the language's dynamic array first, and only build a linked one if those occasional full copies are a cost I can't accept.

Weak answers to avoid

Says 'use an array' and stops That names a backing store but not how it works. Walk through the top index for push and pop, then say what happens when the array fills up.
Claims every array push is strictly O(1) A push that triggers growth copies every element. Say O(1) amortized, and explain that the copies are rare because capacity grows by a factor.
Pushes and pops at the wrong end Popping the tail of a singly linked list or the front of an array costs O(n). Keep the top at the list head or at the array's end.
Treats array and list as interchangeable Callers see the same contract, but memory behaves differently. Mention the resize copies for the array and the extra pointer per node for the list.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Linked Lists, Stacks & Queues cheatsheet.

← Back to all Linked Lists, Stacks & Queues questions

Pro · $10/mo

67 of 78 Linked Lists, Stacks & Queues answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →