Sequence 12 — Advanced Data Structures

Graphs, trees, binary search trees and hash tables, building on Year 12's arrays, ADTs, queues, stacks and dictionaries. AQA 4.2.7–4.2.9.

Retrieval of Year 12 Data Structures & Introduction to Graphs

  • Explain why different data structures exist
  • Describe the characteristics of graphs
Lesson ready

Representing Graphs

  • Represent graphs using adjacency matrices and adjacency lists
  • Implement graph operations (add vertex, add edge, check for an edge, find neighbours)
Lesson ready

Trees and Tree Traversal

  • Identify tree terminology (root, parent, child, leaf, height, depth)
  • Explain how a tree relates to, and differs from, a general graph
Lesson ready

Binary Search Trees

  • Explain the binary search tree (BST) property
  • Implement insertion and search for a BST
Lesson ready

Hash Tables and Hashing

  • Explain the hash function, bucket/index and collision mechanism in genuine technical depth
  • Implement a basic hash table using a hash function and a fixed-size bucket array
Lesson ready

Collision Handling in Hash Tables

  • Explain why collisions are inevitable in a fixed-size hash table
  • Implement collision handling using separate chaining
Lesson ready

Comparing Data Structures

  • Compare the performance characteristics of arrays, graphs, BSTs and hash tables
  • Apply Year 12 algorithm-performance analysis to Year 13's new data structures
Lesson ready