Arrays, dynamic arrays and tuples

An array stores its elements side by side in one block of memory. Every element has the same size, so the computer finds element i with one calculation: start address plus i times the element size. That is why reading any element by index takes the same short time, O(1), whether the array holds ten items or ten million.

The price is rigidity. A classic array has a fixed size chosen when it is created, and it is only fast when you know the index. Looking for a value without knowing where it is means checking elements one by one: O(n).

temps = [21, 19, 23, 25]   # a list: Python has no fixed-size array in the core language
temps[2]                    # 23, O(1)

from array import array
prices = array('d', [9.5, 10.0, 10.25])   # compact array of floats

let temps: [i32; 4] = [21, 19, 23, 25]; // size is part of the type
let third = temps[2];                    // 23
// temps[10] would panic at runtime: indexes are bounds-checked

Most of the time you don't know the size in advance, so languages offer a dynamic array: Python's list, Rust's Vec, Java's ArrayList. Inside it is an ordinary array with spare room. Its length is how many elements you stored; its capacity is how many fit before it must grow.

When it's full and you append, it allocates a bigger block, usually about twice the size, copies everything over, and frees the old block. Copying is slow, but it happens rarely, and each time it doubles the room. Spread over all appends, the cost per append is O(1) on average. This is called amortised O(1).

msgs = []
msgs.append("hi")       # amortised O(1)
msgs.extend(["how", "are", "you"])
len(msgs)               # 4

let mut msgs: Vec<&str> = Vec::with_capacity(100); // reserve room up front
msgs.push("hi");
println!("{} of {}", msgs.len(), msgs.capacity()); // 1 of 100

Adding at the end of a dynamic array is cheap. Adding at the front or in the middle is not: every element after that position has to move one step to make room, and removing works the same way in reverse. That is O(n), and with a million elements it's a million moves.

If a program keeps inserting or removing at the front, an array is the wrong tool. A deque (lesson 4) or a linked list (lesson 3) handles that end cheaply.

tasks = ["b", "c", "d"]
tasks.insert(0, "a")   # O(n): shifts b, c, d
tasks.pop(0)            # O(n) again

from collections import deque
q = deque(tasks)
q.appendleft("a")       # O(1)

let mut tasks = vec!["b", "c", "d"];
tasks.insert(0, "a");   // O(n)

use std::collections::VecDeque;
let mut q: VecDeque<&str> = tasks.into_iter().collect();
q.push_front("a");      // O(1)

A tuple groups a fixed number of values, often of different types, where each position has a meaning: (latitude, longitude), (status code, message). An array is a row of the same kind of thing; a tuple is one record.

In Python tuples are immutable: you can't change them after creation. That makes them hashable, so they can be dictionary keys and set members, which lists can't. In Rust a tuple's type lists every position, like (f64, f64, &str); whether you can change it depends on whether the variable is declared mut. When the positions need names, both languages offer something clearer: a named tuple or dataclass in Python, a struct in Rust.

place = (51.50, -0.12, "London")
lat, lon, name = place          # unpacking
distance = {("London", "Paris"): 344}   # tuple as a dict key
# place[0] = 52  -> TypeError: tuples are immutable

let place: (f64, f64, &str) = (51.50, -0.12, "London");
let (lat, lon, name) = place;    // destructuring
let first = place.0;

struct Place { lat: f64, lon: f64, name: String } // when names help

Putting it together for a dynamic array of n elements:

Read or write by index: O(1). Append at the end: amortised O(1). Insert or remove at the front or in the middle: O(n). Find a value without knowing its index: O(n), unless the array is sorted, in which case binary search finds it in O(log n).

Arrays also have an advantage the O-notation hides: elements sit next to each other, so the processor reads them into its cache in chunks. Walking through an array is often several times faster than walking through the same number of elements scattered around memory, as in a linked list.