Show understanding that a stack, queue and linked list are examples of ADTs

10.4 Introduction to Abstract Data Types (ADT)

An Abstract Data Type (ADT) defines what a data structure does – the collection of values it holds and the operations that can be performed on those values – without prescribing how those operations are implemented. In Cambridge International AS & A‑Level Computer Science (9618) the ADT is the contract that client code relies on; the concrete data structure (array, linked list, circular buffer, …) is the implementation that fulfils that contract.

Key Characteristics of an ADT

• Encapsulation: data and the operations that manipulate it are bundled together.
• Well‑defined interface: a fixed set of operations (the contract) that the ADT guarantees.
• Implementation independence: the same ADT can be realised with arrays, linked structures, buffers, etc.
• Behaviour described by axioms or contracts: e.g. LIFO for a stack, FIFO for a queue, sequential access for a linked list.

Why ADTs Matter in the Cambridge Syllabus

• Provide a language for reasoning about correctness (AO2).
• Allow you to swap implementations without changing client code (AO3).
• Many exam questions ask you to choose the most suitable ADT for a given problem.
• Paper 4 tasks require you to implement at least one ADT in a permitted language (Java, Python, Visual Basic).

Canonical ADTs Examined in the Curriculum

The three ADTs that are explicitly examined are Stack, Queue and Linked List. Each is introduced abstractly first, then linked to possible concrete implementations.

1. Stack ADT

Concept: Last‑In‑First‑Out (LIFO). The most recently added element is the first that can be removed.

def push(S, x):
S.append(x)          # O(1) for list‑based implementation

def pop(S):
if not S:
raise IndexError('pop from empty stack')
return S.pop()       # O(1)

def top(S):
if not S:
raise IndexError('top of empty stack')
return S[-1]         # O(1)

def isEmpty(S):
return len(S) == 0

Mathematical description (optional):

