Describe arrays and records as data structures, explain constant-time array indexing and contrast static with dynamic arrays

What this dot point is asking

SEAB wants you to describe arrays and records as data structures, explain why array indexing is constant time, and contrast static with dynamic arrays. The central idea is that an array's contiguous layout lets any element be reached by a single address calculation, while a record bundles related values of different types into one named unit.

The answer

Arrays and contiguous storage

An array is an ordered collection of elements of the same type, stored in contiguous (adjacent) memory locations and accessed by an integer index starting at 0. Because the elements sit back to back, the address of element $i$ is:

This single multiplication and addition is independent of the array's length, so reading or writing array[i] is $O(1)$ - constant-time random access. This direct addressing is the array's defining strength.

The cost of insertion and deletion

The same fixed layout makes structural changes expensive. Inserting at the front, or deleting from the front, requires shifting every following element, which is $O(n)$. Only appending at the end (with room) is cheap.

Two-dimensional arrays

A 2D array (a grid or matrix) is indexed by row and column, grid[r][c], and is typically stored row by row in memory (row-major order). The address arithmetic extends naturally, so element access is still $O(1)$.

Records

A record (or struct) groups several fields, which may be of different types, under one name:

# a record-like structure for one student
student = {"name": "Wei Ling", "age": 17, "grade": "A"}

Where an array holds many items of one type, a record holds related items of mixed types as one logical unit. An array of records then stores many such units, indexed by position - far safer than keeping several parallel arrays in step.

Static versus dynamic arrays

• A static array has a fixed size, set at creation; it cannot grow.
• A dynamic array can resize: when full, it allocates a larger block and copies the elements, giving amortised $O(1)$ appends despite occasional costly copies. Python's list is a dynamic array.

Examples in context

Example 1. An image as a 2D array. A greyscale image is a grid of pixel values stored as a two-dimensional array. Reading pixel (r, c) is instant address arithmetic, which is why image filters that touch every pixel are efficient - each access is $O(1)$ and the whole pass is $O(\text{width} \times \text{height})$.

Example 2. A record of fixed format. A weather station logs each reading as a record of timestamp, temperature, humidity and pressure. Storing readings as an array of these records keeps every reading's fields together and lets the program jump to the thousandth reading instantly by index, rather than juggling four separate arrays.

Try this

Q1. State and justify the time complexity of reading array[100] in an array of 1000 elements. [2 marks]

• Cue. $O(1)$ - the address is computed directly from base, index and element size, regardless of length.

Q2. Why is inserting an element at the front of an array $O(n)$? [1 mark]

• Cue. Every existing element must shift one place right to make room, which is $n$ moves.

Q3. Give one advantage of an array of records over several parallel arrays. [1 mark]

• Cue. Each item's fields stay bundled together, so the arrays cannot fall out of step and one record moves as a unit.