You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This final lesson steps back from individual structures and asks a more architectural question: not "how is a stack built?" but "what is a stack, independently of how it is built?" The answer is the idea of the abstract data type (ADT) — a structure described purely by what it does (its operations) rather than how it does it (its implementation). Every structure in this course — stacks, queues, lists, trees, graphs — can be viewed as an ADT, and doing so is one of the most powerful tools for writing software that is maintainable: code written against an ADT's interface keeps working even when the implementation underneath is completely replaced. The lesson develops the interface-versus-implementation distinction, revisits the course's structures as ADTs, explains why ADTs aid maintainability, and closes with the related static-versus-dynamic classification of how a structure uses memory. It is the natural capstone to the module and links directly forward to object-oriented programming.
This lesson addresses the H446 1.4.2 Data Structures content on abstract data types:
(Phrasing here paraphrases the specification content; it is not a verbatim quote.)
An abstract data type (ADT) is a logical, implementation-independent description of a data structure, defined by two things only:
Crucially, an ADT says nothing about how the data is stored or how the operations are carried out. It is a contract describing the interface (what a user can do) while deliberately hiding the implementation (how it is done underneath). The word abstract is doing the work: we abstract away the mechanism and keep only the behaviour.
A familiar analogy is a car's driving controls. The interface is the steering wheel, the accelerator and the brake: every driver knows what they do. The implementation — whether the engine is petrol, diesel or electric, how the brakes are hydraulic or regenerative — is hidden, and a driver can switch from one car to a completely different one without relearning to drive, because the interface is the same. An ADT offers a program exactly that: a stable set of controls behind which the engineering can change freely.
It helps to see why this abstraction is more than a tidy way of talking. Throughout this course you have studied structures from the inside: how a stack pushes by appending and pops by removing the last element, how a queue manages a front and a rear, how a BST follows pointers down to a leaf. That inside view is essential for building the structures, but it is exactly the wrong view for using them in a large program. A team writing, say, a web server does not want to think about whether the request queue is a circular array or a linked list every time it adds a request — it wants to think "add this request to the queue, take the next one off the queue" and nothing more. The ADT is what makes that possible: it lets the user of a structure reason at the level of behaviour ("a queue is first-in-first-out") while the author of the structure worries about the mechanism. Abstraction here is therefore a division of labour — it draws a clean line between the person who builds a component and the people who use it, and that line is what allows software to be built by large teams at all. This is the same idea of abstraction met in the computational-thinking course, now applied specifically to data: keep the behaviour that matters, discard the detail that does not.
This is the single most important distinction in the topic, so it is worth stating sharply:
| Interface (the ADT) | Implementation (the data structure) | |
|---|---|---|
| Answers | what can I do? | how is it done? |
| For a stack | push, pop, peek, isEmpty | an array + a top index, or a linked list |
| Seen by | the user of the structure | only the structure's author |
| Changes | rarely (it is a contract) | freely, without breaking users |
Everything met in this module can be described as an ADT by listing its operations and saying nothing about its internals. This is exactly how the specification expects you to characterise them.
| Operation | Effect |
|---|---|
push(item) | add an item to the top |
pop() | remove and return the top item |
peek() | return the top item without removing it |
isEmpty() | true when the stack holds no items |
Nothing here says whether the stack is an array or a linked list — only the last-in, first-out behaviour.
| Operation | Effect |
|---|---|
enqueue(item) | add an item to the rear |
dequeue() | remove and return the front item |
front() | return the front item without removing it |
isEmpty() | true when the queue holds no items |
Again purely behavioural: first-in, first-out, regardless of whether a circular array or a linked list sits underneath.
| Operation | Effect |
|---|---|
insert(index, item) | place an item at a position |
remove(index) | delete the item at a position |
get(index) | read the item at a position |
contains(item) | test whether an item is present |
size() | number of items |
| ADT | Characteristic operations |
|---|---|
| Tree | insert, delete, search, traverse |
| Graph | addVertex, addEdge, getNeighbours, hasEdge |
| Dictionary (map) | put(key, value), get(key), remove(key), containsKey(key) |
| Priority queue | insert(item, priority), removeHighest(), peekHighest() |
In every row, the ADT is the list of operations; the structure that fulfils them (a BST or hash table for a dictionary; a binary heap or sorted array for a priority queue) is a separate, hidden choice — which is precisely the next idea.
The pay-off of separating interface from implementation is that the same ADT can be realised by different data structures, each with different performance, and the choosing is invisible to the user:
| ADT | Implementation A | Implementation B | Trade-off |
|---|---|---|---|
| Stack | array + top index | singly linked list | array is cache-friendly; list grows without resizing |
| Queue | circular array | linked list | array bounds size; list is unbounded |
| List | array (random access) | linked list (cheap insert) | get is O(1) vs O(n); insert is O(n) vs O(1) |
| Dictionary | hash table | balanced BST | hash table O(1) average; BST keeps keys ordered |
| Priority queue | sorted array | binary heap | heap gives O(logn) insert and remove |
Consider the dictionary row. A program that needs key→value lookup writes its code against put/get/containsKey. Behind that interface the author might first use a hash table for O(1)-average lookup; later, discovering that the program also needs to list keys in order, they could swap in a balanced BST (whose in-order traversal yields sorted keys) — and not one line of the using code changes, because the interface is identical. That ability to change the engine without disturbing the driver is the whole point, and it is what makes ADTs so valuable for large systems.
The priority queue row reinforces the same lesson from a performance angle. The naive implementation is a sorted array: removeHighest is then trivial (take the end element) but insert is O(n) because the new item must be shifted into its sorted position. A far better implementation is a binary heap — a complete binary tree stored in an array — which gives both insert and removeHighest in O(logn). A program that started with the sorted-array version and later found insertion too slow can switch to the heap version purely by replacing the implementation behind the insert/removeHighest/peekHighest interface; every caller is untouched. Notice the recurring pattern across both examples: the interface is a fixed promise, and the implementation is a free variable the author can tune for speed, memory or ordering as the program's needs become clear. Choosing the right implementation for an ADT is itself a frequent exam task — for instance, "which structure should implement this dictionary, and why?" — and the answer always turns on the performance and ordering trade-offs the interface deliberately leaves open.
Maintainability — the ease of changing software safely over its lifetime — is where ADTs earn their keep, and the specification expects you to explain why. Three linked benefits follow from hiding the implementation behind an interface:
| Benefit | How the ADT delivers it |
|---|---|
| Modularity | each ADT is a self-contained unit that can be written, tested and understood on its own, so a large system decomposes into manageable parts |
| Reuse | a well-defined ADT (a stack, a dictionary) can be dropped into many different programs without modification |
| Flexibility / future-proofing | the implementation can be optimised or replaced without touching any code that uses the ADT, because users depend only on the interface |
| Safety | restricting access to a fixed set of operations stops users corrupting the internal state directly |
| Simplicity | a user need learn only the interface, not the (possibly intricate) implementation |
The mechanism that enforces all of this is encapsulation (information hiding) — bundling the data with its operations and exposing only the interface. In an object-oriented language this is done with a class whose internal data is private and whose operations are public:
# BAD: a bare list exposes the implementation; any code can corrupt it
stack = []
stack.append(10) # nothing stops a user inserting in the middle,
stack.insert(0, 99) # violating the LIFO contract entirely
# GOOD: a Stack ADT exposes only push/pop/peek; the list is hidden
class Stack:
def __init__(self):
self._items = [] # private: the chosen implementation
def push(self, item):
self._items.append(item)
def pop(self):
if not self._items:
raise IndexError("Stack underflow")
return self._items.pop()
def peek(self):
return None if not self._items else self._items[-1]
def is_empty(self):
return len(self._items) == 0
s = Stack()
s.push(10)
s.push(20)
print(s.pop()) # 20 -- LIFO guaranteed; no way to break it
The "good" version cannot be misused into violating last-in-first-out, because the only operations exposed are the LIFO ones — and if the author later replaces self._items with a linked list, every user keeps working untouched. This is the direct bridge to the object-oriented programming lesson: a class with private fields and public methods is the standard way to implement an ADT, and encapsulation is the principle that makes the interface/implementation split enforceable rather than merely a convention.
When an exam asks you to design an ADT, you specify the interface, not the code. A disciplined design states, for each operation, its name, inputs, outputs and behaviour, plus any pre-/post-conditions and edge cases (especially the empty structure). As a worked example, a Set ADT (a collection of unique values):
| Operation | Input | Output | Behaviour |
|---|---|---|---|
add(item) | item | — | add the item only if not already present |
remove(item) | item | — | remove the item if present |
contains(item) | item | boolean | is the item in the set? |
union(other) | a set | a set | all items in either set |
intersection(other) | a set | a set | items in both sets |
size() | — | integer | number of items |
isEmpty() | — | boolean | is the set empty? |
Notice this table mentions no storage mechanism. The set could be implemented with a list, a hash table or a balanced BST — the design is silent on that, exactly as it should be. A common exam error is to start writing for loops and arrays in answer to a design question: that describes an implementation, not an ADT, and loses the marks the question is testing.
A final classification — independent of the ADT idea but examined alongside it — concerns how a structure uses memory. A static data structure has a fixed size, fixed at compile time / creation, with memory allocated all at once and unchangeable thereafter; the classic example is the array. A dynamic data structure can grow and shrink at run time, allocating and freeing memory as needed; the classic examples are the linked list, tree and graph, all built from heap-allocated nodes joined by pointers.
| Static (e.g. array) | Dynamic (e.g. linked list) | |
|---|---|---|
| Size | fixed when created | grows/shrinks at run time |
| Memory | allocated once, contiguous | allocated per-node, scattered (heap) |
| Wasted space | possible (over-allocate) or overflow (under-allocate) | only what is needed at the time |
| Access | O(1) random access by index | O(n) — must traverse from the start |
| Overhead | none beyond the data | extra memory for pointers |
| Insertion/deletion | costly (shift elements) | cheap at a known node (re-link pointers) |
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.