AQA 7517 · Paper 1 · 4.2.8

Dictionaries
as Data Structures

AQA A-Level Computer Science · Section 4.2 Fundamentals of Data Structures

WHAT YOU'LL LEARN

Key-value pairs · Dictionary operations · Comparison with arrays · AQA pseudocode

AQA SPEC LINK

4.2.8 — Dictionaries as data structures

Dictionary Concept

What is a Dictionary?

A dictionary is an abstract data type that stores key-value pairs. Each key is unique and maps to a value. Also called an associative array or map.

phone = {"Alice": "07700900001", "Bob": "07700900002", "Carol": "07700900003"}

Access value by key: phone["Alice"] returns "07700900001"

Dictionary Operations

Dictionary Operations (AQA Pseudocode)

# Create dictionary
scores ← {}

# Add / update entry
scores["Alice"] ← 95
scores["Bob"] ← 88

# Read value
OUTPUT scores["Alice"]  # outputs 95

# Delete entry
DELETE(scores, "Bob")

Internal Implementation

How Dictionaries Work Internally

Most dictionary implementations use a hash table internally. The key is passed through a hash function to find the storage index.

key → hash function → index → store value at index

Lookup: same process — hash(key) → index → retrieve value

Collisions handled by chaining or probing (same as hash tables)

Average O(1) for all operations: add, search, delete, update

Properties

Dictionary Properties

KEY RULES

Keys must be unique

Keys must be immutable (e.g. string, integer)

Values can be any type, including lists or other dicts

VS ARRAYS

Arrays indexed by integer; dicts by any key

Dicts: O(1) lookup by key; arrays O(n) to search by value

Arrays ordered; dicts may not be ordered

Iterating Dictionaries

Iterating Over a Dictionary

# Iterate over key-value pairs
FOR EACH key IN scores
  OUTPUT key, " : ", scores[key]
ENDFOR

# Check if key exists
IF "Alice" IN scores THEN
  OUTPUT "Found"
ENDIF

Nested Dictionaries

Dictionaries of Dictionaries

Values can themselves be dictionaries, allowing complex nested structures:

students ← {
  "A001": {"name": "Alice", "grade": "A"},
  "A002": {"name": "Bob", "grade": "B"}
}

# Access nested value
OUTPUT students["A001"]["name"]  # Alice

Applications

Real-World Uses

Phone books — name (key) → number (value)

Student records — student ID (key) → details (value)

Word frequency count — word (key) → count (value)

JSON data — web APIs return data as key-value pairs (JavaScript Object Notation)

Caching — URL (key) → cached response (value)

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

A programmer uses a dictionary to store the prices of items:
prices = {"bread": 1.20, "milk": 0.89, "eggs": 2.50}
(a) Write pseudocode to add a new item "butter" with price 1.75. [1]
(b) Write pseudocode to output all items whose price is over £1.00. [3]
(c) State ONE advantage of using a dictionary over a 2D array to store this data. [1]

[5 marks]

1 mark

(a) prices["butter"] ← 1.75

3 marks

(b) FOR EACH item IN prices / IF prices[item] > 1.00 THEN OUTPUT item / ENDFOR

1 mark

Summary

Key Points to Remember

Dictionary = collection of key-value pairs; keys must be unique & immutable

Implemented using a hash table internally → average O(1) operations

Operations — add, retrieve, update, delete, iterate, check membership

vs Array — dict uses meaningful keys; array uses integer indices

Widely used: phone books, caches, JSON, frequency counting

🎉 Lesson complete — move to the quiz!