IB COMPUTER SCIENCE | B2.2.1 Static and Dynamic Structures

Lesson objective

Compare static and dynamic data structures, explaining memory allocation and resizing and evaluating speed, memory usage and flexibility for different scenarios.

Learn

B2.2.1 | STATIC AND DYNAMIC STRUCTURES

01 | HOW MUCH ROOM SHOULD A COLLECTION HAVE?

A program stores scores, bookings or sensor readings. Sometimes the number of entries is known: a sensor records exactly one value for each of 24 hours. Sometimes it is uncertain: users keep joining an online activity.

A data structure organises data and supports operations on it. Here we compare structures whose allocated extent is fixed once created with structures designed to grow or shrink as entries change.

This common SL/HL lesson connects size, capacity, memory allocation and resizing to speed, memory usage and flexibility. The right choice depends on the operations and constraints, rather than one category always being better.

02 | SIZE IS NOT CAPACITY

Size is the number of logical entries currently stored. Capacity is the number of entries a structure can accommodate in its currently allocated storage. They can differ.

A four-slot buffer containing 10, 20 and 30 has three logical entries and capacity four. The fourth slot exists but is not currently part of the logical collection.

index 0 10
index 1 20
index 2 30
index 3 spare

A slot may hold a value or a reference, depending on the language and representation. The boxes are an abstract storage model, not measured byte addresses or a picture of complete objects in memory.

03 | STATIC: FIXED EXTENT ONCE CREATED

In this topic, a static data structure has a fixed allocated extent once created, such as a fixed-length array. Its elements can normally be updated; fixed size does not mean that its values are immutable.

If an array has four slots, replacing the value at index 1 does not resize it. A program may also maintain a separate count of how many slots currently contain valid entries.

Do not confuse this meaning with Java’s static keyword, or assume every fixed-length array must be allocated at compile time. A Java array can be created during execution with a length calculated then; that array’s length subsequently remains fixed.

04 | DYNAMIC: CHANGE THE COLLECTION’S EXTENT

A dynamic data structure supports changing its logical number of entries during execution. It may acquire additional storage or release/unlink storage as needed.

Examples include resizable arrays such as Python lists and Java ArrayLists, and linked structures made from separately allocated nodes. Their implementation mechanisms are different.

Dynamic does not mean unlimited: growth is constrained by available memory, implementation limits and application rules. It also does not promise that every deletion immediately returns memory to the operating system.

05 | MUTABILITY AND RESIZABILITY ARE DIFFERENT

Change Fixed-length array Resizable array
Replace an existing element Normally allowed Allowed
Add a logical entry in an existing spare slot Possible if the program maintains a count and capacity remains Possible without growing backing capacity
Increase allocated extent of the same fixed array Not allowed; create a different larger array if needed Managed through the structure’s resizing operations
Store an arbitrary number of entries Not possible Not possible: resources are finite

A structure can be mutable but fixed in extent. Conversely, Python strings are immutable even though a variable can be rebound to a different-length string. Classify the structure’s behaviour, not simply whether its variable name can be assigned again.

06 | FIXED STORAGE: A SIMPLE ADDRESSABLE BLOCK

An ordinary array uses an indexed sequence of slots. For a uniform slot width, an element’s position can be derived from a base position and its index. This supports efficient direct access without walking through preceding elements.

A fixed extent can make storage requirements and bounds straightforward to plan. Reserving a known maximum can avoid a capacity-growth copy during ordinary insertion into a spare slot.

The trade-off is a limit chosen in advance of later insertions: reserve too much and space is unused; reserve too little and another entry cannot be accommodated without an explicit redesign or new allocation.

07 | JAVA EXAMPLE: A FIXED-LENGTH ARRAY

public class FixedExample {
    public static void main(String[] args) {
        int length = 4;
        int[] scores = new int[length];
        scores[0] = 10;
        scores[1] = 20;
        scores[1] = 25;
        System.out.println(scores.length); // 4
        System.out.println(scores[1]);     // 25
    }
}

The length is selected when new int[length] executes. Java initialises these int elements to zero, but zero is not automatically an “unused” marker: zero could be a valid score. Maintain a separate count or a suitable occupancy policy if not all slots represent logical entries.

Java does not provide append on an array to increase its length. You can allocate a new larger array and copy entries, but the original array has not changed its own length.

08 | A FIXED-CAPACITY POLICY IN PYTHON

capacity = 4
slots = [None] * capacity
size = 0

for score in [10, 20, 30, 40, 50]:
    if size < capacity:
        slots[size] = score
        size = size + 1
    else:
        print("Buffer full:", score)

print(slots)
print("Stored entries:", size)

The output rejects 50, keeps [10, 20, 30, 40] and reports four stored entries. None marks spare slots in this small example, while size identifies the occupied prefix.

The underlying Python list remains a dynamic structure. This code imposes a fixed-capacity application policy by using indexed replacement and rejecting overflow; it does not turn Python list into a different low-level fixed array type.

This distinction lets you model fixed-capacity behaviour in Python without making an inaccurate claim about its built-in list implementation.

09 | RESIZABLE ARRAYS: SIZE CAN CHANGE

scores = [10, 20]
scores.append(30)
scores[1] = 25
print(scores)       # [10, 25, 30]
print(len(scores))  # 3
scores.pop()
print(scores)       # [10, 25]

Python list supports adding and removing entries. len gives its current logical size, not the amount of spare internal backing storage. The list can retain capacity beyond that size.

In CPython, lists use a contiguous array of object references and reserve extra space during growth. The referenced objects need not be adjacent. Do not infer that a Python list is a chain of linked nodes from the word list.

10 | JAVA EXAMPLE: ARRAYLIST

import java.util.ArrayList;

public class DynamicExample {
    public static void main(String[] args) {
        ArrayList<Integer> scores = new ArrayList<>(2);
        scores.add(10);
        scores.add(20);
        scores.add(30);
        scores.set(1, 25);
        System.out.println(scores.size()); // 3
        System.out.println(scores.get(1)); // 25
    }
}

The constructor’s 2 supplies an initial capacity, not a permanent two-element limit. size is three after the additions. ArrayList manages a resizable backing array; its growth policy is not a syllabus requirement to memorise.

Integer is a reference type used by the generic collection. Representation overhead differs from a primitive int array, so compare actual language representations rather than assuming equal bytes per score.

11 | WHAT HAPPENS WHEN THE BACKING ARRAY IS FULL?

A resizable array may reserve extra slots so several additions can use existing capacity. When a larger block is required, a simplified model is: allocate a bigger backing block, copy existing entries, place the new entry and switch to the new block.

For a reference-based array, copying entries means copying references, not necessarily duplicating all the underlying objects. The previous block becomes eligible for reclamation according to the memory manager once it is no longer needed.

The exact allocator may sometimes extend or reuse a block. The allocate-and-copy model explains potential cost without claiming that every implementation performs a physically separate move on every append.

Stage Size Capacity Illustrative work
Before growth 2 2 Two entries, no spare slot.
Acquire larger block 2 4 Reserve a four-slot backing block.
Copy and append 3 4 Copy two entries, then write the new one.
Later append 4 4 Write into the remaining spare slot.

12 | VISUALISE GROWTH

This illustration uses a teaching policy that doubles capacity from two to four. It is not a promise about the exact growth factor of Python list or Java ArrayList.

index 0 10
index 1 20

After adding 30 with a growth step:

index 0 10
index 1 20
index 2 30
index 3 spare

One spare slot remains. Growing by more than one slot reduces how often the structure must request another block, at the cost of unused capacity.

If a separate larger block is needed, old and new blocks can coexist temporarily during copying. Peak memory during a resize can therefore exceed the final backing capacity.

13 | SPEED: NAME THE OPERATION

Direct indexed access in an array can be efficient whether its capacity is fixed or resizable. Dynamic does not automatically mean slow.

Appending to a resizable array with spare capacity is usually a small operation. A growth-triggering append may need to copy many existing entries, so it can take longer than nearby appends. Across many appends, suitable growth policies provide low average cost; this is often called amortised constant-time append.

