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.
Trace the top link through a push and pop
Push 4, then 9. The top node contains 9 and points to the earlier node containing 4. Pop returns 9 and replaces top with that earlier link. The next pop returns 4 and leaves an absent top. A later push must create a fresh valid stack without depending on the old nodes.
The linked implementation needs one endpoint because every operation uses the top. This differs from a queue, which needs access to both insertion and removal ends for constant-time operations. The node field named prev points toward the older stack entry.
Separate a returned node from a returned payload
Most versions return a node from peek and pop; Rust returns an optional integer. Neither policy permits a valid zero to mean empty. Tests normalize the observed payload while still checking the structural state. A consumer retaining a returned node may also retain the older chain if links remain attached.
Push, peek, and pop use O(1) structural work and O(n) retained node storage for n entries. Check empty peek/pop, one push/pop, repeated payloads, alternating operations, and draining then refilling. Also verify that peek does not remove the entry. A linked stack exposes pointer updates clearly, although a native growable array is often simpler when a product only needs stack behavior.
Python example and implementation choices
The stack's last attribute references the top Node, and None marks emptiness. Pop reads that node before advancing the endpoint, preserving the returned data. The original code leaves its prev link attached, so a retained removed node can keep older entries alive. Checking a node's presence rather than its payload ensures zero-valued entries are not mistaken for an empty stack.
Complete implementation
class Node:
def __init__(self, data):
self.data = data
self.prev = None
class Stack:
def __init__(self):
self.last = None
def peek(self):
return self.last
def push(self, item):
previous_last_item = self.last
self.last = Node(item)
self.last.prev = previous_last_item
return self.last
def pop(self):
removed_item = self.last
# Update `last` as long as we have items left in the stack
if removed_item:
self.last = removed_item.prev
return removed_item
Continue in Python
Open Implement a Stack for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Python example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The Python interview preparation guide connects these language choices with further practice and the cross-language operation reference.