Appearance
D1 · Data Structures and Matrices
Spec reference: Sections D1 and D2 - How Data is Organised Key idea: Understand stacks, queues, arrays, lists, and how matrices are represented in computer systems.
Data structures
A data structure is a way of organising and storing data so it can be accessed and modified efficiently.
Stack
A stack is a Last In, First Out (LIFO) data structure.
- Push: Add an item to the top of the stack.
- Pop: Remove an item from the top of the stack.
- Peek: View the top item without removing it.
Real-world uses:
- Undo functionality in applications.
- The call stack in programming (tracking function calls).
- Browser back button history.
Push 3 → [3]
Push 7 → [3, 7]
Push 2 → [3, 7, 2]
Pop → returns 2, stack is [3, 7]Queue
A queue is a First In, First Out (FIFO) data structure.
- Enqueue: Add an item to the back of the queue.
- Dequeue: Remove an item from the front of the queue.
Real-world uses:
- Print queues (first document sent is first to print).
- CPU process scheduling.
- Network packet buffers.
Enqueue A → [A]
Enqueue B → [A, B]
Enqueue C → [A, B, C]
Dequeue → returns A, queue is [B, C]Array
An array is an ordered collection of elements of the same data type, stored in contiguous memory locations and accessed by an index.
1D array (list):
scores = [85, 72, 91, 64, 78]
scores[0] = 85
scores[4] = 782D array (table/matrix):
grid = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
grid[1][2] = 6Key features:
- Fast access by index: O(1).
- Fixed size in many languages.
- Efficient for storing ordered data.
List
A list is similar to an array but is more flexible. In many languages (e.g. Python), lists can:
- Hold elements of different data types.
- Grow and shrink dynamically.
- Be nested (lists within lists).
Matrices and arrays
A matrix is a rectangular grid of values arranged in rows and columns. In computer systems, matrices are represented as two-dimensional arrays.
Mathematical operations on matrices
Addition: Add corresponding elements. Matrices must be the same size.
Multiplication: Each element in the result is the dot product of a row from the first matrix and a column from the second.
Number of columns in first matrix must equal number of rows in second.
Multi-dimensional arrays
A multi-dimensional array extends the concept beyond 2D.
- 1D: A simple list (one index).
- 2D: A table (row, column).
- 3D: A cube (layer, row, column). Used in image processing (width, height, colour channel).
Row-major and column-major order
When a 2D array is stored in memory (which is 1D), the elements must be laid out in a sequence.
Row-major order
Elements are stored row by row. The last index changes fastest. Used by C, Python (NumPy default).
Matrix: Memory layout (row-major):
[1, 2, 3] 1, 2, 3, 4, 5, 6, 7, 8, 9
[4, 5, 6]
[7, 8, 9]Column-major order
Elements are stored column by column. The first index changes fastest. Used by Fortran, MATLAB.
Matrix: Memory layout (column-major):
[1, 2, 3] 1, 4, 7, 2, 5, 8, 3, 6, 9
[4, 5, 6]
[7, 8, 9]Exam point
The choice between row-major and column-major matters for performance. If you access data in the same order it is stored in memory, you get better cache performance. Accessing in the wrong order causes frequent cache misses.
Summary
| Term | Meaning |
|---|---|
| Stack (LIFO) | Last item added is the first to be removed |
| Queue (FIFO) | First item added is the first to be removed |
| Array | Fixed-size ordered collection accessed by index |
| 2D array | Table of values with row and column indices |
| Row-major | Storing array elements row by row in memory |
| Column-major | Storing array elements column by column in memory |