\[

\text{push}(S,x)=S\cdot x,\qquad

\text{pop}(S)=\begin{cases}

(S',x) &\text{if }S=S'\cdot x\\[2mm]

\text{error} &\text{if }S=\varepsilon

\end{cases}

\]

Typical concrete implementations – fixed‑size array with a “top” index, or a singly‑linked list where push inserts at the head.

2. Queue ADT

Concept: First‑In‑First‑Out (FIFO). The earliest added element is the first that can be removed.

def enqueue(Q, x):
Q.append(x)          # O(1) for list‑based implementation

def dequeue(Q):
if not Q:
raise IndexError('dequeue from empty queue')
return Q.pop(0)      # O(n) for list; O(1) for circular buffer or linked list

def front(Q):
if not Q:
raise IndexError('front of empty queue')
return Q[0]          # O(1)

def isEmpty(Q):
return len(Q) == 0

Mathematical description (optional):

\[

\text{enqueue}(Q,x)=\langle q1,\dots ,qn,x\rangle,\qquad

\text{dequeue}(Q)=\begin{cases}

(\langle q2,\dots ,qn\rangle , q_1) &\text{if } n\ge1\\[2mm]

\text{error} &\text{if } n=0

\end{cases}

\]

Typical concrete implementations – circular array (fixed size) or a singly‑linked list with pointers to both front and rear.

3. Linked‑List ADT

Concept: An ordered collection of nodes, each containing data and a reference to the next node (and optionally the previous node). The ADT does not prescribe whether the list is singly‑, doubly‑ or circularly linked – those are implementation choices.

def insert(L, i, x):
if i < 0 or i > L.size:
raise IndexError('bad index')
new = Node(x)
if i == 0:                 # insert at head
new.next = L.head
L.head = new
else:
prev = node_at(L, i-1)
new.next = prev.next
prev.next = new
L.size += 1

def delete(L, i):
if i < 0 or i >= L.size:
raise IndexError('bad index')
if i == 0:
L.head = L.head.next
else:
prev = node_at(L, i-1)
prev.next = prev.next.next
L.size -= 1

def get(L, i):
if i < 0 or i >= L.size:
raise IndexError('bad index')
return node_at(L, i).data

def size(L):
return L.size

def isEmpty(L):
return L.size == 0

Implementation variants:

• Singly‑linked list – fast insertion/deletion at the head (O(1)).
• Doubly‑linked list – fast insertion/deletion at both ends (O(1) for tail operations).
• Circular linked list – useful for round‑robin scheduling.

Comparison of the Three ADTs

Link to the Cambridge Syllabus (AO1‑AO3)

• AO1 – Knowledge: Define each ADT, list its operations, and state its abstract properties (LIFO, FIFO, sequential access).
• AO2 – Analysis: Given a problem statement, decide which ADT best satisfies the requirements and justify the choice (e.g., “use a stack for expression evaluation”).
• AO3 – Design & Implementation: Write pseudocode or real code that implements the ADT, develop test cases, and analyse time/space efficiency.

Typical exam tasks:

1. Write pseudocode for push and pop and explain why each runs in O(1).
2. Choose an appropriate ADT for a “print queue” and describe how you would implement it with a circular buffer.
3. Given a sequence of operations on a linked list, draw the list after each step (testing understanding of pointers).
4. Convert an array‑based stack implementation to a linked‑list version without changing the client code.

Practical Activities (Paper 4 preparation)

• Lab 1 – Stack: Implement a stack in Java and Python, write JUnit/pytest test cases, and measure runtime for 10⁶ push/pop operations.
• Lab 2 – Queue: Build a circular‑buffer queue, then replace it with a linked‑list version; compare memory usage.
• Lab 3 – Linked List: Implement singly‑ and doubly‑linked lists, add insert and delete at arbitrary positions, and demonstrate edge‑case handling (empty list, index out of range).
• Mini‑project: Design a text‑editor “undo” feature using two stacks (undo/redo) – this integrates multiple ADTs and highlights the importance of abstraction.

Quick Audit Checklist – Have You Covered the Syllabus?

Actionable Improvement Suggestions (once your full lecture notes are available)

1. Map every syllabus sub‑topic to a note section using the checklist above. Highlight any gaps in red and add the missing material.
2. Integrate examples that mirror past paper questions. For each ADT, include a short “exam‑style” scenario (e.g., evaluating a postfix expression with a stack) and a step‑by‑step solution.
3. Provide side‑by‑side pseudo‑code vs real code (Java and Python) for at least one concrete implementation of each ADT. This satisfies AO3 requirements and aids students who prefer a specific language.
4. Include a concise “contract” box for each ADT that lists the operations, their pre‑conditions, post‑conditions and expected time complexity. This reinforces the abstract nature of the ADT.
5. Add quick‑reference tables for:

   • Time/space complexity of each operation (array vs linked implementation).
   • When to prefer a stack, queue or linked list (decision‑making flowchart).

6. Embed self‑checking questions after each major section (e.g., “What will be the output of the following sequence of stack operations?”) with answer keys.
7. Link theory to practical tasks by stating the exact AO3 assessment criteria that each lab or mini‑project satisfies.
8. Ensure consistent terminology with the official syllabus (e.g., use “enqueue”/“dequeue” rather than “add”/“remove” for queues).
9. Review formatting – headings should follow a logical hierarchy (h2, h3, h4), tables must have clear captions, and code blocks should be uniformly indented.
10. Proofread for accuracy – verify that all mathematical descriptions, complexity claims and example outputs are correct.

Summary

Stacks, queues and linked lists are the cornerstone ADTs for Cambridge International Computer Science. Mastering them at the abstract level enables you to:

• Reason about algorithmic correctness (AO2).
• Design flexible programs that can change implementation without affecting client code (AO3).
• Answer a wide range of knowledge, analysis and programming questions in the examinations.

Use the tables, pseudocode, and checklist in this note as a quick‑reference guide while studying, practising programming, or revising for the exams.