Lesson notes
These notes explain the problem and current implementation. They are a reading companion, not a verbatim transcript of the recording.
This lesson builds a stack by keeping a reference to the latest linked node. Each node points to the item that was previously on top. The API exposes push, pop, and peek, followed by an array-backed comparison. Both representations implement last-in, first-out order; their storage bookkeeping differs.
Link each new top to the old top
Pushing creates a node whose previous link contains the old top reference, then replaces the stack's top with that node. Starting empty, pushing A creates a node with no predecessor. Pushing B then makes B point to A. The latest value is reachable immediately without scanning older items.
Peeking inspects the current top while preserving it. Check the current API's returned shape when using the implementation: a node object and its data are different results. A wrapper can intentionally expose either, but its callers and tests must agree. Empty access also needs a clear rule rather than relying on an accidental property error.
Save the popped item before changing the reference
To pop, save the current top, move the top reference to its predecessor, then return the saved item. The current solution returns null only when the stack was already empty. Popping the final item returns that item and leaves the top empty. Checking emptiness only after updating the reference would incorrectly discard that last result.
Use a short operation trace: push A, push B, pop B, pop A, then pop from empty. Add another push afterward to check that the empty-to-nonempty transition still works. If you also track size, assert that it agrees with the reachable chain after every operation.
State the storage model behind the cost
The linked version performs a constant number of reference operations per method and stores one node per retained item. An array-backed stack can use its final position instead. Dynamic array growth makes append amortized constant time under geometric resizing; a particular resize can still copy all retained values.
Continue with Stacks for call-stack intuition and Valid Brackets for a concrete use. Open the current implementation and explain why each pop returns the formerly newest item even when it also empties the structure.