Use a stack, queue and linked list to store data

10.4 Introduction to Abstract Data Types (ADT)

Abstract Data Type (ADT) – a logical description of a data structure that defines:

• the set of values it can hold,
• the operations that may be performed on those values,
• the mathematical properties (invariants, pre‑ and post‑conditions) each operation must satisfy.

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).

1. Syllabus mapping – where ADTs sit in the Cambridge programme

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

Exam‑focus (AO) reminder

• AO1 – Knowledge & understanding: define an ADT, list its core operations, state invariants.
• AO2 – Application: choose the appropriate ADT for a given problem, write pseudocode for its operations.
• AO3 – Analysis: compare time‑complexity, memory use and suitability of different ADT implementations.

---

2. Stack – LIFO (Last‑In‑First‑Out)

2.1 Interface (operations)

• 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.

2.2 Mathematical properties

• Invariant: |push| – |pop| ≥ 0 (size never negative).
• LIFO property: for pushes x₁, x₂, …, xₙ the sequence of values returned by successive pop calls is xₙ, xₙ₋₁, …, x₁.
• Pre‑condition for pop / peek: !isEmpty().
• Post‑condition for push: the new element becomes the top of the stack.

2.3 Error handling

• Under‑flow: calling pop or peek on an empty stack must raise an error (or return a sentinel such as null).
• Overflow: only for a fixed‑size array implementation; a push when the array is full must raise an error or trigger dynamic resizing.

2.4 Complexity (worst‑case)

• push, pop, peek, isEmpty – O(1).

2.5 Implementation options

• Array‑based – static array (fixed capacity) or dynamic array that doubles in size when full.
• Linked‑list based – each node stores an element and a reference to the next node; the head of the list is the top of the stack.

2.6 Example pseudocode (linked‑list implementation)

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

2.7 Common applications (exam‑relevant)

• Evaluation of postfix (Reverse Polish) expressions.
• Function‑call management – the call stack.
• Back‑tracking problems (maze solving, puzzle solving).

---

3. Queue – FIFO (First‑In‑First‑Out)

3.1 Interface (operations)

• 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.

3.2 Mathematical properties

• Invariant: size ≥ 0 at all times.
• FIFO property: for enqueues x₁, x₂, …, xₙ the sequence of values returned by successive dequeue calls is x₁, x₂, …, xₙ.
• Pre‑condition for dequeue / front: !isEmpty().
• Post‑condition for enqueue: the new element becomes the rear of the queue.

3.3 Error handling

• Under‑flow: dequeue or front on an empty queue raises an error or returns a sentinel.
• Overflow: only for a fixed‑size array implementation; an enqueue when the array is full must be handled.

3.4 Complexity (worst‑case)

• enqueue, dequeue, front, isEmpty – O(1) when a circular array or a linked list with front/rear pointers is used.

3.5 Implementation options

• Circular array – fixed capacity, wrap‑around indices for front and rear.
• Linked list – maintain pointers to both front and rear nodes; each node stores a single next reference.

3.6 Example pseudocode (linked‑list implementation)

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

3.7 Common applications (exam‑relevant)

• Task scheduling – printer queues, CPU job queues.
• Breadth‑first search (BFS) of graphs.
• Buffering streams of data (e.g., keyboard input, network packets).

---

4. Linked List – dynamic collection of nodes

4.1 Variants

• Singly linked list – each node has a next reference only.
• Doubly linked list – each node has next and prev references.
• Circular linked list – the last node’s next points to the first node (singly or doubly).

4.2 Interface (core operations)

• 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.

4.3 Mathematical properties

• Invariant: #insert – #delete = length ≥ 0.
• Link uniqueness: each node’s next (and prev for doubly) points to exactly one other node or null (or to the head in a circular list).
• Pre‑conditions: for insert and delete, 0 ≤ pos ≤ length (or length‑1 for delete).
• Post‑conditions: after insert(pos, x) the element x occupies position pos and all subsequent elements shift one position forward.

4.4 Error handling

• Invalid position (e.g., pos < 0 or pos > length) – raise an error.
• Attempting delete on an empty list – under‑flow error.

4.5 Complexity (worst‑case)

• 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).

4.6 Implementation sketch (singly linked list)

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

4.7 Common applications (exam‑relevant)

• Dynamic collections where the size changes frequently.
• Adjacency‑list representation of graphs.
• Implementation of other ADTs – stacks and queues can be built from linked lists.

---

5. Choosing the appropriate ADT – worked example

Problem: Store a sequence of integers entered by a user and later retrieve them in reverse order.

1. Stack
   • For each input n: stack.push(n).
   • When reverse order is required, repeatedly call stack.pop() until isEmpty() is true.
   • Justification (AO2): The LIFO property guarantees the required reverse sequence with a single ADT – no extra work.
2. Queue
   • Enqueue each input: queue.enqueue(n).
   • To obtain reverse order, transfer all elements to a stack: while !queue.isEmpty() { stack.push(queue.dequeue()); } then pop.
   • Justification: A queue alone yields FIFO order; an additional stack is needed, making the stack the more direct choice.
3. Linked List
   • Insert each new integer at the head: list.insert(0, n). The list now stores the numbers in reverse order automatically.
   • Alternatively, insert at the tail (preserving input order) and traverse the list backwards – possible only with a doubly linked list.
   • Justification: Head insertion is O(1) and yields the required order, but extra pointer management of a doubly linked list is unnecessary if only reverse retrieval is needed.

---

6. Comparison of Stack, Queue and Linked List

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)

---

7. Formal notation (optional for higher‑level study)

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 otin \text{valid positions} \end{cases} \end{aligned} \]

---

8. A‑Level extensions – deeper ADT concepts

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.

Summary of A‑Level extensions

• All A‑Level topics build on the core ADTs covered in sections 2‑4.
• When answering exam questions, always start by stating the relevant ADT, its invariants and then justify why it meets the problem requirements (AO2).
• Where the question asks for analysis, compare time‑complexity and memory usage against the basic implementations (AO3).

---

9. Quick revision checklist (exam‑ready)

• Define abstract data type and differentiate interface vs implementation.
• List the core operations, invariants and typical complexities for stack, queue and linked list.
• Be able to sketch pseudocode for an array‑based and a linked‑list‑based implementation of each ADT.
• Identify which ADT is most suitable for a given real‑world scenario (e.g., undo feature → stack; printer jobs → queue; dynamic collection → linked list).
• Recall A‑Level extensions (priority queue, deque, circular list, self‑adjusting list, concurrent structures) and the key reasons they are introduced.
• Know the AO mapping: definition → AO1, choice/design → AO2, comparison/analysis → AO3.