SLIDE 1
CSZone.co.uk
Click to advance · Arrow keys also work
CAIE 9618 · Paper 2 · Topic 2.2.4

Abstract
Data Types

Stacks · Queues · Linked Lists · Trees · Graphs

CSZone Cambridge International AS & A Level Computer Science 9618
Abstract Data Type

Defined by Behaviour, Not Implementation

An Abstract Data Type (ADT) is a data structure defined by the operations it supports and the rules governing those operations — independently of how it is implemented in memory. The user of an ADT knows what it does; not how it does it.
KEY ADTs IN CAIE 9618
Stack (LIFO)
Queue (FIFO)
Linked List
Binary Tree
Graph
WHY ABSTRACT?
Separates interface from implementation. A stack can use an array or linked list internally — the calling code doesn't need to change. Promotes modularity and reuse.
Stack — LIFO

Last In, First Out

A stack allows insertion and removal only at the top. Think of a stack of plates — you can only add or remove from the top.
OPERATIONS
Push(item) — add to top
Pop() — remove & return top
Peek() — read top (no remove)
isEmpty() — TRUE if empty
isFull() — TRUE if full
REAL-WORLD USES
Call stack (function calls)
Undo/redo in editors
Browser back button
Expression evaluation
Depth-first search
Stack pointer (SP) tracks the index of the top element. Push increments SP; Pop decrements it.
Queue — FIFO

First In, First Out

A queue adds at the rear and removes from the front. Like a queue at a ticket office — first to arrive is first served.
OPERATIONS
Enqueue(item) — add to rear
Dequeue() — remove from front
Peek() — read front item
isEmpty() — TRUE if empty
isFull() — TRUE if full
CIRCULAR QUEUE
Uses modular arithmetic so the rear pointer wraps around to the start of the array, reusing freed slots. Avoids wasted space from a linear queue.
USES
Print spoolers, CPU scheduling, breadth-first search, keyboard buffer.
Linked List

Dynamic Chain of Nodes

A linked list is a sequence of nodes, each containing a data field and a pointer to the next node. The last node's pointer is NULL (or –1).
OPERATIONS
Find(item) — traverse from head
Insert(item) — update pointers
Delete(item) — bypass node
isEmpty() — head = NULL?
ADVANTAGES vs ARRAYS
Dynamic size — grows/shrinks at runtime
Insertion/deletion: O(1) if pointer known
No shifting elements needed
Disadvantage: no direct (random) access — must traverse from head
In CAIE pseudocode, linked lists use parallel arrays: one for data values, one for pointer (next) values, plus a startPointer (head) and freePointer (next free slot).
Binary Tree

Hierarchical Node Structure

A binary tree is a tree where each node has at most two children (left and right). A binary search tree (BST) keeps left < root < right for all nodes.
KEY TERMS
Root — topmost node, no parent
Leaf — node with no children
Left/Right child — child pointers
Height — longest root-to-leaf path
BST OPERATIONS
Insert — compare & traverse left/right
Search — O(log n) average
Traversals — pre-order, in-order, post-order
IN-ORDER TRAVERSAL
Left → Root → Right. Visits BST nodes in ascending order.
Graph

Vertices and Edges

A graph is a set of vertices (nodes) connected by edges (arcs). Edges can be directed or undirected, and weighted or unweighted.
TYPES
Directed — edges have direction (digraph)
Undirected — edges go both ways
Weighted — edges carry a cost/distance
Unweighted — edges have no value
REPRESENTATIONS
Adjacency matrix — 2D array; good for dense graphs; O(V²) space
Adjacency list — array of lists; good for sparse graphs; O(V+E) space
USES
Road networks, social networks, internet routing, dependency graphs.
Exam Practice

Cambridge-style questions

Question 1
A program uses a stack implemented with an array of size 5. Show the state of the stack and stack pointer after: Push(10), Push(20), Push(30), Pop(), Push(40). State the value returned by Peek().
4 marks
After Push(10): stack=[10], SP=0
After Push(20): stack=[10,20], SP=1
After Push(30): stack=[10,20,30], SP=2
After Pop(): returns 30, stack=[10,20], SP=1  1
After Push(40): stack=[10,20,40], SP=2  1
Peek() returns 40 (top of stack, SP=2)  1
SP correctly tracked throughout  1
Exam Practice

Cambridge-style questions

Question 2
Describe how a binary search tree (BST) would store the values 15, 8, 22, 4, 12 when inserted in that order. Draw the resulting tree structure and state the result of an in-order traversal.
5 marks
Root = 15. Insert 8: 8 < 15 → left child of 15. Insert 22: 22 > 15 → right child of 15. 2
Insert 4: 4 < 15 → left, 4 < 8 → left child of 8. 1
Insert 12: 12 < 15 → left, 12 > 8 → right child of 8. 1
In-order traversal (Left→Root→Right): 4, 8, 12, 15, 22 — ascending order. 1
Common Mistakes

Don't lose easy marks

1
Confusing stack (LIFO) with queue (FIFO) — always state the order principle. A stack removes from where it inserted; a queue removes from the opposite end.
2
Forgetting that Pop() is destructive — it removes the item AND returns it. Peek() only reads the top without removing. Candidates often confuse these two operations.
3
In a BST question, not showing the comparison process step by step. Examiners award marks for showing each left/right decision made during insertion or search, not just the final tree.
Topic Summary — 2.2.4

What You Need to Know

STACK & QUEUE
Stack: LIFO · Push/Pop/Peek/isEmpty
Queue: FIFO · Enqueue/Dequeue/Peek
Both can be implemented as arrays or linked lists
LINKED LIST
Nodes with data + pointer
Dynamic size, efficient insert/delete
No random access — must traverse from head
BINARY TREE
Each node ≤ 2 children
BST: left < root < right
In-order = ascending order
GRAPH
Vertices + edges (directed/undirected, weighted/unweighted)
Adjacency matrix vs adjacency list
CSZone

Next Topic

2.3.1
Stacks & Queues in Practice
Implementation · Pseudocode · Worked examples
Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools