You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson introduces the fundamental distinction between static and dynamic data structures — one of the most important conceptual foundations in A-Level Computer Science. The way a structure allocates and manages memory determines how fast it runs, how much memory it consumes, and whether it can adapt to data whose size is not known in advance. Mastering this distinction lets you justify design decisions in the written paper rather than merely describing structures.
This lesson addresses AQA A-Level Computer Science (7517), section 4.2.1 (Data structures). It covers the difference between static and dynamic structures, how memory is allocated for each (compile-time allocation versus runtime allocation on the heap), and the comparative advantages and limitations you are expected to evaluate. It also introduces the idea of an abstract data type (ADT), which underpins the stack (§4.2.4), queue (§4.2.3), and list/linked-list (§4.2.6) topics later in this unit. The spec area is described in original wording below; AQA's published specification text is not reproduced.
A data structure is a way of organising, storing, and managing data so that it can be accessed and modified efficiently. Choosing the correct data structure affects both the performance (how quickly operations run) and the correctness (whether the program behaves as intended) of a solution. Every non-trivial program makes data-structure choices, even implicitly: a Python list, a dictionary, and a string are all data structures with different performance characteristics.
Data structures are classified as either static or dynamic, depending on when and how their memory is allocated. This single distinction drives almost every trade-off you will be asked to evaluate.
A static data structure has a fixed size that is fixed at compile time — before the program runs. Once the structure has been created, the amount of memory it occupies cannot change during execution.
| Feature | Description |
|---|---|
| Size | Fixed — must be declared when the structure is created. |
| Memory allocation | Reserved at compile time; the exact byte count is known before execution. |
| Memory usage | May waste memory if not fully used; cannot grow if more space is needed. |
| Access | Typically allows direct (random) access to any element using an index in constant time. |
| Examples | Arrays (in most languages), fixed-size strings, records/structs. |
The pseudocode declaration DECLARE scores : ARRAY[0..9] OF INTEGER reserves a fixed block of ten integer slots. The compiler can compute the exact memory requirement immediately: ten integers at four bytes each gives a contiguous 40-byte block.
# Python's built-in list is dynamic, so a fixed-size array is simulated
# with the array module to demonstrate the static concept.
import array
scores = array.array('i', [0] * 10) # 10 four-byte signed integers
scores[3] = 42 # direct index access, O(1)
Because the elements occupy a single contiguous run of memory, the address of element i can be calculated by simple arithmetic — this is what makes index access constant-time.
If an array begins at base address B and each element occupies S bytes, the address of element i is computed directly:
address(i)=B+i×S
No traversal is needed; the processor jumps straight to the location. This is the defining advantage of contiguous static storage and is the reason an array supports random access while a linked list does not.
Suppose an array of 32-bit integers (S=4 bytes) begins at base address B=2000. The address of element 5 is:
address(5)=2000+5×4=2020
The processor performs one multiply and one add — a fixed amount of work — regardless of whether the array holds 10 elements or 10 million. Contrast this with finding the fifth node of a linked list, which requires following five pointers one after another. This is the concrete reason the two structures have such different access characteristics, and it is worth being able to reproduce this calculation in an exam.
A dynamic data structure can grow and shrink while the program is running. Memory for each new element is requested at runtime and released when no longer needed.
| Feature | Description |
|---|---|
| Size | Variable — can grow or shrink during execution. |
| Memory allocation | Requested at runtime from the heap as elements are added. |
| Memory usage | Uses only as much as is needed, but each element carries extra bytes for pointers/references. |
| Access | Usually requires sequential access (traversal) to reach a given element. |
| Examples | Linked lists, binary trees, graphs, linked-implementation stacks and queues. |
next pointer), consuming extra memory.| Feature | Static | Dynamic |
|---|---|---|
| Size | Fixed at creation | Can change during execution |
| Memory allocation | Compile time | Runtime (heap) |
| Memory efficiency | May waste reserved space | Uses only what is needed (plus pointers) |
| Access speed | O(1) random access | O(n) sequential access for linked structures |
| Overflow risk | Yes — cannot grow | No — grows until system memory is exhausted |
| Pointer overhead | None | Yes — each node stores one or more pointers |
| Cache performance | Good (contiguous) | Poorer (scattered nodes) |
| Example | Array | Linked list |
Exam Tip: A very common exam question asks you to compare static and dynamic data structures and evaluate the advantages and disadvantages of each. Always give specific examples (array for static, linked list for dynamic) and relate the trade-off back to the scenario in the question rather than reciting a generic list.
Programs use two main regions of memory during execution, and the static/dynamic distinction maps onto them.
| Memory area | Used for | Characteristics |
|---|---|---|
| Stack | Local variables, parameters, return addresses (stack frames) | Fast, LIFO, automatically managed, limited fixed size |
| Heap | Dynamically allocated data (objects, list nodes) | Larger, flexible, allocated/freed at runtime, garbage-collected or manually managed |
Static data structures such as a local array are typically placed on the call stack or in a fixed data segment. Dynamic structures request memory for each node from the heap. When a node is removed and nothing references it, the memory is reclaimed — automatically by a garbage collector in languages such as Python or Java, or manually (e.g. free/delete) in languages such as C.
The heap is a pool of free memory from which a running program can request blocks of arbitrary size on demand. When you create a new linked-list node, the program asks the memory manager for a block large enough to hold the node's data and its pointer; the manager finds free space, returns its address, and records the block as in use. Because requests and releases happen in any order, the heap can become fragmented — interspersed with small unusable gaps — which is one reason dynamic structures can be less memory-efficient than their contiguous static counterparts.
Modern languages offer a structure that blurs the static/dynamic boundary: the dynamic array (Python's list, Java's ArrayList, C++'s vector). It stores elements contiguously like a static array — preserving O(1) indexed access — yet grows automatically like a dynamic structure. The trick is over-allocation with periodic resizing.
A dynamic array keeps two numbers: its logical length (items in use) and its capacity (slots actually allocated). When an append would exceed the capacity, the structure:
Starting from capacity 2 and appending six items, the resize events are:
| Append # | Capacity before | Resize? | Capacity after | Copy cost |
|---|---|---|---|---|
| 1 | 2 | no | 2 | 0 |
| 2 | 2 | no | 2 | 0 |
| 3 | 2 | yes → 4 | 4 | copy 2 |
| 4 | 4 | no | 4 | 0 |
| 5 | 4 | yes → 8 | 8 | copy 4 |
| 6 | 8 | no | 8 | 0 |
Most appends cost O(1); only the occasional resize costs O(n). Because the capacity doubles, resizes become rarer as the array grows, and the average (amortised) cost of an append works out to O(1). This is why appending to a Python list feels instant even though an individual append might secretly copy the whole array. The dynamic array is the structure recommended in many "unknown size but need indexed access" scenarios, and recognising it as a third option between a plain array and a linked list is a mark of strong understanding.
It helps to be able to classify a given structure quickly. The table below sorts common examples and states the deciding reason — exactly the kind of justification a "state and justify" question demands.
| Structure | Static or dynamic? | Why |
|---|---|---|
Fixed-size array ARRAY[0..99] | Static | Size declared at compile time; cannot grow |
Fixed-length string (e.g. STRING[10]) | Static | A fixed array of characters; capacity set in advance |
| Record / struct | Static | Number and types of fields are fixed at design time |
| 2D array (grid/matrix) | Static | Both dimensions fixed at creation |
| Singly/doubly linked list | Dynamic | Nodes allocated on the heap at runtime |
| Binary tree, graph (node-based) | Dynamic | New nodes created on demand during execution |
| Linked-implementation stack / queue | Dynamic | Grows node-by-node, no fixed ceiling |
Dynamic array (Python list) | Hybrid | Contiguous like an array, yet auto-resizes like a dynamic structure |
Note that records are static: although their field values change freely, the shape of a record (its fields and their types) is fixed when the type is declared, so no memory is allocated or freed as the program runs. This is a common discrimination point in the exam — do not confuse "the data changes" with "the structure is dynamic".
In some languages a string is simply a fixed-length array of characters with a sentinel marking the end. Declaring STRING[10] reserves ten character slots regardless of how many are used, so storing "Hi" wastes eight slots — the same trade-off as any static structure. Languages with dynamic strings (Python, Java) instead allocate just enough space and re-allocate when the string grows, illustrating the static/dynamic distinction at the level of a single data type rather than a whole collection.
| Scenario | Recommended | Reason |
|---|---|---|
| The number of elements is known in advance | Static (array) | No overhead, predictable allocation, fast access |
| The number of elements is unknown or changes frequently | Dynamic (linked list) | Can grow and shrink as required at runtime |
| Fast random access to arbitrary elements is required | Static (array) | O(1) index access via address arithmetic |
| Frequent insertions/deletions in the middle are required | Dynamic (linked list) | Only pointers are re-linked; no element shifting |
An abstract data type (ADT) is a logical description of how data is viewed and the operations that may be performed on it, without specifying how those operations are implemented. A data structure is a concrete implementation that realises an ADT. The same ADT can be implemented by more than one data structure, with different performance.
| ADT | Possible implementations |
|---|---|
| Stack | Array-based stack, linked-list-based stack |
| Queue | Array-based (linear/circular) queue, linked-list queue |
| List | Array, linked list |
| Map / Dictionary | Hash table, binary search tree |
This separation of interface (what the operations do) from implementation (how they are coded) is the principle of abstraction — a recurring theme across the specification, from problem-solving to object-oriented programming.
Because an ADT hides its implementation, you can swap the underlying data structure without changing any code that uses the ADT. A program that uses a Stack ADT through its push/pop interface works identically whether the stack is backed by an array or a linked list; only the performance and capacity behaviour change. This is information hiding and encapsulation — the same principles you meet in object-oriented programming. In the exam, "Define an abstract data type" should be answered as: a description of a set of values together with the operations permitted on them, independent of any particular implementation. The follow-up "Give an example of two implementations of the same ADT" is then easy — for instance, an array-based versus a linked-list-based stack.
The contrast becomes concrete when the same logical task is coded both ways. Consider storing a growing collection of integers.
# STATIC-style: fixed capacity, overflow if exceeded
import array
fixed = array.array('i', [0] * 5) # capacity 5, allocated up front
count = 0
def add_fixed(value):
global count
if count == 5:
raise OverflowError("no room — cannot grow")
fixed[count] = value
count += 1
# DYNAMIC-style: linked nodes, grows until memory is exhausted
class Node:
def __init__(self, data):
self.data = data
self.next = None
head = None
def add_dynamic(value):
global head
node = Node(value) # heap allocation at runtime
node.next = head
head = node # no capacity limit
The static version refuses the sixth item; the dynamic version keeps allocating nodes on demand. Neither is universally "better": the static version is faster and simpler when five is genuinely the maximum, while the dynamic version is safer when the count is unknown. This is the trade-off the whole lesson turns on.
A weather-monitoring program records temperature readings. The developer is unsure whether to store the readings in a fixed-size array or a linked list. The number of readings per day is not known in advance, but once stored the program frequently retrieves the reading at a particular position to plot a graph.
(a) State one advantage and one disadvantage of using a static array for this task. (2 marks) (b) Explain why a dynamic data structure might be more appropriate for storing the readings. (3 marks) (c) Evaluate the two approaches and recommend, with justification, which the developer should choose. (4 marks)
AO breakdown:
A static array has a fixed size, so it is fast to access by index but it can run out of space if there are more readings than expected. A dynamic structure like a linked list can grow as more readings are added so you do not need to know the number in advance. I would use a linked list because the number of readings is not known.
(a) Advantage: an array gives O(1) random access, so any reading can be retrieved directly by index. Disadvantage: its size is fixed at compile time, so it may overflow if more readings arrive than expected, or waste memory if fewer do.
(b) A linked list is dynamic and allocates each node on the heap at runtime, so it grows and shrinks as readings are added or removed. This suits the scenario because the number of readings per day is not known in advance, avoiding both overflow and wasted reserved space.
(c) The linked list handles the unknown count well, but the program "frequently retrieves the reading at a particular position", and a linked list only offers O(n) sequential access. An array offers O(1) access but risks overflow. I would therefore use a dynamically resizing array (e.g. a Python list), which grows like a linked list yet preserves O(1) indexed access.
(a) Advantage — contiguous storage gives O(1) index access via address arithmetic (B+i×S); disadvantage — capacity is fixed at compile time, causing overflow or wasted memory when the true count is unknown.
(b) The readings count is unbounded and variable, so runtime (heap) allocation is preferable: a linked list adds a node only when needed, eliminating the over-allocation a fixed array would require and the risk of overflow. Each node carries a small pointer overhead, which is acceptable for this volume of data.
(c) The decision is a trade-off between flexible size and fast indexed retrieval. A plain linked list satisfies the first but degrades the graph-plotting step to O(n) per lookup, which is O(n2) across all positions. A fixed array satisfies the second but cannot handle the unknown count safely. The optimal choice is a dynamic array (resizable array list): amortised O(1) append gives growth, while contiguous storage retains O(1) indexed access — the best of both for this workload. If insertions were instead frequent in the middle of the data, a linked list would win, so the recommendation is workload-specific. I therefore recommend a dynamic array, justified by the dominant "retrieve by position" requirement.
Examiner-style commentary: The mid-band answer states correct facts but never connects them to the retrieve-by-position requirement, so it cannot access the evaluation marks. The stronger answer correctly identifies the access-pattern conflict and proposes the resizable array. The top-band answer adds quantified reasoning (the O(n2) cost of repeated linked-list lookups), recognises that the best choice depends on the workload, and reaches a justified, scenario-specific recommendation — exactly what AO3 "evaluate" demands.
A games console runs a program that loads a level. Some data — the maximum number of players (always 4) — is fixed, while other data — the list of projectiles currently in flight — changes constantly as the game runs.
(a) Define the terms compile-time allocation and runtime allocation. (2 marks) (b) For each of the two kinds of data above, state whether a static or a dynamic structure is more suitable and justify your answer. (4 marks) (c) Explain one disadvantage that the dynamic structure introduces compared with the static one. (2 marks)
AO breakdown:
(a) Compile-time allocation is done before the program runs; runtime allocation is done while it runs.
(b) The players should be static because there are always 4. The projectiles should be dynamic because the number changes.
(c) A dynamic structure is slower to access.
(a) Compile-time allocation reserves memory before execution, with the size fixed in advance. Runtime allocation requests memory from the heap while the program runs, so the amount can vary.
(b) The maximum players is a fixed value (4), so a static array of size 4 is ideal — no overhead and instant access. The projectiles in flight are created and destroyed constantly and their number is unknown, so a dynamic structure (e.g. a linked list) is suitable because it grows and shrinks as projectiles appear and disappear.
(c) The dynamic structure adds pointer overhead — each projectile node stores a reference as well as its data — and access is O(n) rather than O(1).
(a) Compile-time allocation reserves a fixed, known quantity of memory before the program executes, so its size cannot change at run time. Runtime allocation obtains memory dynamically from the heap during execution, allowing the amount used to grow or shrink in response to the program's behaviour.
(b) The "maximum players" datum is a small, fixed constant (4), so it should use a static array of size 4: the size is known at compile time, allocation is trivial, access is O(1), and there is no pointer overhead — a dynamic structure here would only add cost for no benefit. The "projectiles in flight" collection is highly volatile, with items created and removed many times per second and no sensible fixed upper bound; a dynamic structure (linked list, or a dynamic array if indexed access is needed) is appropriate because it allocates a node per projectile at runtime and releases it when the projectile is destroyed, avoiding both overflow and a large permanently reserved block.
(c) The dynamic choice trades performance and locality for flexibility. Each projectile node carries a pointer, increasing per-element memory, and the nodes are scattered across the heap, harming cache performance — so iterating over hundreds of projectiles every frame can be measurably slower than iterating a contiguous array, even though both are O(n). Frequent allocation and deallocation can also fragment the heap. In a tight per-frame game loop this overhead is significant, which is why some games pre-allocate a fixed pool of projectile slots to regain contiguous, allocation-free storage — a deliberate move back toward static allocation.
Examiner-style commentary: The mid-band answer is correct but undeveloped — part (b) gives no justification beyond restating the question, and part (c) names a disadvantage without explaining it. The stronger answer justifies both choices and identifies two concrete costs. The top-band answer defines the terms precisely, justifies each allocation model against the specific data characteristics, and in (c) explains why the cost matters in a per-frame game loop, even noting the real-world "object pool" mitigation — demonstrating the synoptic, evaluative depth examiners reward at the top band.
free heap memory causes a memory leak (memory consumed but never reclaimed), while free-ing too early creates a dangling pointer that references reclaimed memory — a major source of crashes and security vulnerabilities. Contrast this with Python's automatic reference counting and Java's garbage collector, which trade a little runtime overhead for safety. This connects directly to the systems-software and security content.This content is aligned with the AQA A-Level Computer Science (7517) specification.