TheIBAxolotl
Static arrays and dynamic lists
- A static array has a fixed size set when it is created and holds items of one type in consecutive memory. Access by index is instant, but it cannot grow. In Java:
int[] scores = new int[30]; - A dynamic list grows and shrinks as items are added or removed: Python
list, JavaArrayList. It is more flexible but uses extra memory, and inserting near the front means shifting every later item.
import java.util.ArrayList;
ArrayList<String> names = new ArrayList<>();
names.add("Ana");
names.add("Kofi");
names.remove(0); // names is now [Kofi]
int n = names.size(); // 1Indexes start at 0, so the last item of a list of length n is at n - 1.
One-dimensional processing
The standard patterns are total, count, maximum/minimum and search:
temps = [18, 23, 21, 27, 19]
highest = temps[0] # start from a real item, not 0
for t in temps:
if t > highest:
highest = t
print(highest) # 27Starting the maximum at temps[0] (rather than 0) keeps the code correct when every value is negative.
Two-dimensional structures
A 2D structure is a list of rows; grid[r][c] is row r, column c.
marks = [[7, 5, 6],
[4, 6, 3],
[6, 7, 5]]marks[1][2] is 3 (row 1, column 2). To process every cell, nest two loops: outer over rows, inner over columns.
# total of each column
cols = len(marks[0])
for c in range(cols):
total = 0
for r in range(len(marks)):
total = total + marks[r][c]
print(c, total)Output: 0 17, 1 18, 2 14. The main diagonal is marks[i][i] (7, 6, 5); the other diagonal is marks[i][n-1-i] (6, 6, 6).
Java uses the same idea: int[][] seats = new int[12][30];, then seats.length is the number of rows and seats[0].length the number of columns.
Choosing a structure
| Situation | Best fit | Why |
|---|---|---|
| Size known and fixed (chessboard, 7 days) | Static array | Fast, memory-efficient, size never changes |
| Size unknown or changing (online queue, chat log) | Dynamic list | Can grow and shrink |
| Grid or table data (seating, pixels, timetable) | 2D array | Natural row/column indexing |
| Undo history, matching brackets | Stack (HL) | Last in, first out |
| Print jobs, customer service line | Queue (HL) | First in, first out |
Stacks (HL)
A stack is LIFO: the last item pushed is the first popped. Operations: push, pop, peek (look at the top), isEmpty.
Trace: push 3, push 8, pop, push 1, pop, pop.
| Operation | Stack (bottom -> top) | Returned |
|---|---|---|
| push 3 | 3 | |
| push 8 | 3, 8 | |
| pop | 3 | 8 |
| push 1 | 3, 1 | |
| pop | 3 | 1 |
| pop | empty | 3 |
Uses: undo, browser back button, the call stack for functions, checking balanced brackets (push every opening bracket, pop on each closing one and check they match; the expression is balanced only if the stack is empty at the end). Popping an empty stack is underflow; pushing onto a full fixed-size stack is overflow.
Queues (HL)
A queue is FIFO: items join at the rear (enqueue) and leave from the front (dequeue).
from collections import deque
q = deque()
q.append("job1") # enqueue
q.append("job2")
first = q.popleft() # dequeue -> "job1"A circular queue in a fixed array wraps the front and rear pointers back to index 0, so freed space is reused: rear = (rear + 1) % size.
Common mistakes
- Off-by-one:
range(1, len(a))skips index 0;a[len(a)]is out of range. - Swapping row and column in
grid[r][c]. - Initialising a maximum to 0.
- Reversing LIFO and FIFO.
Exam tips
- When justifying a structure, link it to a property of the scenario (fixed size, changing size, order of service).
- In 2D questions, write the row and column index of each item you use in your working.
- For stack and queue traces, draw the structure after every operation.