Stack (linked list)

Cost and properties

push / pop	O(1) worst case
space	40n bytes (Java)
order	LIFO
overhead	one object + pointer per item

Reference: Sedgewick & Wayne, §1.3.

Stack (linked list) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class Stack:
    # Push and pop at the FRONT of a singly linked list: the only node we
    # ever touch is the first one, so the cost cannot depend on the size.

    class _Node:
        __slots__ = ('item', 'next')
        def __init__(self, item, nxt):
            self.item, self.next = item, nxt

    def __init__(self):
        self.first = None                 # top of the stack
        self.n = 0

    def push(self, item):
        self.first = Stack._Node(item, self.first)   # new node -> old first
        self.n += 1

    def pop(self):
        if self.first is None:
            raise IndexError('stack underflow')
        item = self.first.item
        self.first = self.first.next      # orphan the old head
        self.n -= 1
        return item

Why it works

The invariant

first points at the most recently pushed node, and each node points at the one pushed before it. That is the entire data structure: the list order is the LIFO order, so neither operation has to search or shift anything.

Why linked, not array

Cost per operation is constant in the worst case, which matters when a single slow operation is unacceptable (real-time systems, or an operation inside a tight inner loop). The price is memory: an extra reference per item plus object overhead — about 40 bytes per item in Java, versus ~8 for a resizing array. Compare with the resizing-array version: same API, opposite trade-off.

Loitering

The Java implementation must null out the popped reference or the array/node keeps the object alive — a loitering memory leak. Here, dropping first is enough because the orphaned node becomes unreachable immediately.

Why the API is a separate idea

The client sees only push, pop, is_empty. Two completely different implementations satisfy it, so a client written against the API can switch between them for performance without changing a line. That separation — API, then implementation, then cost — is the spine of the whole first course.

What to try in the animation

A word pushes it; a - pops. The default is the course's tobe.txt test string.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• tobe.txt (course) — to be or not to - be - - that - - - is
• push then drain — a b c d e - - - - -
• underflow — a - -

Open Stack (linked list) in the player →

The rest of Stacks and queues

• Stack (resizing array) Keep items in an array and double it when it fills.
• Queue (linked list) Enqueue at the back, dequeue from the front.