Why can a linked-node stack hold millions of elements when a thread's call stack overflows far sooner?

## Three different things wearing one word The word *stack* names at least three separate ideas, and the confusion behind this question comes from collapsing them. 1. **The abstract data type.** A contract: `push`, `pop`, `peek`, an empty check, and the LIFO guarantee. It constrains the *order* elements come back, and nothing else. No storage, no capacity, no memory model. 2. **A realization of that contract.** Contiguous slots plus an index, or a chain of nodes each pointing at the one beneath. Both satisfy the contract; they differ in where the elements live and what bounds the depth. 3. **The machine's call stack.** A per-thread region of memory that the calling convention manages in LIFO order to hold call frames — return addresses, saved registers, local variables. It obeys the same discipline, which is why it carries the name, but it is a fixed hardware-and-runtime mechanism, not something you instantiate. Once those are separated, the question answers itself: (2) and (3) have different ceilings because they draw on different resources. ## Why a linked-node stack is bounded only by memory Each push allocates one node holding the element and a reference to the node beneath, then moves the head reference. Nodes come from the general-purpose allocator, so they can sit anywhere in the process's address space and need not be adjacent. There is no preallocated envelope to exhaust, so the depth ceiling is "how much memory can this process obtain" — millions of nodes if each node is small and memory is plentiful. Push and pop stay O(1), because both still touch exactly one node. The costs are real but different in kind: every element carries the overhead of a link (and of whatever the allocator's per-object bookkeeping costs), every push may involve an allocation, and traversal chases references that are scattered rather than adjacent, so it is much less friendly to caches than walking a contiguous block. ## Why the call stack is bounded far tighter When a thread is created, the system reserves one contiguous region for it and records the bounds. Frames are pushed by moving a stack pointer within that region — extremely cheap, no allocator involved, and perfect locality. The price of that design is that the region is a fixed reservation made in advance. It cannot be relocated once references point into it, and it cannot generally be extended into whatever happens to lie next to it. When the frames outgrow it, execution runs into the guard at the end and the thread fails. The size of that reservation is a deployment-scale decision, not a per-structure one: every thread pays for it, so runtimes pick defaults in the range of hundreds of kilobytes to a few megabytes rather than gigabytes. That is why frame depth ceilings land in the thousands-to-hundreds-of-thousands range while a data-structure stack in the same process shrugs at millions of elements. Mainstream ecosystems have not converged on one number here — operating systems and managed runtimes each pick their own default reservation, and several let you request a different one per thread — which is itself the tell that this is a policy knob on a fixed mechanism, not an intrinsic property of LIFO. ## Choosing between the two realizations of the ADT | | Contiguous array realization | Linked-node realization | |---|---|---| | depth ceiling | the chosen capacity | available memory | | per-element overhead | none beyond the slot | one link per node, plus allocator bookkeeping | | locality | excellent, elements adjacent | poor, nodes scattered | | per-push work | write a slot, move an index | allocate a node, move a reference | | memory profile | fixed and predictable up front | grows and shrinks with use | On a memory-capped device buffering unacknowledged readings, the contiguous realization is usually right: the ceiling is known, the memory is provably bounded, and the per-push cost has no allocator in it. Where the depth genuinely cannot be estimated and memory is plentiful, node-based storage removes the ceiling question at the price of overhead and locality. ## The sentence that shows you understand it "The stack data structure and the call stack share the LIFO discipline, not the mechanism: one is a contract I can realize over any memory I can obtain, the other is a fixed per-thread reservation made before my code runs." A candidate who says that will never mistake a full buffer for a thread overflow, or try to fix one with the remedy for the other.