For a stack holding a billion small values, what does linked backing cost that array backing does not?
answer
- count everything stored beside the value
- one allocation per element adds up
- array slack versus node overhead
- what two blocks alive at once means
- one huge contiguous run versus many small pieces
basics
~20 sEvery linked element carries a next-pointer plus allocator bookkeeping, so a small payload often costs two to three times its own size. Array backing instead pays in unused reserved slots and needs one enormous contiguous block.
solid answer
~50 sLinked backing pays per element: a next-pointer, allocator header and alignment padding sit alongside every value, so a small payload can easily end up costing two to three times what it does in a packed buffer — at a billion elements that difference is measured in gigabytes, not percentages. It also pays a separate allocation per element and scatters the nodes, so walking the stack chases pointers instead of striding through adjacent slots. Array backing pays differently: it holds up to a growth factor's worth of unused slots, and during a resize the old and new blocks coexist, so peak demand exceeds the steady footprint. Its hard limit is different too — it needs one contiguous block of that size, which fragmentation can deny even when total free memory is ample. Linked backing dies on total footprint and allocation churn; array backing dies at a resize.
go deeper
Know that a linked element stores a pointer alongside its value, while a contiguous buffer stores only values but reserves spare slots. Being able to say which one holds unused capacity is the expected starting point.
Quantify it: pointer plus allocator header plus padding against payload size, and slack plus resize peak on the other side. Explain why the ratio depends on how big each element is.
Show you choose from the actual pressure — a memory ceiling, a fragmented long-lived heap, an unknown peak size — and that you know reserving capacity up front removes most of the array-side objections in one move.
Own the call when the numbers are close and the constraint is organisational: a fleet memory budget, a machine size you are trying not to grow into, or a structure whose peak nobody can predict. Say what evidence would justify the more expensive option.
## Same asymptotics, very different bytes Both backings store n elements in O(n) space, which is why asymptotic notation is useless for this decision. The constants are the answer, and at a billion elements the constants are the whole story. ## What a linked element actually costs A node holds the value and at least one pointer to the next node. On a 64-bit machine that pointer is 8 bytes. On top of that, most general-purpose allocators attach bookkeeping to each separately allocated object — a size or class header — and round the total up to an alignment or size-class boundary. For a small payload the overhead is not a rounding error: an 8-byte value in a node with an 8-byte pointer, a header and rounding can occupy 24 to 32 bytes. That is the familiar **2-3x** figure. It gets worse for a doubly linked variant, which adds a second pointer, and better for large payloads, where the fixed per-node cost is amortised across a bigger value. At a billion elements: roughly 8 GB packed contiguously versus roughly 24-32 GB as nodes. That is the difference between fitting on a machine and not. A second linked cost is not space but time and pressure: **one allocation per element**. A billion pushes means a billion allocator round-trips on the way in and a billion releases on the way out, and it hands the allocator a billion chances to fragment the heap. ## What array backing costs instead Contiguous backing is not free either, and an honest comparison names its costs: - **Reserved but unused slots.** A growth-doubling buffer just after a growth is about half empty, so the steady-state waste is bounded by the growth factor. Expect up to roughly 50% slack in the doubling case. - **The resize peak.** During growth, the old block and the new block are alive at the same time, so momentary demand is the sum of both. For a structure at 8 GB, the growth to 16 GB briefly wants 24 GB. - **One contiguous block.** This is the qualitative difference. Linked backing can use memory wherever it finds it, in element-sized pieces. Array backing needs a single run of the full size. On a fragmented heap, a large contiguous request can fail while plenty of total memory is free — a failure mode with no analogue on the linked side. ## Layout, at structure-choice level Beyond raw bytes, the two layouts behave differently when the stack is walked or drained. Array elements sit next to each other and are visited in address order; linked nodes sit wherever the allocator put them, so each step follows a pointer to an unpredictable address. For a hot stack that is pushed and popped constantly — a parser's operand stack, say — the contiguous version is doing arithmetic on an index while the linked version is dereferencing. That is a real and consistent gap in practice, and it is why contiguous backing is the default choice even when both options are O(1). ## Which one dies first, and from what This is the crux of the follow-up an interviewer will ask, and the answer is that they fail differently rather than one simply being better: | pressure | array backing | linked backing | |---|---|---| | total memory | best case: packed, plus bounded slack | 2-3x for small payloads | | peak during growth | old + new block alive together | no peak — grows element by element | | fragmented heap | may fail to find one large block | keeps working | | allocation count | logarithmic in n | one per element | | unknown final size | must guess or repeatedly copy | indifferent | If the size is known ahead of time, reserving the array up front removes the resize peak and the copies at once, and contiguous backing wins on every column but fragmentation. If the size is unknown and the heap is hostile, or if per-element memory can be released promptly as the stack drains, linked backing is the one that keeps running. ## The wrong answers Two answers fail here. The first says "they are both O(n) space, so it does not matter" — true asymptotically, wrong by a factor of three in bytes. The second says "linked backing wastes nothing because it allocates exactly what it needs" — this counts the payload and ignores the pointer, the header and the padding, which for small values dominate. A strong answer names both sides' costs and identifies which pressure the actual system is under.
- For a hot parser stack that is pushed and popped constantly, which backing would you choose?Contiguous. Its push and pop are index arithmetic on adjacent slots, its elements are laid out in order, and one allocation covers many elements instead of one per push. A parser's stack depth is also usually modest and bounded, so the resize argument barely applies and the capacity can be reserved once. Linked backing would add an allocation per token and a pointer dereference per access for no benefit at that scale.
- At what payload size does the linked overhead stop mattering?When the value is large relative to the fixed per-node cost. A pointer plus header plus padding is a roughly constant number of bytes per node, so for a kilobyte-sized element it is noise, while for an 8-byte element it triples the footprint. The rule of thumb is to compare the payload against the fixed node cost: overhead matters when they are the same order of magnitude.
- Total free memory is plentiful but the array-backed growth fails — how?Contiguous backing needs one unbroken run of the requested size. A heap that has been churned by many allocations of varying sizes can hold a large total of free space carved into pieces smaller than the request, so the growth fails even though nothing is exhausted. Linked backing does not hit this, because it asks for element-sized pieces. Reserving the buffer early, before fragmentation accumulates, is the usual mitigation.
saying these in an interview costs you the question
- Says both are O(n) space so the choice is irrelevant
- Claims linked backing allocates exactly what it needs
- Forgets the old and new blocks coexist during a resize
- Ignores the per-element allocation count
- Assumes a large contiguous block is always obtainable