B2.2 Data structures

A single value stored in an array or list, identified by its index.

Data structures and memory

Every value a running program uses lives in random-access memory (RAM), which is a long row of numbered storage locations called addresses. A single variable reserves enough locations for one value of its data type: four bytes for a Java int, for example. A data structure reserves space for many values and adds a rule for finding each one.

Reserving that space is called memory allocation. The operating system (OS) and the language's runtime hand out free regions of RAM to programs and take them back when they are no longer needed; subtopic A1.3, Operating systems and control systems, describes this as memory management. A data structure can receive all of its memory once, when it is created, or request more while the program runs, and this difference divides data structures into static and dynamic ones.

Static and dynamic data structures

Static data structures

A static data structure has a size that is fixed when it is created. In Java, the statement int[] rainfall = new int[7]; reserves exactly seven int slots, and the array can never hold an eighth. The program can change the contents of the seven slots as often as it likes; only the number of slots is fixed.

The slots of a static array sit next to each other in one contiguous block of memory, in index order. Because every element has the same size, the address of any element can be calculated in one step from the start of the block, without searching:

The memory diagram of rainfall shows seven 4-byte integers stored from address 1000. Element 3 is at $1000 + 3 \times 4 = 1012$, and element 6 would be at $1000 + 6 \times 4 = 1024$. The calculation takes the same time whether the array has 7 elements or 7 million, which is why reading or writing any element by its index takes constant time, O(1).

The same diagram explains the main limitation. Memory on either side of the block may already belong to other data, so the array cannot be stretched where it is. A program that needs more room must create a new, larger array and copy the elements across itself.

Dynamic data structures

A dynamic data structure grows and shrinks while the program runs. A Python list starts empty and accepts as many append calls as memory allows; a Java ArrayList does the same with add. The program does not need to know in advance how many items will arrive.

There are two ways to build a dynamic structure. A dynamic array (also called a resizable array) keeps its elements in one contiguous block, like a static array, but replaces the block with a larger one when it fills up. A linked structure stores each item in a separate piece of memory together with a reference to the next item, so it can grow one item at a time anywhere in memory; linked lists are HL content in subtopic B4.1. Java's ArrayList and Python's list are both dynamic arrays, which keeps their indexing as fast as a static array's.

How a dynamic array grows

A dynamic array allocates more slots than it currently needs. The number of slots in the block is its capacity; the number of items actually stored is its size. While the size is below the capacity, adding an item only writes it into the next spare slot.

When an item arrives and the array is full, the array performs a resize. It allocates a new block, copies every existing element into it, stores the new item and releases the old block. The resize diagram shows a full block of capacity 4 being replaced by one of capacity 6. The new capacity is the old capacity plus half of it, which is the rule Java's ArrayList uses.

The growth factor matters a great deal. If the array grew by one slot each time, every single addition would copy the whole array, and appending $n$ items would copy $0 + 1 + 2 + \dots + (n - 1) = \tfrac{n(n-1)}{2}$ elements in total. Growing by a fixed proportion makes resizes rare, because each one creates many spare slots. The program count_copies simulates both rules for an array that starts empty: one slot at a time, and Java's rule (start at 10, then add half the capacity).

Both versions print the same table:

For 10,000 items, growing one slot at a time copies almost 50 million elements, while growing by half copies 28,096: fewer than three copies per item on average. Most additions cost a single write and only an occasional one triggers a large copy, so the average cost of an addition stays constant even though a single addition can take $O(n)$ time. The cost is extra memory, because just after a resize up to a third of the new block is spare slots that hold nothing.

Comparing static and dynamic structures

Neither family is better in every situation. A static structure is the right choice when the number of items is known and fixed: seven days in a week, 64 squares on a chessboard, 12 monthly totals. A dynamic structure suits data whose amount is unknown or changes: items in a shopping basket, songs in a playlist, sensor readings logged until someone presses stop.

