B2.2.1 · Data structures
Static versus dynamic structures
By the end you can
Contrast memory allocation, fixed bounds, and resizing costs of static arrays versus dynamic heap structures.
Data structures organise and store data so that algorithms can process information efficiently. The most fundamental division in data structure design is between and .
Static data structures#
A static structure has a fixed size and fixed memory footprint determined at compile time or upon initial declaration. The classic example is a traditional array (e.g. int scores[50]):
- Predictable memory footprint: The operating system allocates a single contiguous block of RAM. Memory management is straightforward with no pointer fragmentation.
- Direct random access: Accessing any element by its index takes constant time ($O(1)$) because the address of element $i$ is calculated instantaneously: Address = Base + i * ElementSize.
- Wasted space vs overflow: If you declare an array of 1,000 items and store only 10, the remaining 990 slots waste memory. Conversely, if 1,001 items arrive, the array suffers an overflow error and cannot accept new entries.
Dynamic data structures#
A dynamic structure expands and contracts flexibly at runtime to match the exact volume of data being stored. Examples include linked lists, binary search trees, and dynamic arrays (like Python list or Java ArrayList):
- Flexible capacity: Nodes are allocated on the heap one at a time as new items arrive, meaning memory is only consumed when actually needed.
- No arbitrary upper limit: The structure can continue growing until total system RAM is exhausted.
- Pointer overhead and fragmentation: Each data item must store one or more pointers/references to other nodes, increasing memory consumption per element. Accessing element $k$ in a linked structure requires traversing node-by-node ($O(n)$ access).
Check yourself
Static and dynamic structures
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 8 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Compare static data structures and dynamic data structures in terms of size, memory allocation, and risk of overflow.
[4]Compare: Similarities and differences, about both things, point by point.
2.State two advantages of using a static array over a dynamic data structure such as a linked list.
[2]State: Give a short answer, no explanation needed.
3.Explain one drawback or performance overhead associated with dynamic data structures.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
In a nutshell
- Static data structures have a fixed size determined at compile time or initial declaration that cannot grow or shrink.
- Static arrays occupy contiguous memory offering O(1) random index access but risking wasted memory or overflow.
- Dynamic data structures allocate memory nodes on the heap at runtime, growing and shrinking flexibly.
- Dynamic structures avoid arbitrary capacity limits but incur pointer memory overhead and O(n) sequential traversal.