What is a Dictionary (Abstract Data Type)?

A dictionary (also called a map or associative array) is an ADT that stores an unordered collection of key-value pairs. Each key is unique and is used to look up its associated value.

Dictionaries are typically implemented using hash tables, giving O(1) average-case operations.

Dictionary Operations

Dictionary as ADT vs Implementation

As an abstract data type, a dictionary defines the interface (what operations are supported) without specifying the underlying data structure. Common implementations:

• Hash table — O(1) average for lookup/insert/delete
• Balanced BST — O(log n) for all operations, but keeps keys sorted

Dictionaries in AQA Pseudocode

// AQA 7517 pseudocode — dictionary creation and access
student_grades ← {}   // empty dictionary

// Add key-value pairs
student_grades["Alice"] ← 85
student_grades["Bob"] ← 72
student_grades["Charlie"] ← 91

// Lookup
OUTPUT student_grades["Alice"]   // outputs 85

// Delete
REMOVE student_grades["Bob"]

Key Properties of Dictionaries

• Keys are unique — each key appears at most once
• Unordered — no guaranteed order of key-value pairs (unlike arrays)
• Mutable — key-value pairs can be added, removed, or updated
• Keys can be any hashable type — strings, integers, etc.
• Values can be any type — including lists, nested dictionaries

Applications

• Storing student records (student ID → name/grade)
• Configuration settings (setting name → value)
• Counting word frequencies (word → count)
• Implementing caches and lookup tables
• JSON data representation