Published by Patrick Mutisya · 14 days ago
An Abstract Data Type (ADT) defines a data structure by specifying the operations that can be performed on it and the mathematical properties of those operations, without prescribing how the structure is implemented. The focus is on what the data type does, not how it does it.
The following three structures are classic examples of ADTs that you will encounter:
A stack follows the Last‑In‑First‑Out (LIFO) principle. The abstract operations are:
push(x) – insert element x on the top.pop() – remove and return the top element.top() – return the top element without removing it.isEmpty() – true if the stack contains no elements.Mathematically, if \$S\$ denotes the current sequence of elements (top on the right), then:
\$\text{push}(S, x) = S \cdot x\$
\$\$\text{pop}(S) = \begin{cases}
(S', x) & \text{if } S = S' \cdot x \\
\text{error} & \text{if } S = \varepsilon
\end{cases}\$\$
A queue follows the First‑In‑First‑Out (FIFO) principle. The abstract operations are:
enqueue(x) – insert element x at the rear.dequeue() – remove and return the front element.front() – return the front element without removing it.isEmpty() – true if the queue contains no elements.If \$Q = \langle q1, q2, \dots , q_n\rangle\$ denotes the ordered sequence (front on the left), then:
\$\text{enqueue}(Q, x) = \langle q1, q2, \dots , q_n, x\rangle\$
\$\$\text{dequeue}(Q) = \begin{cases}
( \langle q2, \dots , qn\rangle , q_1) & \text{if } n \ge 1 \\
\text{error} & \text{if } n = 0
\end{cases}\$\$
A linked list is a collection of nodes where each node contains data and a reference (link) to the next node. The abstract operations typically include:
insert(i, x) – insert element x at position i (0‑based).delete(i) – remove the element at position i.get(i) – retrieve the element at position i.size() – return the number of elements.isEmpty() – true if the list contains no elements.The ADT does not prescribe whether the list is singly‑linked, doubly‑linked, or circular; those are implementation choices.
| Property | Stack | Queue | Linked List |
|---|---|---|---|
| Access Order | LIFO – last element added is first removed | FIFO – first element added is first removed | Sequential – any position can be accessed (subject to traversal cost) |
| Typical Operations | push, pop, top, isEmpty | enqueue, dequeue, front, isEmpty | insert, delete, get, size, isEmpty |
| Common Implementations | Array (fixed size) or linked list | Array (circular buffer) or linked list | Singly‑linked, doubly‑linked, circular |
| Complexity (average case) | push/pop – \$O(1)\$ | enqueue/dequeue – \$O(1)\$ | insert/delete at head – \$O(1)\$; at arbitrary position – \$O(n)\$ |
By describing a stack, queue, or linked list as an ADT, we can:
Understanding the distinction between an ADT and its concrete implementation is essential for writing modular, maintainable code and for performing the algorithmic analysis required at A‑Level.