Both kinds store elements of a declared type, both are indexed from 0, and a dynamic array uses a static array internally. The difference lies in who handles growth: with a static array the programmer must notice that it is full and copy the data, while a dynamic structure does it automatically at a small, mostly hidden cost.

Case study: dynamic arrays inside Java and Python

Java's ArrayList and Python's list are both dynamic arrays: each object keeps its elements in an ordinary fixed-size array that it replaces when full. The public source code of both languages shows the exact growth rules. Java's ArrayList documents a default initial capacity of 10. When an element is added to a full list, its private grow method computes a preferred new capacity of oldCapacity + (oldCapacity >> 1): the shift right by one bit halves the old capacity, so the list grows by about 50%. The elements are copied into the new array with Arrays.copyOf, and the old array becomes garbage that the Java runtime reclaims.

CPython, the standard Python interpreter, describes its lists as "variable-length arrays, not Lisp-style linked lists": one contiguous array of references to objects. When a list must grow, list_resize allocates about one eighth more than the new size, plus a small constant: the formula is newsize + (newsize >> 3) + 6, rounded down to a multiple of 4. Because a Python list stores references rather than the values themselves, one list can hold an integer, a string and another list side by side, and its index arithmetic still works because every reference is the same size.

The two growth rules give quite different capacity sequences for a list that starts empty and keeps growing:

Sources: OpenJDK source file java/util/ArrayList.java (DEFAULT_CAPACITY and the grow method); CPython source file Objects/listobject.c and the Python Design and History FAQ, "How are lists implemented in CPython?"; all read October 2026.

The two designs make different trade-offs. Java's 50% growth means fewer resizes but up to a third of the block unused after a resize; CPython's smaller over-allocation wastes less memory per list but resizes more often. Both choices keep the average cost of appending constant, and both keep $O(1)$ indexing, which a linked structure cannot offer. Inserting at the front is slow in both, because every element must shift one place.

Arrays and lists in code

One-dimensional arrays

An array stores a fixed number of elements of one data type under one name. Each element is reached by its index, counting from 0, so an array of length $n$ has indices 0 to $n - 1$.

Each stored value is called an element. The index says where an element is; the element is the value found there. In rainfall[3] = 21, 3 is the index and 21 is the element.

The two course languages create fixed-size arrays differently. Java has true static arrays: int[] rainfall = new int[7]; creates seven integers, each set to a default value (0 for numbers, false for boolean, null for objects such as String), and rainfall.length gives 7. Python has no built-in static array in this sense. A list created at a fixed size with rainfall = [0] * 7 and never appended to or removed from behaves like one, and that is how Python programs model a static array. Python also offers the tuple for a sequence that must never change.

A Java array is still created at run time, and in Java every array is stored on the heap. What makes it static is that its length can never change once new has run; immutability is a different idea, because the elements of a Java array can be overwritten freely.

Reading, updating and traversing

Reading or writing one element uses its index in square brackets: rainfall[3] reads the fourth element and rainfall[3] = 21 replaces it. Many tasks need every element in turn, such as a total, an average, a maximum or a count, and visiting each element in order is called traversal.

Two loops traverse an array. A counted loop runs an index from 0 to the last index, which gives both the position and the value; a for-each loop gives each value directly but not its index. The program for a week of rainfall uses both: a counted loop to find the total and the wettest day (which needs the index), and a for-each loop to count the dry days.

Both programs print the same results:

The maximum starts as the first element, not as 0, so the code also works when every value is negative. The total, maximum and count are all written as loops rather than with Python's sum, max or len, which shows the work those built-ins do and gives code that runs where they are not available. The Java version casts total to double before dividing; without the cast, 49 / 7 would use integer division and any fractional part would be lost.

Lists in Python and ArrayList in Java

Python's built-in sequence type is the list. It is ordered, indexed from 0 and dynamic, and it can hold values of any type.