Inserting into the middle of an ordered array can require shifting later entries in either fixed or resizable storage. Do not confuse insertion shifts with capacity growth, or assume an unused slot removes all insertion work.

14 | MEMORY: SPARE SPACE AND OTHER OVERHEAD

Representation Potential unused storage / overhead Consequence
Fixed-length array Slots reserved for a chosen maximum may remain unused. Predictable bound, but a poor estimate can waste space or reject entries.
Resizable array Spare capacity, structure metadata and possible temporary growth storage. Flexible size with some extra storage and occasional growth work.
Linked nodes Links and node allocation overhead. No single pre-reserved backing array, but links and allocations still cost memory.

Memory usage depends on the actual values or references, slot width, headers, alignment, allocator and language. “Dynamic uses exactly the memory of its data” is not a sound general claim.

Logical removal does not necessarily shrink backing capacity. Reclamation and returning memory to the operating system are also different events.

15 | LINKED STRUCTURES GROW DIFFERENTLY

A linked structure stores entries in nodes connected by references. Nodes do not need one contiguous backing array. Adding a node can allocate it separately and update links rather than copying every existing entry.

10

link to next

20

link to next

30

no next node

The trade-off includes link storage, allocation work and traversal. Finding the item at position k normally involves following links rather than calculating an indexed slot directly.

An insertion can be efficient once the necessary node position is already known; finding that position may still be expensive. Not every dynamic structure uses the same allocation or resizing mechanism.

16 | INTERACTIVE: FIXED LIMIT OR GROWING CAPACITY?

Compare two array-style teaching models: fixed capacity four, and a resizable model initially capacity two. Add the next value to both. A full fixed model rejects the addition; the dynamic model doubles its capacity when full, copying its existing entries first.

The counters count abstract slot writes and copied entries, not bytes or measured time. This toy growth policy is not the exact implementation of a language collection. You can try ten additions, remove the last stored entry from each, or reset.

FIXED-CAPACITY MODEL

RESIZABLE-ARRAY MODEL

Removing the last entry reduces logical size but retains capacity in both models. After the fixed model rejects an addition, the two collections can contain different numbers and values. This illustrates independent policies, not two views of one shared collection.

17 | PREDICT THE FIRST FIVE ADDITIONS

Added value Fixed: size / capacity Dynamic: size / capacity Dynamic entries copied by this append
10 1 / 4 1 / 2 0
20 2 / 4 2 / 2 0
30 3 / 4 3 / 4 2
40 4 / 4 4 / 4 0
50 4 / 4; rejected 5 / 8 4

The dynamic model has copied six existing entries in total after five additions and written five new entries. This illustrates why one addition may be more costly than another.

In the allocate-new-block model, growing from four slots to eight can temporarily require both blocks: twelve slots, excluding all metadata and element objects. Final capacity is eight, not twelve.

18 | REMOVAL DOES NOT GUARANTEE SHRINKING

Removing the final entry often changes size without moving the other entries. The implementation may keep its backing capacity for future use, or apply a separate shrink policy when appropriate.

Shrinking aggressively after every removal could cause repeated copying if additions follow immediately. Retaining too much capacity can also be undesirable. The policy balances future workload and memory use.

For a linked structure, unlinking a node makes it unavailable through that chain, but actual reclamation depends on remaining references and memory management. Logical deletion is not a guarantee of immediate physical memory return.

19 | WHEN A FIXED EXTENT FITS THE TASK

A daily device buffer that must hold exactly 24 readings has a known bound. Fixed storage can be straightforward, with predictable indexing and no growth-copy event while filling the reserved slots.

A board with a fixed number of positions or a small embedded application with a verified memory budget can have similar needs. State what happens when the capacity is reached rather than writing past the bound.

A fixed extent alone does not guarantee a real-time deadline: the rest of the algorithm, runtime and hardware also matter. Use it as one reason in a contextual choice, not a universal performance guarantee.

20 | WHEN A DYNAMIC STRUCTURE FITS THE TASK

