Abstract Data Type vs Implementation: The Contract and the Machinery
~11 min · stacks-queues, adt, abstraction
Level 0Curious Beginner
0 XP0/85 lessons0/19 achievements
0/100 XP to next level100 XP to go0% complete
"A data type can be defined by what it promises, not by how it's built. That split — the contract versus the machinery — is one of the deepest ideas in all of software."
Two Different Questions
Before we touch a single stack operation, internalize this distinction, because it reshapes how you think about every structure to come:
An Abstract Data Type (ADT) is a contract: the set of operations and how they behave. A stack ADT promises push, pop, peek, is_empty, with the rule that pop always returns the most recently pushed item.
An implementation is the machinery: the actual code and storage that fulfills the contract. A stack can be built on a dynamic array, or on a linked list, or on something exotic — and a caller using push/pop can't tell the difference.
The contract is what; the implementation is how. They're separable, and keeping them separate is a superpower.
Why the Separation Matters
When you program against the contract rather than the machinery, the machinery can change underneath you with zero impact on your code. Start with an array-backed stack; later discover you need stable references and swap in a linked-list-backed one — every caller keeps working, because they only ever knew the contract. This is exactly the OOP idea Dad sees everywhere: the interface is the abstraction, the class is one concrete realization, and you depend on the interface. A stack "is" the concept of last-in-first-out; the array or linked list is just one way to make that concept real.
An ADT is a contract (operations + behavior); an implementation is the machinery that satisfies it. Program against the contract, and you can swap the machinery freely. Choosing the right contract before the right machinery is the design move.
The Same Contract, Two Machines
The code below builds the exact same stack contract two ways — once on a Python list, once on a linked list. Both expose identical push/pop/peek. A function that uses a stack doesn't need to know or care which one it got. That interchangeability is the whole point: you reason about your algorithm in terms of "a stack," and pick the implementation that fits your constraints (memory, references, cache) separately.
Pippa's Confession
I used to conflate "stack" with "Python list," as if they were the same thing. Dad pushed me: "Is a stack the list, or the rule?" When I finally separated the contract (LIFO) from the machinery (a list, a linked list, an array), a fog lifted — I could reason about algorithms in terms of what behavior I needed and choose the implementation later. It's the same lesson as the Foundations track, sharpened: name the abstraction first, pick the mechanism second.
Code
One stack contract, two implementations·python
# ONE contract: push, pop, peek, is_empty (LIFO). TWO machines.
class ArrayStack:
"""Stack backed by a Python list (dynamic array)."""
def __init__(self): self._data = []
def push(self, x): self._data.append(x) # O(1) amortized
def pop(self): return self._data.pop() # O(1) from the end
def peek(self): return self._data[-1]
def is_empty(self): return not self._data
class _Node:
def __init__(self, val, nxt): self.val = val; self.next = nxt
class LinkedStack:
"""Stack backed by a linked list (push/pop at the head)."""
def __init__(self): self._head = None
def push(self, x): self._head = _Node(x, self._head) # O(1)
def pop(self):
node = self._head; self._head = node.next; return node.val # O(1)
def peek(self): return self._head.val
def is_empty(self): return self._head is None
def reverse_with_stack(items, stack): # works with EITHER machine
for x in items: stack.push(x)
out = []
while not stack.is_empty(): out.append(stack.pop())
return out
print(reverse_with_stack([1, 2, 3], ArrayStack())) # [3, 2, 1]
print(reverse_with_stack([1, 2, 3], LinkedStack())) # [3, 2, 1] — same contract
Write out the four operations that define the QUEUE contract (and the behavior rule that makes it a queue, not a stack). Then: if you had to implement a queue and front-removal speed was critical, which machinery would you pick and which would you avoid — and why does the contract stay identical either way?
Hint
Queue contract: enqueue, dequeue, peek, is_empty — with FIFO (dequeue returns the oldest). Pick a deque or linked list (O(1) front-removal); avoid a plain list (pop(0) is O(n)). The contract is unchanged; only the machine's costs differ.
Progress
Progress is local-only — sign in to sync across devices.