Abstraction is the process of hiding complex implementation details and exposing only the essential features of a system. In the context of ADTs:
- Users interact with the ADT through its interface (the operations)
- The implementation (arrays, linked lists, trees, etc.) is hidden
Modularisation is the decomposition of a system into self-contained modules, each responsible for one aspect of the problem. A module:
- Has a clear, well-defined interface
- Can be developed and tested independently
- Can be replaced without affecting other modules
KEY TAKEAWAY: ADTs are the primary tool for achieving both abstraction and modularisation in algorithm design. They let you reason about data at a high level without implementation concerns.
When you declare S = Stack.empty() and use push, pop, and top, you are working entirely at the abstract level:
- You do not need to know if the stack is backed by an array or a linked list
- Your algorithm is correct for any correct implementation
- The implementation can change (for performance reasons) without modifying your algorithm
This is the separation of concerns principle — algorithmic concerns are separate from data-structure concerns.
A large problem is broken into modules:
Problem: Route-finding in a city
├── Module 1: Graph ADT (represent the road network)
├── Module 2: Priority Queue ADT (support Dijkstra's algorithm)
├── Module 3: Dictionary ADT (store shortest distances)
└── Module 4: Dijkstra's algorithm (uses Modules 1, 2, 3)
Each module is defined by its ADT signature. Module 4 does not know how the graph stores edges — only that it can call neighbours(v).
| Level | What You See | Example |
|---|---|---|
| Problem domain | Real-world entities | Cities, roads, distances |
| ADT level | Abstract data + operations | Graph, vertices, addEdge |
| Implementation | Data structures | Adjacency list, dictionary |
| Hardware | Memory, bits | Bytes in RAM |
Good algorithm design works at the ADT level, not the implementation level.
Problem: Model a university enrolment system.
A modular ADT-based design:
- Student represented as a Dictionary (studentID → attributes)
- Course represented as a Set (enrolled student IDs)
- Waitlist represented as a Queue (FIFO enrolment order)
- Schedule conflicts represented as a Graph (courses as nodes, conflicts as edges)
Each ADT can be implemented independently; the enrolment algorithm works with any correct implementations.
EXAM TIP: VCAA exams may ask you to describe how modularisation and abstraction are achieved through ADTs. Mention: (1) interface vs. implementation separation, (2) independent module development, and (3) how ADT operations correspond to problem operations.
| Benefit | Explanation |
|---|---|
| Simplicity | Work at the problem’s natural level of abstraction |
| Reusability | ADT implementations reused across algorithms |
| Maintainability | Change implementation without changing algorithms |
| Testability | Test modules independently with mock implementations |
| Team collaboration | Teams work on different modules simultaneously |