A changing workshop waiting list or a document’s collection of search results may have an unpredictable count. A resizable collection avoids one permanently fixed maximum chosen by the application, while still needing resource limits.

Choose the implementation from the operations: a resizable array suits indexed access and frequent appends; a linked approach can suit known-position link changes but brings traversal and link overhead.

If a sensible upper estimate is known, reserving capacity in advance may reduce later growth work. This does not make the collection’s size fixed or remove all allocation overhead.

21 | A BALANCED COMPARISON

Factor Fixed-length array Resizable array / linked alternatives
Common purpose Organises and stores entries for later operations. Also organises and stores entries; operations and rules still matter.
Extent Fixed once that array is created. Logical size can grow/shrink; backing strategy depends on representation.
Indexed access Direct indexed slot access. Resizable array also supports direct indexing; linked traversal differs.
Growth Full capacity needs rejection or explicit replacement allocation. May allocate/copy backing storage or add nodes.
Memory Known reserved extent, possibly unused slots. Spare capacity or node/link overhead; peak allocation can matter.
Flexibility Useful when count/bound is stable and known. Useful when count changes, with resource limits and policy costs.

For the IB command term compare, identify similarities and refer to both items throughout. This lesson also makes the differences explicit because the syllabus requires their fundamental differences and trade-offs. If asked to compare and contrast, cover both similarities and differences.

22 | APPLY THE TRADE-OFFS TO A SCENARIO

A school records one temperature per hour and separately keeps a changing list of visitors. For the 24-hour readings, a fixed-length array maps each hour to one slot and avoids growth. For visitors, a dynamic collection can accommodate changing numbers without rejecting everyone beyond a small initial estimate.

Neither decision is complete without limits and operations. Missing hourly readings need an occupancy or missing-data policy; a visitor collection still needs sensible memory and retention limits.

Justify speed through the relevant action: indexed retrieval, appending, searching, middle insertion or removal. “Static is faster” without naming the workload is not a meaningful comparison.

23 | WORKED MEMORY CALCULATION

Assume an abstract array stores one four-byte entry in each slot and ignore headers, references and alignment. A fixed array with capacity 100 occupies 400 bytes of slot storage even if only 30 slots are logically occupied. The occupied entries account for 120 bytes and unused slots for 280 bytes.

A resizable backing array with capacity 40 uses 160 bytes under the same simplified assumptions. It may later need growth, and this comparison does not establish the actual footprint of Python objects or Java boxed integers.

If that 40-slot block grows to a separate 80-slot block, copying could temporarily involve 120 slots, or 480 bytes, before the old block is reclaimed. State the assumptions and distinguish peak from final storage.

24 | COMMON MISTAKES

Mistake Correction
Static means values can never change. Fixed extent differs from element mutability.
Static arrays must be allocated at compile time. A fixed-length array can be created with a runtime-selected length.
Python list is a linked list. CPython list uses a resizable array of references.
Every append copies all existing entries. A resizable array can use spare capacity; copying may occur on growth.
Dynamic storage is unlimited or has no overhead. Memory and implementation limits remain; spare slots or links cost storage.
Deleting an item instantly returns its bytes to the OS. Logical size, backing capacity and reclamation differ.
A prefilled Python list is inherently static. A fixed-capacity policy can use a still-dynamic list.
Any dynamic structure has slow indexed access. Resizable arrays and linked structures have different access mechanisms.

25 | CHECK THE IMPLEMENTATION CLAIMS

Distinguish a conceptual model from a language guarantee. Our doubling example makes growth visible; Java ArrayList does not specify its exact growth policy in its API contract. CPython’s list implementation also should not be reduced to one fixed multiplier you assume forever.

For language-specific details, consult the official documentation. Focus your explanation on logical size, backing storage, possible resizing work and the operations required by the scenario.

Java ArrayList documentation | Python documentation: CPython list implementation

26 | YOUR COMPARISON CHECKLIST

Can you separate size from capacity and fixed extent from immutability? Can you explain growth through backing-array allocation/copying and through linked-node allocation? Can you connect speed, memory and flexibility to actual operations?