Java separates the two ideas. Its arrays are static, and the class ArrayList from the package java.util provides the dynamic version.

The type in angle brackets says what the ArrayList holds. It must be a class, so whole numbers are stored as Integer and decimals as Double; Java converts between int and Integer automatically (called autoboxing), so list.add(5) works. The table pairs the common operations in the two languages.

The playlist program uses each kind of operation once and prints the list after each change.

The Python version prints:

After remove("Intro"), "Rain" moves to index 0, so pop(0) removes "Rain". Every removal or insertion changes the index of each element after it, which is the source of several common bugs.

What insert and remove do inside

Adding to the end of a dynamic array is cheap, but inserting in the middle is not. The insertion diagram shows insert(1, 55) on an array holding 40, 70 and 90: to open a gap at index 1, the array moves 90 one place right, then 70, and only then writes 55. The moves start from the end; starting from the gap would overwrite 90 with 70 before 90 had been moved.

Removing at an index does the reverse: every later element moves one place left to close the gap. Both operations take time proportional to the number of elements that move, so inserting or removing at the front of a list of $n$ elements is $O(n)$, while adding or removing at the end is usually $O(1)$. The functions insert_at and remove_at do the shifting by hand on a fixed block of six slots, with a separate counter size for the slots in use: the same work that insert and pop hide.

The Python functions use global size because they assign to the global variable size; the Java version uses a static field for the same purpose.

Removing elements during a traversal

A frequent task is removing every element that fails a test, such as every mark below 40. Removing while stepping forward through a list skips elements: after a removal, the next element slides into the current index, and the loop then moves past it without checking it.

The forward loop removes 30 at index 1, 28 slides into index 1, and the loop moves on to index 2, so 28 is never tested. Walking backwards avoids this because a removal only moves elements that have already been checked. Another safe approach is to build a new list containing only the elements to keep. In Python, marks[:] makes a copy of the list so that the original stays unchanged.

Two-dimensional arrays

Many kinds of data come as a table: scores for several students on several tests, seats in rows of a cinema, pixels in an image, squares on a board. A two-dimensional array stores such a table as rows and columns, and each element needs two indices.

By convention the first index selects the row and the second selects the column: scores[r][c]. The grid diagram shows three students (rows 0 to 2) and four tests (columns 0 to 3). scores[1] is the whole of row 1, the list [90, 84, 77, 95], and scores[1][3] is the single element 95 at the end of that row.

In Java, int[][] scores = new int[3][4]; creates three rows of four integers, all 0, and the values can also be written directly between braces. scores.length is the number of rows (3) and scores[0].length the number of columns (4). Python has no separate 2D type: a 2D list is a list of lists, and len(scores) and len(scores[0]) give the rows and columns.

Traversing a 2D array with nested loops

Visiting every element needs a nested loop: an outer loop over the rows and an inner loop over the columns. Processing a whole row before moving to the next is called row-major order, and it suits per-row results such as each student's total. Swapping the loops gives column-by-column order, which suits per-column results such as each test's average.

The position of total = 0 decides what is totalled. Placed inside the outer loop, the total restarts for every row (or column); placed before both loops, it would accumulate the whole grid. In every case the indices stay in the order scores[r][c], whichever loop is outside.

The program row_max finds something about each row of a small grid; its Java version, RowMax, is identical in structure.

Creating 2D lists in Python safely

Python offers a tempting shortcut for an empty grid, [[0] * 4] * 3, but it is wrong. The inner expression makes one row; multiplying the outer list by 3 copies the reference to that row three times. The aliasing diagram contrasts the two results: shared has three slots pointing at the same row, so a change to shared[0][1] appears in every row, while board has three separate rows.

The fault is easy to miss because the shortcut looks correct when printed before any change. It comes from how lists store references to objects rather than the objects themselves, the same reason a dynamic array can hold values of mixed types.

Stacks

Last in, first out

