Array-backed vs linked-node stack: what does a single push cost in each?
answer
- one backing copies, one never does
- where does a stack push happen
- what a full buffer forces
- amortized versus worst case per push
- node allocation and one pointer move
basics
~20 sLinked-node push is O(1) worst case: allocate a node and link it to the head. Array-backed push is O(1) amortized: usually one slot write, but a full buffer forces copying every element into a larger block.
solid answer
~50 sWith linked nodes, a push allocates a node and points it at the current top, so every push is genuinely constant time in the worst case — there is no copying, ever. With a growth-doubling array, almost every push is a single slot write plus a count increment, but when the buffer is full the push must obtain a bigger block and copy all `n` existing elements, so that one push is O(n). Averaged over a sequence of pushes the cost is O(1) amortized, because each expensive copy is preceded by roughly as many cheap pushes as it copies elements. The two backings therefore have the same amortized bound and very different worst-case shapes: linked backing pays a small, steady price per push (an allocation and a pointer); array backing pays almost nothing most of the time and occasionally pays for everything at once.
go deeper
Be ready to state both costs cleanly: linked push is O(1) worst case, array push is O(1) amortized with an O(n) copy when the buffer fills. Say which end a stack pushes at and why no traversal is needed.
Explain the mechanics behind the amortized claim — count, capacity, copy on overflow — and why pop is the cheap direction unless a shrink policy is added. Contrast per-element memory and allocation counts, not just the big-O labels.
Show that you pick a backing from the requirement, not the label: contiguous by default, linked or pre-reserved when a single operation must not stall. Name what you would measure to tell whether the copy is actually hurting the caller.
Own the framing that identical amortized bounds can still be the wrong default for a whole class of services. Decide when a team standardises on pre-reserved contiguous buffers versus a linked variant, and what evidence flips that default.
## The two backings A stack needs only two operations at one end: push and pop. Two backing stores can provide them. **Linked backing.** Each element lives in its own node holding the value plus a pointer to the node beneath it. The structure keeps one pointer to the top node. A push allocates a node, sets its next-pointer to the current top, and moves the top pointer to the new node. A pop reads the top node's value, moves the top pointer to `next`, and releases the old node. Neither operation touches any other element, so both are **O(1) worst case** — not amortized, not expected: worst case. **Array (contiguous) backing.** Elements sit in consecutive slots of one buffer, with a `count` of how many are in use. A push writes `buf[count]` and increments `count` — a couple of instructions. A pop decrements `count` and reads the slot. But the buffer has a fixed capacity, and when `count == capacity` the next push cannot write anywhere. It must acquire a larger block (typically some constant factor bigger), copy all `n` existing elements into it, and only then write the new one. **That single push is O(n).** ## Amortized is not "every operation" The standard claim is that array-backed push is **O(1) amortized**. That is a statement about the total cost of a worst-case *sequence*: n pushes starting from an empty stack cost O(n) work in total, so O(1) each on average over the sequence. It is a strong guarantee — stronger than average-case, because it assumes no distribution over inputs and holds for the worst sequence — but it says **nothing about any individual push**. One of them copied the whole structure. If a caller has a per-operation latency budget rather than a throughput budget, that distinction matters. The reason the amortization works is that a copy of n elements can only happen after the buffer went from n/2 to n elements, i.e. after roughly n/2 cheap pushes, each of which can be charged a small constant to pay in advance for its share of the future copy. ## What else differs | | array backing | linked backing | |---|---|---| | push | O(1) amortized, O(n) worst case | O(1) worst case | | pop | O(1) worst case | O(1) worst case | | index the k-th element | O(1) | O(k) — must walk | | per-element space | one slot, plus unused reserved slots | slot plus pointer(s) plus allocation bookkeeping | | layout | one contiguous block | nodes scattered wherever the allocator put them | | allocations | rare (one per growth) | one per element | Note that pop is the easy case for both: an array-backed pop never needs to copy anything unless the implementation also shrinks the buffer, which is a separate policy decision. ## Which one is the default, and why Array backing is the usual default for stacks and queues, for reasons the asymptotics do not show: the constant factor on a slot write is tiny, elements are laid out next to each other so scanning them is fast, and one allocation serves many elements instead of one per element. Linked backing earns its keep when the worst case per operation matters more than the average (a hard tail-latency budget), when the stack must grow without any single large contiguous block being available, or when elements are large and stable node addresses are useful. A third option often collapses the argument: if the maximum size is known, reserve that capacity for the array up front. Then no growth ever happens during operation and array push is O(1) worst case too, with contiguous layout intact. ## The mistake to avoid The common wrong answer runs in both directions. One version says array push is "O(1), full stop", forgetting the copy entirely. The other says linked push "must be slower because pointers", or worse, that a linked stack has to walk to the end to push — it does not, because a stack pushes at the same end it pops from, which is exactly the end the top pointer already names. The accurate summary is: same amortized bound, different worst case, different memory shape.
- Does a linked-node stack need to walk the list to push?No. A stack pushes and pops at the same end, and the structure keeps a pointer to that end — the top node. A push allocates one node, sets its next-pointer to the current top, and reassigns the top pointer. Nothing is traversed. Walking would only be needed if pushes happened at the far end from the pointer the structure keeps, which is a design nobody chooses for a stack.
- Is pop symmetric with push in the array-backed case?By default yes: pop decrements the count and reads a slot, O(1) worst case, with no copying. Asymmetry appears only if the implementation reclaims memory by shrinking the buffer, because a shrink copies the surviving elements into a smaller block. That makes pop O(n) in the worst case too, and it is why shrink thresholds need care rather than being the mirror image of the growth threshold.
- If both give O(1) amortized push, why would anyone pick linked backing?Because the worst case per operation differs. Linked push has no copy step at all, so it cannot produce a latency spike proportional to the current size. That matters under a per-operation deadline, and it matters when no single contiguous block large enough for the next growth is available. Outside those cases, array backing usually wins on constant factors and total memory.
Array backing is one long shelf: adding a book is instant until the shelf is full, and then you carry every book to a longer shelf. Linked backing is a chain of separate boxes: every addition costs one box and one clip, forever.
saying these in an interview costs you the question
- Says array-backed push is O(1) with no worst case
- Claims a linked stack must traverse to push
- Treats amortized O(1) as a per-operation guarantee
- Says linked backing has no per-element overhead
- Thinks pop can trigger a copy in every array implementation