Practise a comparison that includes a shared purpose, explicit mechanism differences and a contextual judgement. The next lesson constructs programs using arrays and lists.

MATCH THE STORAGE IDEA TO ITS ROLE

Terminology

Terminology

Data structure

An organisation of data supporting particular operations.

Static data structure

In this topic, a structure with a fixed allocated extent once created.

Dynamic data structure

A structure designed to change its logical number of entries during execution.

Logical size

The number of entries currently considered stored.

Capacity

The number of entries accommodated by currently allocated backing storage.

Allocation

Obtaining memory for a structure or part of it.

Resizing

Changing backing storage extent to accommodate a collection’s needs.

Fixed-length array

An indexed array whose own length is fixed after creation.

Resizable array

A collection using array-style backing storage that can be grown or otherwise resized.

Backing array

The internal array of slots supporting a resizable collection.

Spare capacity

Allocated slots beyond the current logical entries.

Contiguous storage

A sequence of adjacent storage slots within an allocated block.

Reference

A value referring to another object or node.

Node

An allocated entry containing data and one or more links in a linked structure.

Link

A reference connecting nodes.

Traversal

Visiting entries in sequence, such as following links.

Indexed access

Accessing an entry by its position.

Append

Adding an entry at the logical end.

Insertion shift

Moving later array entries to preserve order when inserting into the middle.

Amortised cost

Average cost per operation over a sequence, including occasional expensive operations.

Growth policy

The rule determining how much additional backing storage to acquire.

Memory overhead

Storage beyond the represented payload, such as metadata, spare capacity or links.

Peak memory

The maximum simultaneous memory involved during an operation.

Reclamation

Making no-longer-needed allocated storage available for reuse under the memory manager.

Immutability

An object’s contents cannot be changed in place; distinct from fixed extent.

Overflow policy

The defined response when a bounded collection has no available slot.

Application limit

A bound imposed by program requirements or policy.

ArrayList

Java’s resizable-array implementation of its List interface.

Python list

A dynamic sequence; CPython implements it using a resizable array of object references.

Preallocation

Reserving storage capacity in advance of later insertions.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which distinguish size and capacity?
2. Which describe fixed-length arrays?
3. Which are accurate allocation claims?
4. Which describe resizable arrays?
5. Which describe Python list?
6. Which describe linked structures?
7. Which describe memory trade-offs?
8. Which explain speed meaningfully?
9. Which describe deletion?
10. Which support a contextual choice?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Compare the purpose and organisation of static and dynamic data structures.

2. Distinguish logical size from capacity with an example.

3. Explain why a fixed-length array is not necessarily immutable.

4. Describe a resizable array growth operation.

5. Explain the first five appends in the doubling model.

6. Compare indexed access in fixed arrays, resizable arrays and linked structures.

7. Explain one memory disadvantage of each main representation.

8. Justify a fixed array for exactly24 hourly readings, including a limitation.

9. Justify a dynamic collection for changing search results, including a limitation.

10. Calculate slot storage for capacity100, size30 and four bytes per entry under the simplified model.

11. Explain why removing an entry need not reduce allocated capacity.

12. Explain why a Python fixed-capacity buffer example does not prove Python list is static.

COMPARE IT | TWO DIFFERENT WORKLOADS

A device records exactly 60 readings each minute. A separate application collects an unpredictable number of messages. Compare a fixed-length array with a resizable array for these workloads. Include a shared capability, memory trade-offs, indexed access and growth behaviour. Explain what happens if the chosen limit or available memory is exceeded.

Reveal an answer outline

Both organise indexed entries. A fixed array can reserve 60 reading slots and avoid capacity-growth copying while filling them, but must handle missing readings and changed bounds. A resizable array supports an uncertain message count and direct indexed access, but spare capacity and growth work affect memory and latency. Neither is unlimited; define an honest overflow or resource-failure policy.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B2.2.1 Static and Dynamic Structures is coming soon. Complete the matching task and written questions in your exercise book.