A stack holds items in a pile and allows access to one end only, called the top. A new item goes on top, and the only item that can be removed is the one on top: the one added most recently. A pile of plates in a canteen behaves this way, and so does the undo feature of a text editor, which reverses the most recent change first.

The order a stack enforces has its own name, LIFO. Items leave in the reverse of the order they arrived: push A, B and C and they come back as C, B and A.

The term "stack" also names the call stack that a running program uses to keep track of subprogram calls. The call stack works on exactly the LIFO rule but is managed by the language, not written by the programmer; it is HL content in subtopic B2.4, Programming algorithms.

The four stack operations

A stack is defined by what can be done to it. Four operations are enough for almost every use, and each acts only on the top.

The opposite operation removes the top item and hands it back to the program.

Sometimes a program only needs to know what is on top, without changing the stack.

Before popping or peeking, a program must know whether there is anything to remove.

An array-based stack keeps track of the top with a single integer variable that holds the index of the top item. On an empty stack it holds −1, one below the first index.

The stack sequence diagram follows a stack of capacity 3 through six operations. Each push moves the top pointer up one place and writes the new item there; each pop reads the item at the top pointer and moves the pointer down; peek reads without moving anything.

The same sequence can be recorded as a table with one row per operation, a compact written record of every change. The contents are listed bottom to top.

After the pop, the 5 may still be stored in slot 2 of the array, but it is no longer part of the stack: the top pointer marks where the stack ends, and the next push overwrites that slot with 8.

Overflow and underflow

An array-based stack has a fixed capacity, so two things can go wrong. Pushing onto a full stack has nowhere to put the item, and popping an empty stack has nothing to return. A correct implementation checks for both before acting.

The empty case has its own name.

The Stack class implements all four operations on a fixed-size array, plus is_full to detect overflow. It raises an exception on overflow or underflow rather than returning a wrong value, so the calling code can decide what to do.

Both programs print:

The order of the two lines inside push matters. The pointer moves up first and the item is written at the new position; in pop, the item is read first and the pointer moves down afterwards. Reversing either pair overwrites the top item or returns the wrong one.

Stack performance and memory

Push, pop, peek and isEmpty each read or change one slot and one pointer, so each takes constant time, $O(1)$, however many items the stack holds. No element ever moves, because nothing is inserted or removed anywhere except the top. A program that only ever needs the most recent item therefore avoids the $O(n)$ shifting of a list insertion or removal at the front.

Memory depends on how the stack is built. An array-based stack reserves its full capacity when it is created, so a stack of capacity 1,000 holding 3 items still occupies 1,000 slots, and a 1,001st push overflows. A dynamic stack, built on a dynamic array or a linked structure, grows as items arrive: its memory is roughly proportional to the number of items, and it overflows only when the computer runs out of memory. The trade-off is the same one as between static and dynamic arrays: predictable, fixed memory with a hard limit, or flexible memory with occasional resizing (or, for a linked stack, an extra reference stored with every item).

Both course languages provide ready-made stacks. In Python, a list is used directly: append pushes, pop() with no argument pops from the end, stack[-1] peeks and len(stack) == 0 tests for empty, and all of these are $O(1)$ because they work at the end of the list. In Java, the ArrayDeque class provides push, pop, peek and isEmpty. Java also has an older class called Stack, which still works but is no longer recommended.

In the print-queue half of the program, the oldest job leaves first rather than the newest, which is the behaviour of a queue. The Java version prints false in lower case.

Choosing a stack

A stack is the right choice whenever a problem needs the most recent unfinished item first. That pattern appears in many places:

• Undo in editors. Each change is pushed; undo pops the most recent change and reverses it. A second stack often holds undone changes so that redo can push them back.

• Browser back button. Each page visited is pushed; Back pops the current page and shows the page visited before it.

• Reversing data. Pushing a sequence and then popping everything returns it in reverse order.

