Choosing the Right Data Structure

This lesson synthesises everything you have learned about data structures and provides a framework for choosing the most appropriate data structure for a given problem. This is a critical skill for A-Level Computer Science exams, where you will be expected to justify your choices.

---

Why the Choice Matters

The choice of data structure affects:

• Time complexity — how fast operations are.
• Space complexity — how much memory is used.
• Code complexity — how easy the code is to write and maintain.
• Scalability — how well the solution handles growing data.

Choosing the wrong data structure can lead to slow, memory-hungry, or overly complex programs. Choosing the right one can make the solution elegant and efficient.

---

Decision Framework

When choosing a data structure, ask these questions:

Question	Guides You Toward
Is the size known in advance?	Static (array) or dynamic (linked list, tree)
Do I need fast access by index?	Array (O(1) access)
Do I need fast access by key?	Hash table (O(1) average)
Do I need sorted data?	BST (in-order traversal) or sorted array
Do I need LIFO access?	Stack
Do I need FIFO access?	Queue
Do I need priority-based access?	Priority queue (heap)
Are insertions/deletions frequent?	Linked list or BST
Do I need to model relationships?	Graph
Do I need to model hierarchies?	Tree

---

Comparison of All Data Structures

Data Structure	Access	Search	Insert	Delete	Space	Best For
Array	O(1)	O(n) linear / O(log n) binary	O(n)	O(n)	O(n)	Random access, known size
Linked List	O(n)	O(n)	O(1) at head	O(n) find + O(1) remove	O(n)	Frequent insertions/deletions
Stack	O(1) top	O(n)	O(1) push	O(1) pop	O(n)	LIFO operations, recursion
Queue	O(1) front	O(n)	O(1) enqueue	O(1) dequeue	O(n)	FIFO operations, scheduling
Hash Table	N/A	O(1) avg	O(1) avg	O(1) avg	O(n)	Key-value lookup, dictionaries
BST	O(log n)	O(log n) avg	O(log n) avg	O(log n) avg	O(n)	Sorted data, range queries
Graph	O(1) adj. matrix	O(V+E) BFS/DFS	O(1) edge	O(1) edge	O(V^2) or O(V+E)	Relationships, networks

---

Scenario-Based Analysis

Scenario 1: Student Records System

Requirements: Store 200 student records with name, ID, and grade. Need fast lookup by student ID.

Best choice: Hash table with student ID as the key.

Justification: Hash tables provide O(1) average-case lookup by key. The fixed number of students (200) means the hash table can be sized appropriately with a low load factor.

Alternative: An array of records sorted by ID with binary search would also work (O(log n) search), but insertions would be slower (O(n) shifting).

Scenario 2: Undo Feature in a Text Editor

Requirements: Track changes so that the user can undo the most recent change.

Best choice: Stack.

Justification: The undo operation always reverts the most recent change — this is LIFO behaviour, which is exactly what a stack provides. Push each change onto the stack; pop to undo.

Scenario 3: Print Job Scheduler

Requirements: Process print jobs in the order they are submitted.

Best choice: Queue (circular queue for efficiency).

Justification: Print jobs should be processed in FIFO order — the first job submitted should be printed first. A circular queue efficiently reuses array space.

Scenario 4: Autocomplete Dictionary