Abstract Data Type (ADT) – a logical description of a data structure that defines:
The ADT hides the underlying implementation (array, linked nodes, etc.). In the Cambridge 9618 Computer Science syllabus this distinction is expressed as the interface (what the ADT does) versus the implementation (how it does it).
| AS‑Level block (1‑12) | Relevant ADT content |
|---|---|
| 10 Data types & structures | Introduction to ADTs, Stack, Queue, Linked List (singly, doubly, circular) |
| 9 Algorithms | Use of stacks/queues in expression evaluation, BFS, back‑tracking |
| 8 Databases | Linked list as basis for dynamic storage (e.g., adjacency lists) |
| 11 Programming constructs | Implementing ADTs in pseudocode / a programming language |
| A‑Level extension block (13‑20) | Advanced ADT topics |
|---|---|
| 13 User‑defined data types | Designing custom ADTs (e.g., priority queue, deque) using linked structures |
| 14 File organisation | Linked‑list based file allocation tables |
| 15 Floating‑point representation | Stacks for expression evaluation involving real numbers |
| 16 Network protocols & switching | Queue models for packet buffering |
| 17 Parallel processing & virtual machines | Concurrent stacks/queues, lock‑free linked lists |
| 18 Boolean algebra & Karnaugh maps | Not directly ADT‑related – listed for completeness |
| 19 Operating system functions | Process control blocks stored in linked lists; ready queues |
| 20 Advanced algorithms & AI | Graph algorithms using adjacency‑list (linked list) representation; search trees |
push(x) – insert element x on the top.pop() – remove and return the top element.peek() – return the top element without removing it.isEmpty() – true iff the stack contains no elements.|push| – |pop| ≥ 0 (size never negative).x₁, x₂, …, xₙ the sequence of values returned by successive pop calls is xₙ, xₙ₋₁, …, x₁.pop / peek: !isEmpty().push: the new element becomes the top of the stack.pop or peek on an empty stack must raise an error (or return a sentinel such as null).push when the array is full must raise an error or trigger dynamic resizing.push, pop, peek, isEmpty – O(1).class StackNode:data
next
class Stack:
top ← null
push(x):
n ← new StackNode
n.data ← x
n.next ← top
top ← n
pop():
if top = null then error "under‑flow"
x ← top.data
top ← top.next
return x
peek():
if top = null then error "under‑flow"
return top.data
isEmpty():
return top = null
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 iff the queue contains no elements.size ≥ 0 at all times.x₁, x₂, …, xₙ the sequence of values returned by successive dequeue calls is x₁, x₂, …, xₙ.dequeue / front: !isEmpty().enqueue: the new element becomes the rear of the queue.dequeue or front on an empty queue raises an error or returns a sentinel.enqueue when the array is full must be handled.enqueue, dequeue, front, isEmpty – O(1) when a circular array or a linked list with front/rear pointers is used.next reference.class QueueNode:data
next
class Queue:
front ← null
rear ← null
enqueue(x):
n ← new QueueNode
n.data ← x
n.next ← null
if rear = null then
front ← rear ← n
else
rear.next ← n
rear ← n
dequeue():
if front = null then error "under‑flow"
x ← front.data
front ← front.next
if front = null then rear ← null
return x
front():
if front = null then error "under‑flow"
return front.data
isEmpty():
return front = null
next reference only.next and prev references.next points to the first node (singly or doubly).insert(pos, x) – place element x at position pos (0‑based index).delete(pos) – remove the element at position pos.search(x) – return the position of the first occurrence of x (or –1 if not found).traverse() – visit each node in order (often to display or process data).isEmpty() – true iff the list contains no nodes.#insert – #delete = length ≥ 0.next (and prev for doubly) points to exactly one other node or null (or to the head in a circular list).insert and delete, 0 ≤ pos ≤ length (or length‑1 for delete).insert(pos, x) the element x occupies position pos and all subsequent elements shift one position forward.pos < 0 or pos > length) – raise an error.delete on an empty list – under‑flow error.insert at head – O(1).insert at arbitrary position – O(n) (must traverse to pos).delete at head – O(1).delete at arbitrary position – O(n).search – O(n).traverse – O(n).class ListNode:data
next
class SinglyLinkedList:
head ← null
size ← 0
insert(pos, x):
if pos < 0 or pos > size then error "invalid position"
n ← new ListNode; n.data ← x
if pos = 0 then
n.next ← head
head ← n
else
cur ← head
for i from 0 to pos‑2:
cur ← cur.next
n.next ← cur.next
cur.next ← n
size ← size + 1
delete(pos):
if pos < 0 or pos ≥ size then error "invalid position"
if pos = 0 then
head ← head.next
else
cur ← head
for i from 0 to pos‑2:
cur ← cur.next
cur.next ← cur.next.next
size ← size - 1
search(x):
cur ← head; index ← 0
while cur ≠ null:
if cur.data = x then return index
cur ← cur.next; index ← index + 1
return -1
traverse():
cur ← head
while cur ≠ null:
output cur.data
cur ← cur.next
isEmpty():
return size = 0
Problem: Store a sequence of integers entered by a user and later retrieve them in reverse order.
n: stack.push(n).stack.pop() until isEmpty() is true.queue.enqueue(n).while !queue.isEmpty() { stack.push(queue.dequeue()); } then pop.list.insert(0, n). The list now stores the numbers in reverse order automatically.| Feature | Stack | Queue | Linked List |
|---|---|---|---|
| Access order | LIFO | FIFO | Sequential as defined by links (head‑to‑tail; doubly allows tail‑to‑head) |
| Core operations | push, pop, peek, isEmpty | enqueue, dequeue, front, isEmpty | insert, delete, search, traverse, isEmpty |
| Mathematical properties | Size ≥ 0; LIFO invariant | Size ≥ 0; FIFO invariant | Size ≥ 0; each node has exactly one next (and optionally one previous) link |
| Typical worst‑case time‑complexity | O(1) for all core operations | O(1) for all core operations (circular array or linked list) | O(1) at head/tail; O(n) for arbitrary position, search, traverse |
| Implementation options | Array (static/dynamic) or linked list | Circular array or linked list (front & rear pointers) | Node objects with next (and optionally prev); head (and tail) pointers |
| Memory use | Fixed (array) or dynamic (linked list) | Fixed (array) or dynamic (linked list) | Dynamic – one node per element plus link fields |
| Common applications | Expression evaluation, recursion, back‑tracking | Task scheduling, BFS, buffering streams | Dynamic collections, adjacency lists, implementing other ADTs |
| Exam relevance (AO) | AO1 (definition), AO2 (choose for reverse‑order problems), AO3 (compare with list/queue) | AO1 (definition), AO2 (model FIFO processes), AO3 (analyse circular array vs linked list) | AO1 (definition of nodes/links), AO2 (design a dynamic collection), AO3 (compare O(1) head insert vs O(n) arbitrary insert) |
Let S be a stack, Q a queue and L a singly linked list.
Stack
\[
\begin{aligned}
\text{push}(S, x) & = S \cup \{(top+1, x)\} \\
\text{pop}(S) & =
\begin{cases}
(S', x) & \text{if } S = S' \cup \{(top, x)\} \\
\text{error} & \text{if } S = \emptyset
\end{cases}
\end{aligned}
\]
Queue
\[
\begin{aligned}
\text{enqueue}(Q, x) & = Q \cup \{(rear+1, x)\} \\
\text{dequeue}(Q) & =
\begin{cases}
(Q', x) & \text{if } Q = \{(front, x)\} \cup Q' \\
\text{error} & \text{if } Q = \emptyset
\end{cases}
\end{aligned}
\]
Singly linked list
\[
\begin{aligned}
\text{insert}(L, pos, x) & = L \cup \{(pos, x)\} \\
\text{delete}(L, pos) & =
\begin{cases}
L' & \text{if } (pos, x) \in L \text{ and } L' = L \setminus \{(pos, x)\} \\
\text{error} & \text{if } pos \notin \text{valid positions}
\end{cases}
\end{aligned}
\]
| Extension topic | Key ideas | Typical exam task (AO) |
|---|---|---|
| Priority queue (heap‑based) | Elements have a priority; dequeue removes the highest‑priority element. Often implemented with a binary heap (array). | AO2 – design a priority‑queue for a hospital triage system; AO3 – compare O(log n) heap vs O(n) linked‑list implementation. |
| Deque (double‑ended queue) | Supports insertion and removal at both front and rear (addFront, addRear, removeFront, removeRear). | AO2 – choose a deque for a palindrome‑checking algorithm. |
| Circular linked list | Last node points back to the first; useful for round‑robin scheduling. | AO1 – define the structure; AO2 – write pseudocode for a round‑robin CPU scheduler. |
| Self‑adjusting lists (e.g., move‑to‑front heuristic) | After a successful search, the accessed node is moved to the head to improve future access time. | AO3 – analyse average‑case performance compared with a standard linked list. |
| Concurrent (thread‑safe) stacks/queues | Use of locks or lock‑free algorithms to allow multiple threads to operate safely. | AO2 – outline a simple lock‑based solution for a shared stack. |
Your generous donation helps us continue providing free Cambridge IGCSE & A-Level resources, past papers, syllabus notes, revision questions, and high-quality online tutoring to students across Kenya.