4.2 Fundamentals of Data Structures AQA Comp Sci

A-Level

Data Structure

A way of organizing and storing data efficiently, chosen to optimise access and manipulation of data. Examples: arrays, lists, trees, tuples, records.

Abstract Data Type (ADT)

A conceptual model for data organization, not tied to a specific implementation. Focuses on what operations can be performed, not how.

Examples of ADTs

Queue, Stack, Graph, Tree, Hash Table, Dictionary, Vector

Static Data Structure

A structure with fixed memory size. Example: array.

Dynamic Data Structure

A structure that can grow or shrink in size during execution. Example: list.

Array

An indexed collection of elements of the same type. In Python, often referred to as a list.

1D Array

Represents a vector, indexed by a single integer.

2D Array

Represents a matrix, indexed by two integers.

nD Array

Set of elements indexed by a tuple of n integers.

Record

A collection of related fields representing one unit of data (e.g., a row in a table).

Field

A single piece of data within a record (e.g., a column in a table).

Text File

Stores data in human-readable characters. Common operations: reading, writing.

Binary File

Stores data in non-text formats such as images or videos.

Queue

Linear data structure using FIFO (First In, First Out). Elements added to rear, removed from front.

Circular Queue

Queue with a fixed-size ring buffer, rear connects to front.

Priority Queue

Queue where items have priority; higher priority items are dequeued first.

Enqueue

Add item to the rear of a queue.

Dequeue

Remove item from the front of a queue. Raises exception if queue is empty.

Front (Queue)

The front/first node of the queue.

Rear (Queue)

The rear/last node of the queue.

Peek (Queue)

Returns the value at the front without removing it. Raises exception if empty.

IsEmpty (Queue)

Returns True if the queue is empty, else False.

Stack

Data structure using LIFO (Last In, First Out). Like a stack of plates.

Push

Add item to the top of the stack.

Pop

Remove item from the top of the stack. Raises exception if empty.

Top (Stack)

The top node of the stack.

Peek (Stack)

View the top item without removing. Raises exception if empty.

IsEmpty (Stack)

Returns True if stack is empty, else False.

Stack Overflow

Error when trying to push onto a full stack.

Stack Underflow

Error when trying to pop from an empty stack.

Stack Frame

Part of the call stack storing function execution data.

Graph

A collection of vertices (nodes) and edges (connections).

Vertex

A node in a graph.

Edge

Connection between two vertices.

Undirected Graph

Edges are bidirectional.

Directed Graph

Edges have a direction (one-way connections).

Weighted Graph

Edges have weights/costs.

Connected Graph

A path exists between every pair of vertices.

Disconnected Graph

Not all vertices are connected.

Cyclic Graph

Contains cycles, i.e., paths that loop back to the start.

Acyclic Graph

No cycles present.

Adjacency Matrix

2D array showing edge connections between vertices.

Adjacency List

Dictionary mapping nodes to a list of connected nodes.

Matrix Pros

Fast lookups, easy to implement.

Matrix Cons

Uses more space (O(n^2)).

List Pros

Efficient for sparse graphs, uses less space.

List Cons

Slower lookups than matrices.

Tree

A connected, undirected, acyclic graph.

Root

Starting node of a tree.

Leaf

Node with no children.

Parent-Child

Relationship where one node connects to its descendants.

Binary Tree

Each node has at most two children.

Binary Search Tree (BST)

Left subtree has smaller values; right subtree has larger.

Tree Applications

Binary search trees, decision trees, heaps.

Hash Table

Data structure using a hash function to assign data to a unique address.

Hash Function

Converts input (key) into an index or address.

Collision

Two keys hash to the same index.

Chaining

Handling collisions using linked lists at each address.

Open Addressing

Resolve collisions by finding another open slot (e.g. add 1).

Double Hashing

Use a second hash function on collision.

Good Hash Function Properties

Shortening, deterministic, diffusing, one-way, collision resistant.

Simple Hash Example

Address = key mod number_of_slots.

Dictionary

A data structure of key-value pairs. Implemented using {} in Python.

dict["key"]

Retrieves the value associated with 'key'.

Vector

A quantity with both direction and magnitude. Represented as [x, y, z].

Scalar

A quantity with magnitude only.

Vector Addition

Add corresponding components: [a1, a2] + [b1, b2] = [a1+b1, a2+b2].

Vector Subtraction

Subtract corresponding components: [a1, a2] - [b1, b2] = [a1-b1, a2-b2].

Scalar Multiplication

Multiply each component by a scalar: 3*[a, b] = [3a, 3b].

Vector Notation

Arrow from origin or ℝ^n vector notation.

Vector Representation (Array)

Fixed-size list: [1.1, 2.3].

Vector Representation (Dictionary)

Index-keyed dictionary: {0: 1.1, 1: 2.3}.

Vector as Function

Function f: S → ℝ mapping index to real value.

Vector Applications

Used in graphics, simulations, multi-dimensional data.

Convex Combination

w = αu + βv where α+β=1 and α, β ≥ 0. Lies within span of u and v.

Dot Product

Sum of products of components. a·b = Σ(ai * bi).

Dot Product Uses

Find angle: cos(θ) = (a·b)/(|a||b|).