Exam Board:
OCR A-Level
4.2 - Data Structures
Specification:
Computer Science H446
Watch on YouTube:
Arrays
Records
Lists & tuples
Stacks
Queues
Linked lists
Trees
Graphs
Hash tables
Data structures are used to organise and store data so it can be accessed and processed efficiently, often through the use of an index or reference. They can be static, meaning their size is fixed during program execution, or dynamic, allowing them to grow or shrink as data changes.
Arrays
An array is a data structure that stores a collection of items of the same data type, with each item accessed using an index.
​
-
A one-dimensional (1D) array is a simple sequence of values, such as test scores for a single person: scores = [12, 15, 18, 20].
​
-
A two-dimensional (2D) array is like a table or grid, made up of rows and columns - for example, storing a timetable or test scores for a class.
-
A three-dimensional (3D) array stores data in multiple layers, like a series of 2D grids. For example, test scores for a class across multiple subjects.
Records
A record groups together related but different types of data under one name. Each individual piece of data within a record is called a field and each field can have a different data type (e.g. string, integer, Boolean).
​
For example, a student record might include fields such as Name (string), Age (integer) and Enrolled (Boolean). Records are often used in databases or programming to represent real-world entities where multiple attributes need to be stored together.
Lists & Tuples
A list stores an ordered collection of items, which can be changed (mutable) after creation. Items in a list can be added, removed or modified, and they can be of different data types. For example, in Python: myList = [10, "apple", True].
​
A tuple is similar to a list but is immutable, meaning its contents cannot be changed once created. Tuples are often used for fixed sets of data that should not be altered, such as coordinates or dates. For example: myTuple = (3, 5, 7).
Stacks
A stack stores data in a last in, first out (LIFO) order, meaning the most recently added item is the first one to be removed. It works much like a stack of plates - you can only add or remove from the top.
​
Two integral functions are push and pop. The push operation adds (or “pushes”) a new item onto the top of the stack. The pop operation removes (or “pops”) the item from the top of the stack.
​
Stacks are commonly used in undo features, function calls and expression evaluation, where tracking the most recent item first is important.
Queues
A queue stores items in a first in, first out (FIFO) order, meaning the first item added is the first one removed.
​​​
New items are added at the rear of the queue using an enqueue operation, and items are removed from the front using a dequeue operation.
​
Queues are often used in task scheduling, print spooling and data buffering, where operations must occur in the same order they were requested.
Linked Lists
A linked list is a dynamic data structure made up of a series of elements called nodes, where each node contains data and a pointer to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations, making it easy to insert or delete items without having to shift other elements.
​
The head is the first node in the list, and the last node usually points to null, indicating the end of the list.
Trees
A tree is a hierarchical data structure made up of nodes connected by branches, starting from a single root node. Each node can have child nodes, and nodes without children are called leaf nodes. Trees are useful for representing data with natural hierarchies, such as file systems or organisational charts.
​
A binary search tree is a special type of tree where each node has at most two children - a left and a right. All values in the left subtree are smaller than the parent node, and all values in the right subtree are larger. This structure allows for efficient searching, insertion and deletion of data, often much faster than in lists or arrays.
Graphs
A graph is made up of nodes (also called vertices) connected by edges and is used to represent relationships between items.
​
Graphs can be directed, where edges have a specific (one-way) direction, or undirected, where connections go both ways.
They can also be weighted, where edges have values such as distance or cost, or unweighted, where all connections are equal.
Graphs are widely used in computing, for example, in social networks (users and friendships), maps (locations and routes) and network routing algorithms.
Hash Tables
A hash table stores key–value pairs and allows for very fast data access. It uses a hash function to convert a key (such as a name or ID) into an index (hash value), which determines where the associated data (value) is stored in memory.
​
When retrieving data, the same hash function is applied to the key to find the value’s location instantly, making lookups close to constant time complexity on average.
If two keys produce the same hash (a collision), techniques such as chaining or linear probing are used to handle it. Hash tables are commonly used in databases, caches and programming languages for tasks like fast searching and indexing.
Questo's Key Terms
Arrays: array, 1-dimensional, 2-dimensional, 3-dimensional, static
​
Records: record, field, data type, primary key
​
Lists and Tuples: list, tuple, mutable, immutable, dynamic
Stacks and Queues: stack, queue, last in first out (LIFO), first in first out (FIFO), push, pop, enqueue, dequeue, pointer
Linked Lists: linked list, null
​
Trees & Graphs: tree, binary tree, binary search tree, root node, branch, graph, weights, directions
​
Hash Table: hash table, key, value, collision, linear probing, chaining
Did You Know?
Trees are used for dialogue options in narrative video games, displaying possible paths based on the player’s previous choices. The final 'suicide mission' of Mass Effect 2 has hundreds of possible variations depending on ship upgrades, squad member loyalty, and assigned roles during the last mission.
