Abstract Data Types
The idea the whole course rests on: separate what a structure does from how it does it. Say what operations exist and what they promise, and leave the implementation free to change without breaking anyone.
- Distinguish an abstract data type from a data structure.
- Write a specification a client can rely on.
- Say why the same ADT admits several implementations.
- Use preconditions to move responsibility deliberately.
Without the separation, every user of your code depends on its internals, and you can never change them. With it, you can replace the implementation entirely and nothing that uses it needs to know.
Every library API is an ADT. Python's list promises indexing
and appending without telling you it is a dynamic array; the interpreter has
changed how it works several times without breaking a single
program.
Barbara Liskov formalised abstract data types in the 1970s and won the Turing Award for it. Her rule, that a subtype must be usable wherever the supertype is expected, is now called the Liskov substitution principle and returns in Unit 10.
ADT versus data structure
One ADT, many possible structures. "Stack" is an ADT; a Python list and a linked list are two structures that implement it.
A Stack promises: put an item on top, take the top item off, ask whether it is empty. That is the whole contract.
# implementation A: a Python list, top at the end
class Stack:
def __init__(self) -> None:
self._items = []
def push(self, item) -> None:
self._items.append(item)
def pop(self):
return self._items.pop()
# implementation B: a Python list, top at the front
class Stack:
def __init__(self) -> None:
self._items = []
def push(self, item) -> None:
self._items.insert(0, item)
def pop(self):
return self._items.pop(0)A leading underscore, as in _items, marks an attribute as
internal. Python does not enforce it — client code can reach
in. The convention says: if you touch this and it breaks later, that is your
fault, not the implementer's.
Writing a specification
In CSC148H1 this is marked, so it is worth getting into the habit immediately.
def pop(self):
"""Remove and return the item most recently pushed onto this stack.
Preconditions: this stack is not empty.
>>> s = Stack()
>>> s.push(1)
>>> s.push(2)
>>> s.pop()
2
"""
return self._items.pop()Two defensible choices for popping an empty stack:
Either is fine. What is not fine is leaving it unsaid, so callers guess and half of them guess wrong.
Why the separation pays
Suppose client code is written against the Stack contract:
def reverse(items: list) -> list:
"""Return a new list with the items of items in reverse order.
>>> reverse([1, 2, 3])
[3, 2, 1]
"""
s = Stack()
for item in items:
s.push(item)
return [s.pop() for _ in range(len(items))]_items.Writing s._items.append(x) instead of
s.push(x) couples your code to the implementation. It works
today and breaks the moment the structure changes — and the error will
surface far from the line that caused it.
• Describing how in a docstring. The client does not care and
should not depend on it.
• Accessing another object's underscore attributes.
• Omitting preconditions and leaving edge behaviour
undefined.
• Confusing the ADT with one of its implementations. A stack is not "a
list with append and pop".
• Writing the code before the specification. The specification is what
tells you when the code is finished.
Practice
Write out each answer before opening it. Original exercises written for this guide in the style of the course's weekly work.
Is "queue" an ADT or a data structure?
Answer
Both stack implementations above are correct. Why prefer A?
Answer
Specify a first() method returning the front of a
queue.
Solution
def first(self):
"""Return the item at the front of this queue, without removing it.
Preconditions: this queue is not empty.
>>> q = Queue()
>>> q.enqueue(5)
>>> q.first()
5
"""What is wrong with this docstring?
def push(self, item) -> None:
"""Append item to the end of self._items."""Answer
Give two reasonable behaviours for dequeuing an empty queue.
Answer
Why can reverse above survive an implementation
change?
Answer
push, pop and the constructor — the public
contract. It never touches internals, so internals are free to
change.Write the operation list for a Set ADT.
Solution
Is it ever right to access another object's private attribute?
Answer
__eq__ works. Across classes, no. The boundary is the
class, not the object.Expanded topic checklist
Course coverage. This unit is part of the complete CSC148H1 topic map. It should cover the following items before you move on:
- ADT versus structure. What each term means and why one ADT admits many structures.
- Specifications. Type annotations, summary, preconditions, examples.
- Information hiding. The underscore convention and what it does and does not enforce.
- Design judgment. Choosing preconditions versus exceptions deliberately.
The calendar names "abstract data types" and "specifications" among the first topics. The course runs on its own notes; check Quercus for the required docstring format, which is marked on every assignment.
The contract is what clients depend on; the implementation is what you stay free to change. Every structure in this course is introduced as a contract first and code second.
Deep practice extensions
Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.
State the difference between an ADT and a data structure.
Guide
Does Python enforce privacy?
Guide
What does a precondition do?
Guide
Can two correct implementations differ in complexity?