• Matching brackets. Each opening bracket is pushed; each closing bracket must match the bracket popped from the top.

• Evaluating expressions. Calculators and compilers use stacks to hold numbers and operators until they can be combined in the right order.

• Backtracking. A maze solver pushes each junction it passes, and pops back to the most recent junction when it reaches a dead end (depth-first search).

• Subprogram calls. The language keeps a call stack: a call pushes a record of where to return, and a return pops it.

Bracket matching shows why only the top matters. In f(x[2)] the ] and ) are each present, but the ) arrives while [ is still open, so the brackets cross. The function is_balanced pushes every opener and checks each closer against the most recent opener.

The three failing strings fail in three different ways: a closer that does not match the top (f(x[2)]), an opener left on the stack at the end (((a + b)), and a closer arriving when the stack is empty (g(h[i])}). The empty check before each pop is what prevents underflow in the third case.

Queues

First in, first out

A queue works like a line of people at a ticket counter. Newcomers join at the back, the person at the front is served next, and nobody jumps ahead. Items leave in the order they arrived, which makes a queue the fair choice wherever requests must be served in turn.

The order a queue enforces is the opposite of a stack's.

A queue has two ends with different jobs, so it needs a name for each and an operation for each.

Removing happens only at the other end.

The front is where the next item to leave waits; the operation of the same name reads it without removing it, just as peek does for a stack.

The other end has its own pointer.

The fourth operation, isEmpty, is the same as for a stack: it reports whether the queue holds any items, and a program checks it before dequeuing. Dequeuing an empty queue is an underflow, and enqueuing onto a full fixed-size queue is an overflow, exactly as for a stack.

A linear queue in an array

The simplest array-based queue keeps a front pointer and a rear pointer that both move only to the right. Enqueue increases rear and writes the item there; dequeue reads the item at front and increases front. Both are $O(1)$, because no elements move.

The linear queue diagram shows the flaw. After four enqueues and two dequeues, slots 0 and 1 are empty, but rear can only move right. After two more enqueues, rear reaches the last slot and the queue reports that it is full, although two of its six slots are free.

There are two simple fixes, and both have a cost. The first is to shift every remaining item one place left after each dequeue, so the front is always at index 0; this reuses the space but makes every dequeue $O(n)$. The second is to let the pointers wrap round to the start of the array, which keeps every operation $O(1)$ and reuses every slot. That second design is the circular queue.

Circular queues

A circular queue treats the array as a ring: the slot after the last one is slot 0. When rear reaches the end and slot 0 is free, the next item goes into slot 0.

The wrap is done with the modulo operator. With capacity $n$, the next index after $i$ is $(i + 1) \bmod n$: for capacity 4, $(2 + 1) \bmod 4 = 3$ and $(3 + 1) \bmod 4 = 0$. The circular queue diagram shows a queue of capacity 4 after the sequence used in the program that follows. P5 and P6 sit in slots 0 and 1 because the rear pointer has wrapped round, but the front pointer is at slot 2, so P3 leaves first.

Once the pointers wrap, comparing them no longer shows whether the queue is empty or full: in both cases the rear sits just behind the front. The usual solution is a third variable, count, which holds the number of items. The queue is empty when count is 0 and full when count equals the capacity.

The trace table records the pointers after each operation of the program. The rear pointer starts at −1 so that the first enqueue moves it to index 0.

A linear queue of the same capacity would have refused P5, because its rear pointer would already be at the last slot; the circular queue reuses slots 0 and 1, which P1 and P2 freed.

Queue performance and memory

A well-built queue performs enqueue, dequeue, front and isEmpty in $O(1)$ time: each changes one slot and one or two variables. A circular queue in an array reserves its whole capacity at creation, so its memory is fixed and it can overflow; a dynamic queue, built on a growing array or a linked structure, uses memory roughly proportional to the number of items waiting.

Problems arise when a structure's cheap end is the wrong one for the task. A Python list makes a good stack because its end is cheap to change, but its front is not: list.pop(0) must shift every remaining element one place left, so it takes $O(n)$ time. Python's standard library provides collections.deque for queues, whose append and popleft are both $O(1)$. In Java, ArrayDeque is used with offer to enqueue, poll to dequeue and peek to read the front; a queue declared as Queue<String> q = new LinkedList<String>(); offers the same three methods.

Choosing a queue

A queue is the right choice whenever items must be handled in the order they arrive, often because something produces work faster than something else can process it. The queue holds the waiting items in arrival order until the slower part is ready for them.

• Print queue (spooler). Documents sent to a shared printer wait in a queue and print in the order they were sent.

• Keyboard buffer. Key presses are stored in a queue until the program reads them, so fast typing is not lost and the letters stay in order.

• CPU scheduling. An operating system keeps processes that are ready to run in a ready queue; round robin scheduling takes the process at the front, runs it for a time slice, then enqueues it again at the rear (subtopic A1.3, Operating systems and control systems).

• Network buffers. A router stores each arriving packet in a queue until the outgoing link is free, and sends packets in arrival order.

• Breadth-first search. Exploring a map or a network level by level enqueues every neighbour of the current place, so nearer places are visited before farther ones.

• Online waiting rooms and call centres. Customers are served in arrival order.

The waiting-room case shows that a queue's fairness depends on the system behind it. When verified fans tried to buy tickets in the presale for the US leg of Taylor Swift's Eras Tour on 15 November 2022, Ticketmaster's site could not cope with the demand, and many users reported sitting in a queue of 2,000 or more people that appeared frozen. The widespread criticism was followed by a US Department of Justice investigation into the parent company, Live Nation Entertainment.

Source: Wikipedia, "Ticketmaster" (section on the Eras Tour presale), read October 2026.

Stacks and queues compared

Stacks and queues are built in similar ways but release items in different orders. Both hold a sequence of items, both allow access only at their ends, both can be built on a fixed-size array (with overflow and underflow) or a dynamic structure, and both perform all four of their operations in $O(1)$ time when built well. They differ in which item leaves next.

A combination of the two sometimes appears in one product. A text editor uses a stack for undo, because the newest change must be reversed first, but sends documents to the printer through a queue, because the oldest job must print first. In each case the choice follows from which item the problem must process next.

Exam focus

Data structures are examined on Paper 2. "Compare static and dynamic data structures" appears as a 4–6 mark question in which each point should refer to both structures. Construct questions ask for code that processes a 1D or 2D array or a list (totals, averages, maximums, counts, searches, adding and removing), often with built-ins such as len, sum, max or pop banned, for 4–8 marks. Trace and state questions give a sequence of stack or queue operations and ask for the contents, the pointers and the values returned, for 2–4 marks. Explain questions ask why a stack or a queue suits a scenario, or what an operation costs in time and memory, for 2–4 marks. Marks go to features of the code (correct loop bounds, correct indices, correct initialisation and update, correct return), not to perfect syntax.

When a code question bans a built-in, it usually wants the loop that the built-in hides: a counter instead of len, a running total instead of sum, a running maximum instead of max. Practise writing each of these on lists and on 2D arrays until it takes less than a minute.

Questions on performance expect precise statements: "push and pop are $O(1)$ because only the top slot and the top pointer change" earns credit, while "stacks are fast" does not. For memory, say whether the structure reserves a fixed capacity or grows with the number of items.

Practice questions

1. Define the term dynamic data structure. [2]

2. State the output of the Python code nums = [4, 8, 15, 16, 23] followed by print(nums[2], nums[len(nums) - 1]) (Java: int[] nums = {4, 8, 15, 16, 23}; and System.out.println(nums[2] + " " + nums[nums.length - 1]);), and identify the index of the element 16. [2]

3. Outline what happens inside a dynamic array when an item is added and the array is full. [3]

4. Construct a function or method that takes a 2D array of integers and returns the sum of each column as a list or array, without using sum. [5]

5. A stack of capacity 3 is empty. Trace the operations push(1), push(2), push(3), push(4), pop(), pop(), peek(), stating what happens at each step and the final value of the top pointer (−1 when empty). [4]

6. Explain why a circular queue makes better use of memory than a linear queue implemented in an array. [3]

7. Explain why list.pop(0) is a poor way to dequeue from a long queue in Python, and state a better alternative. [3]

8. Construct code that removes every negative number from a list of integers, without skipping any element. [4]

9. A web browser stores the addresses a user has visited so that the Back button can return to each earlier site in turn. Explain which data structure is appropriate and how its operations are used. [3]

10. Compare a static array and a dynamic list for storing the scores of a football league that always has 20 teams, and a record of every goal scored in a season, whose number is not known in advance. [4]

Summary

• A data structure organises many values in memory together with the operations to use them. Static structures have a size fixed at creation; dynamic structures grow and shrink at run time.

• A static array is one contiguous block, so any element's address is base address + index × element size and access by index is $O(1)$; it cannot grow and may waste memory or overflow.

• Java's ArrayList and Python's list are dynamic arrays: when full, they allocate a larger block (Java about 50% larger, CPython about one eighth larger), copy every element and continue, so appending is $O(1)$ on average at the cost of spare capacity.

• Arrays and lists are indexed from 0 to length − 1. Traversal uses a counted loop (index and value) or a for-each loop (value only); totals, maximums and counts can be written without built-ins.

• Inserting or removing in the middle of a list shifts later elements and is $O(n)$; removing during a forward traversal skips elements, so loop backwards or build a new list.

• A 2D array is accessed as grid[row][col] and traversed with nested loops; in Python each row must be created separately, never with [[0] * n] * m.

• A stack is LIFO: push, pop, peek and isEmpty all act on the top in $O(1)$ time. An array-based stack uses a top pointer (−1 when empty) and can overflow (push when full) or underflow (pop when empty).

• A queue is FIFO: enqueue at the rear, dequeue and front at the front, isEmpty to check. A linear array queue wastes freed slots; a circular queue wraps its pointers with (i + 1) % capacity and uses a count to tell full from empty.

• Use a stack when the most recent item is needed first (undo, back button, bracket matching, backtracking) and a queue when items must be served in arrival order (printing, keyboard buffer, CPU scheduling, packet buffers).

Self-check

• To do:

  I can explain the difference between the size and the contents of a static array, and between size and capacity in a dynamic array.

• To do:

  I can calculate the address of an array element from the base address, the index and the element size.

• To do:

  I can describe the steps of a dynamic array resize and explain why growing by a proportion is faster than growing by one slot.

• To do:

  I can compare static and dynamic structures point by point, with a similarity and a scenario for each.

• To do:

  I can create, update and traverse a 1D array in Java and a list in Python, using both a counted loop and a for-each loop.

• To do:

  I can find a total, average, maximum and count without sum, len, max or min.

• To do:

  I can use add, insert, get, set, remove and size on an ArrayList, and their equivalents on a Python list.

• To do:

  I can remove elements from a list during a traversal without skipping any.

• To do:

  I can create a 2D array in both languages, avoid the Python row-aliasing trap, and compute row and column totals with nested loops.

• To do:

  I can trace a sequence of push, pop and peek operations, recording the top pointer and the values returned.

• To do:

  I can write an array-based stack class that detects overflow and underflow.

• To do:

  I can trace a circular queue, including the pointer wrapping from the last index to 0.

• To do:

  I can explain why list.pop(0) is $O(n)$ and name the $O(1)$ alternatives in Python and Java.

• To do:

  I can justify choosing a stack or a queue for a given scenario and state what would go wrong with the other.

Markscheme (c)

3