Arrays in memory: indexing, layout and cost

An array stores its items in one block of memory, side by side, every slot the same size. That layout is the whole story of its costs. To read item i, the computer does not search: it takes the address where the block starts, adds i times the size of one slot, and reads there, so a[i] costs the same for the first item and the millionth, O(1). Inserting or deleting in the middle is the opposite: the block has no gaps, so every item after the position must move one slot, O(n) in the worst case. Searching an unsorted array for a value has to look at the items one by one, also O(n). This lesson shows the arithmetic on real memory, what different languages put in each slot, and what happens when an index falls outside the block.

One block, equal slots: why a[i] is one step

Call the address of the first slot the base and the size of one slot w bytes. Item 0 sits at the base, item 1 at base + w, and item i at base + i × w. A 4-byte integer array that starts at address 1000 has a[3] at 1000 + 3 × 4 = 1012. Finding any item takes one multiplication and one addition, whatever the index, which is why indexes start at 0 in most languages: the index is the distance from the base, counted in slots.

The formula is not a teaching model: it is what the hardware does. Python’s array module stores numbers in such a block, and its buffer_info() method returns the base address. The program below reads each item straight from memory at base + i × itemsize with ctypes, without asking the array, and gets the same values back:

"""Finds array elements by address arithmetic: a[i] sits at base + i * item size.

array.array keeps its items side by side in one block of memory. buffer_info() gives the address of a[0] (the base)
and the number of items; ctypes then reads the bytes at base + i * itemsize directly, without asking the array.
"""

import ctypes
from array import array


def read_by_address(a, ctype):
    base, length = a.buffer_info()
    print(f"array('{a.typecode}') of {length} items, {a.itemsize} bytes each")
    for i in range(length):
        offset = i * a.itemsize
        value = ctype.from_address(base + offset).value
        print(f"  base + {offset:2} bytes holds {value!r:5}   a[{i}] is {a[i]!r}")


read_by_address(array("i", [7, 11, 13, 17, 19]), ctypes.c_int)
read_by_address(array("d", [0.5, 1.5, 2.5]), ctypes.c_double)

# One multiplication and one addition find any item: the last of a million costs what the first costs.
squares = array("q", (k * k for k in range(1_000_000)))
base, length = squares.buffer_info()
i = length - 1
offset = i * squares.itemsize
print(f"squares[{i:,}] is at base + {offset:,} bytes and holds {ctypes.c_longlong.from_address(base + offset).value:,}")

array('i') of 5 items, 4 bytes each
  base +  0 bytes holds 7       a[0] is 7
  base +  4 bytes holds 11      a[1] is 11
  base +  8 bytes holds 13      a[2] is 13
  base + 12 bytes holds 17      a[3] is 17
  base + 16 bytes holds 19      a[4] is 19
array('d') of 3 items, 8 bytes each
  base +  0 bytes holds 0.5     a[0] is 0.5
  base +  8 bytes holds 1.5     a[1] is 1.5
  base + 16 bytes holds 2.5     a[2] is 2.5
squares[999,999] is at base + 7,999,992 bytes and holds 999,998,000,001

The last line reads the millionth square at base + 7,999,992 bytes with the same single calculation as the first item. Compiled languages show the same arithmetic. The C++ and Go programs below print where each element of a vector or slice sits, measured from element 0:

// Where the elements of a std::vector sit: v[i] is i * sizeof(element) bytes after v[0].
#include <cstddef>
#include <cstdio>
#include <vector>

template <typename T>
void offsets(const char* name, const std::vector<T>& v) {
  const char* base = reinterpret_cast<const char*>(v.data());
  std::printf("%-20s %zu byte%s each; v[i] sits at v[0] +", name, sizeof(T), sizeof(T) == 1 ? "" : "s");
  for (std::size_t i = 0; i < v.size(); ++i) {
    std::printf(" %td", reinterpret_cast<const char*>(&v[i]) - base);
  }
  std::printf(" bytes\n");
}

int main() {
  offsets("std::vector<char>", std::vector<char>{'a', 'r', 'r', 'a', 'y'});
  offsets("std::vector<int>", std::vector<int>{7, 11, 13, 17, 19});
  offsets("std::vector<double>", std::vector<double>{0.5, 1.5, 2.5, 3.5, 4.5});
}

// Where the elements of a Go slice sit: s[i] is i times the element size after s[0].
package main

import (
	"fmt"
	"unsafe"
)

func offsets[T any](name string, s []T) {
	base := uintptr(unsafe.Pointer(&s[0]))
	fmt.Printf("%-10s %d bytes each; s[i] sits at s[0] +", name, unsafe.Sizeof(s[0]))
	for i := range s {
		fmt.Printf(" %d", uintptr(unsafe.Pointer(&s[i]))-base)
	}
	fmt.Println(" bytes")
}

func main() {
	offsets("[]int32", []int32{7, 11, 13, 17, 19})
	offsets("[]int", []int{7, 11, 13, 17, 19})
	offsets("[]float64", []float64{0.5, 1.5, 2.5, 3.5, 4.5})
}

from session import run, versions

# The C++ file is built with warnings on; go run builds and runs the Go file.
versions("clang++ --version", "go version")
run("""
clang++ -std=c++23 -O1 -Wall -Wextra strides.cpp -o strides && ./strides
go run strides.go
""")

# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ clang++ -std=c++23 -O1 -Wall -Wextra strides.cpp -o strides && ./strides
std::vector<char>    1 byte each; v[i] sits at v[0] + 0 1 2 3 4 bytes
std::vector<int>     4 bytes each; v[i] sits at v[0] + 0 4 8 12 16 bytes
std::vector<double>  8 bytes each; v[i] sits at v[0] + 0 8 16 24 32 bytes
$ go run strides.go
[]int32    4 bytes each; s[i] sits at s[0] + 0 4 8 12 16 bytes
[]int      8 bytes each; s[i] sits at s[0] + 0 8 16 24 32 bytes
[]float64  8 bytes each; s[i] sits at s[0] + 0 8 16 24 32 bytes

The step between neighbours is exactly the element size: 1 byte for a char, 4 for an int or int32, 8 for a double, a float64 or a Go int on a 64-bit computer. The Programmer Calculator does the same arithmetic in hexadecimal, the way debuggers print addresses.

Values or references: what a slot holds

The address arithmetic needs every slot to be the same size, so a slot cannot hold a value of any length. Languages solve this in two ways.

• Values in place. The slots hold the numbers themselves: Python’s array.array, Java’s int[], C++’s std::vector<int>, Go’s []int32 and JavaScript’s Int32Array. One block holds everything, and reading the items in order walks straight through memory.
• References. The slots hold addresses of objects stored elsewhere. Python’s documentation says that a CPython list is “a contiguous array of references to other objects”, so indexing a list is still O(1), but each number is a separate object somewhere else on the heap. Java’s ArrayList<Integer> works the same way, with a reference per Integer object.

The space-complexity lesson measured what references cost: about 40 MB for a list of a million numbers against about 8 MB for an array('q'). Values in place have a second price: the slot has a fixed type, and a value that does not fit is either refused or changed.

What each container keeps in a slot, and what happens to a value too large for it:

• Python list: a reference, 8 bytes on 64-bit CPython. Any object fits, so the question never arises.
• Python array('i'): a C int, 4 bytes. A value outside its range raises OverflowError.
• Java int[]: an int, 4 bytes. A wider value needs a cast, which keeps its lowest 32 bits.
• C++ std::vector<int>: an int, 4 bytes. A wider value is converted, keeping its lowest 32 bits.
• JavaScript Int32Array: a 32-bit integer, 4 bytes. The lowest 32 bits are kept, so a large value wraps round.
• JavaScript Array: any value, laid out as the engine chooses. Any value fits.

A JavaScript Array can hold any value, and the language leaves its layout to the engine; typed arrays such as Int32Array exist to give a fixed layout of numbers. MDN describes what happens to a value outside a typed array’s range: integer arrays keep its lowest bits, which the section on reading past the end shows as 2³¹ turning into −2,147,483,648.

What insert, delete and search cost

Reading and writing a slot are O(1). Everything that changes how many items there are, or looks for a value, costs more, and Python’s documentation lists the exact counts for its lists:

The moves are real work, and a stopwatch sees them. This program reads one item, then inserts an item and deletes it again, at the front, the middle and the end of a list of a million numbers:

"""Times a read, and an insert followed by a delete, at the front, middle and end of a list of a million items.

A read finds its slot by arithmetic, so it costs the same everywhere. An insert at position i first moves the n - i
items after it one slot to the right, and the delete moves them back, so the pair gets cheaper towards the end.
The three positions are timed in turn, 21 rounds, and each keeps its fastest round: that filters out the moments when
the computer was busy with something else, and treats the three positions alike.
"""

import timeit

N = 1_000_000
items = list(range(N))
POSITIONS = (("front, i = 0", 0), ("middle, i = 500,000", N // 2), ("end, i = 1,000,000", N))


def timer(statement, i, number):
    t = timeit.Timer(statement, globals={"items": items, "i": i})
    return lambda: t.timeit(number) / number


reads = [timer("items[i]", min(i, N - 1), 20_000) for _, i in POSITIONS]
shifts = [timer("items.insert(i, -1); del items[i]", i, 20) for _, i in POSITIONS]
best_read = [float("inf")] * 3
best_shift = [float("inf")] * 3
for _ in range(21):
    for k in range(3):
        best_read[k] = min(best_read[k], reads[k]())
        best_shift[k] = min(best_shift[k], shifts[k]())

print(f"a list of {N:,} items")
print(f"{'position':<22}{'items moved':>12}{'read':>9}{'insert + delete':>18}")
for (name, i), r, s in zip(POSITIONS, best_read, best_shift):
    print(f"{name:<22}{N - i:>12,}{r * 1e9:>6.0f} ns{s * 1e6:>12.2f} µs")
assert items == list(range(N))

a list of 1,000,000 items
position               items moved     read   insert + delete
front, i = 0             1,000,000    12 ns      552.14 µs
middle, i = 500,000        500,000    13 ns      253.23 µs
end, i = 1,000,000               0    12 ns        0.06 µs

The read takes about the same few nanoseconds at every position. The insert and delete at the front move a million references twice and take hundreds of microseconds; in the middle they move half as many and take about half as long; at the end they move nothing. Insert at the front of a long list in a loop and those microseconds multiply: building n items that way moves 0 + 1 + … + (n − 1) = n(n − 1)/2 items, which is O(n²).

Two habits follow. Add at the end when the order of arrival does not matter, and when items must come off the front as well, use a structure built for it, such as collections.deque, which the counting-operations lesson timed against list.pop(0).

Reading past the end: five languages, five answers

An index outside the array is a classic bug, and languages differ in what they promise when it happens. Python and JavaScript first:

"""What Python does with an index past either end of a list or an array."""

from array import array

scores = [10, 20, 30]
for i in (3, -1, -4):
    try:
        print(f"scores[{i}] = {scores[i]}")
    except IndexError as error:
        print(f"scores[{i}] raises IndexError: {error}")

typed = array("i", [10, 20, 30])
try:
    typed[3] = 40
except IndexError as error:
    print(f"typed[3] = 40 raises IndexError: {error}")
try:
    typed[0] = 2**31
except OverflowError:
    print("typed[0] = 2**31 raises OverflowError: the value does not fit in a C int")

# A slice is forgiving: it stops at the end instead of raising.
print("scores[1:10] =", scores[1:10])

scores[3] raises IndexError: list index out of range
scores[-1] = 30
scores[-4] raises IndexError: list index out of range
typed[3] = 40 raises IndexError: array assignment index out of range
typed[0] = 2**31 raises OverflowError: the value does not fit in a C int
scores[1:10] = [20, 30]

// What JavaScript does with an index past the end of an Array and of a typed array.
const scores = [10, 20, 30];
console.log('scores[3] =', scores[3]);
console.log('scores[-1] =', scores[-1], '| scores.at(-1) =', scores.at(-1));

const typed = new Int32Array([10, 20, 30]);
typed[3] = 40; // ignored: a typed array never grows
console.log('after typed[3] = 40:', Array.from(typed), 'length', typed.length);
typed[0] = 2 ** 31; // stored modulo 2^32, as a signed 32-bit integer
console.log('after typed[0] = 2 ** 31:', typed[0]);

// Writing past the end of an ordinary Array grows it and leaves holes.
const sparse = [1, 2, 3];
sparse[6] = 7;
console.log('length after sparse[6] = 7:', sparse.length);
let byForEach = 0;
sparse.forEach(() => byForEach++);
let byForOf = 0;
for (const item of sparse) byForOf++;
console.log('forEach visited', byForEach, 'items; for...of visited', byForOf);
console.log('the holes read as', sparse[4]);

scores[3] = undefined
scores[-1] = undefined | scores.at(-1) = 30
after typed[3] = 40: [ 10, 20, 30 ] length 3
after typed[0] = 2 ** 31: -2147483648
length after sparse[6] = 7: 7
forEach visited 4 items; for...of visited 7
the holes read as undefined

Python checks every index and raises IndexError, but it counts negative indexes from the end, so scores[-1] is the last item and an index that slips below 0 does not fail: only −4 is out of range for three items. JavaScript never raises for an index: reading past the end gives undefined, a typed array ignores the write to typed[3], and an ordinary Array grows instead, leaving empty slots called holes. MDN notes that older methods such as forEach skip holes while newer iteration treats them as undefined, which the run shows as 4 visits against 7. Keep arrays dense and those differences never matter.

Java, Go and C++ next. The Java specification says that every array access is checked at run time, and the Go specification makes an index out of range a run-time panic. C++’s operator[] checks nothing: an index past the size is undefined behaviour, so what happens depends on how the program was built. The session builds the same C++ file three ways:

// Java checks every array index: one past the end throws ArrayIndexOutOfBoundsException.
public class Bounds {
    public static void main(String[] args) {
        int[] a = {10, 20, 30};
        int i = a.length;
        try {
            System.out.println(a[i]);
        } catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("ArrayIndexOutOfBoundsException: " + e.getMessage());
        }
    }
}

// Go checks every slice index: one past the end panics with "index out of range".
package main

import "fmt"

func read(s []int, i int) (v int) {
	defer func() {
		if r := recover(); r != nil {
			fmt.Println("panic:", r)
		}
	}()
	return s[i]
}

func main() {
	s := make([]int, 3, 8) // length 3, capacity 8
	s[0], s[1], s[2] = 10, 20, 30
	fmt.Println("len", len(s), "cap", cap(s))
	read(s, len(s))
	fmt.Println("s[:4] is allowed (up to cap):", s[:4])
}

// Reads v[i] for the index given on the command line. operator[] checks nothing: an index past the end is
// undefined behaviour, so what happens depends on how the program was built.
#include <cstdio>
#include <cstdlib>
#include <vector>

int main(int argc, char** argv) {
  std::vector<int> v = {10, 20, 30};
  v.reserve(8);  // room for 8 ints; v.size() is still 3
  const int i = argc > 1 ? std::atoi(argv[1]) : 0;
  std::printf("size %zu, capacity %zu, reading v[%d]\n", v.size(), v.capacity(), i);
  std::fflush(stdout);
  volatile int value = v[i];
  (void)value;
  std::printf("the read returned, with no error\n");
}

from session import run, versions

versions("java -version", "clang++ --version", "go version")
# The C++ file is built three ways: with AddressSanitizer, with libc++'s fast hardening, and plainly.
run(
    """
java Bounds.java
go run bounds.go
clang++ -std=c++23 -O1 -g -fsanitize=address bounds.cpp -o bounds_asan
./bounds_asan 3
./bounds_asan 8
clang++ -std=c++23 -O1 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_FAST bounds.cpp -o bounds_hardened
./bounds_hardened 3
clang++ -std=c++23 -O1 bounds.cpp -o bounds_plain
./bounds_plain 3
""",
    expect_failure=("./bounds_asan 3", "./bounds_asan 8", "./bounds_hardened 3"),
)

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Bounds.java
ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
$ go run bounds.go
len 3 cap 8
panic: runtime error: index out of range [3] with length 3
s[:4] is allowed (up to cap): [10 20 30 0]
$ clang++ -std=c++23 -O1 -g -fsanitize=address bounds.cpp -o bounds_asan
$ ./bounds_asan 3
size 3, capacity 8, reading v[3]
AddressSanitizer: container-overflow
READ of size 4
    in main at bounds.cpp:13
  the address is 12 bytes inside of 32-byte region
SUMMARY: AddressSanitizer: container-overflow bounds.cpp:13 in main
[stopped by signal SIGABRT]
$ ./bounds_asan 8
size 3, capacity 8, reading v[8]
AddressSanitizer: heap-buffer-overflow
READ of size 4
    in main at bounds.cpp:13
  the address is 0 bytes after 32-byte region
SUMMARY: AddressSanitizer: heap-buffer-overflow bounds.cpp:13 in main
[stopped by signal SIGABRT]
$ clang++ -std=c++23 -O1 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_FAST bounds.cpp -o bounds_hardened
$ ./bounds_hardened 3
size 3, capacity 8, reading v[3]
[stopped by signal SIGTRAP]
$ clang++ -std=c++23 -O1 bounds.cpp -o bounds_plain
$ ./bounds_plain 3
size 3, capacity 8, reading v[3]
the read returned, with no error

Read the C++ results in order:

1. AddressSanitizer, index 3. The vector has size 3 but room for 8, so v[3] is inside memory the program owns. The sanitizer still reports a container-overflow: the address is 12 bytes inside the 32-byte block, past the items in use.
2. AddressSanitizer, index 8. Past the whole block: a heap-buffer-overflow, 0 bytes after the 32-byte region.
3. libc++ fast hardening. The library checks the index itself and stops the program at once with a trap (SIGTRAP), without a message. The libc++ documentation recommends that most projects adopt this mode.
4. A plain build. The read returns without any error. Nothing in the language says what value it got.

The fourth line is why out-of-bounds reads survive testing in C and C++: the program carries on with whatever bytes were there. Build tests with AddressSanitizer, use at() (which throws std::out_of_range) where an index comes from outside the program, and consider hardening for release builds. Go’s slices make the same distinction as the C++ vector: indexing stops at the length, 3, while re-slicing with s[:4] may reach up to the capacity, 8.

Exercise

FixedArray gets a block of slots once, the way a C array or a typed array does, and you write the insert and the delete that move items one at a time and count the moves.

class FixedArray:
    """Up to `capacity` items in a list of slots made once; `size` of them are in use."""

    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.size = 0

    def items(self):
        return self.slots[: self.size]

    def insert_at(self, i, value):
        """Puts value at position i (0 <= i <= size); returns how many items moved right."""
        raise NotImplementedError("write insert_at")

    def delete_at(self, i):
        """Removes the item at position i (0 <= i < size); returns how many items moved left."""
        raise NotImplementedError("write delete_at")

from fixed_array import FixedArray


def filled(*values, capacity=8):
    a = FixedArray(capacity)
    for v in values:
        a.insert_at(a.size, v)
    return a


def test_insert_into_empty():
    """inserting into an empty array moves nothing"""
    a = FixedArray(4)
    assert a.insert_at(0, "x") == 0
    assert a.items() == ["x"]


def test_insert_at_front_and_middle():
    """inserting at position i moves the size - i items from i onwards"""
    a = filled(10, 20, 30)
    assert a.insert_at(0, 5) == 3
    assert a.items() == [5, 10, 20, 30]
    assert a.insert_at(2, 15) == 2
    assert a.items() == [5, 10, 15, 20, 30]
    assert a.insert_at(5, 35) == 0
    assert a.items() == [5, 10, 15, 20, 30, 35]
    assert len(a.slots) == 8


def test_delete_moves_later_items_left():
    """deleting at position i moves the items after it and clears the freed slot"""
    a = filled(10, 20, 30, 40)
    assert a.delete_at(1) == 2
    assert a.items() == [10, 30, 40]
    assert a.slots[3] is None
    assert a.delete_at(2) == 0
    assert a.delete_at(0) == 1
    assert a.items() == [30]


def test_bad_positions_change_nothing():
    """a position out of range raises IndexError and leaves the array as it was"""
    a = filled(1, 2, 3, capacity=4)
    for call in (lambda: a.insert_at(4, 9), lambda: a.insert_at(-1, 9), lambda: a.delete_at(3), lambda: a.delete_at(-1)):
        try:
            call()
        except IndexError:
            pass
        else:
            raise AssertionError("expected IndexError")
    assert a.items() == [1, 2, 3] and a.size == 3


def test_full_array():
    """inserting into a full array raises OverflowError and changes nothing"""
    a = filled(1, 2, capacity=2)
    try:
        a.insert_at(0, 0)
    except OverflowError:
        pass
    else:
        raise AssertionError("expected OverflowError")
    assert a.items() == [1, 2]


def test_total_moves():
    """building 100 items by inserting at the front moves 4,950 items; deleting from the front moves 4,950 again"""
    a = FixedArray(100)
    assert sum(a.insert_at(0, k) for k in range(100)) == 4950
    assert a.items() == list(range(99, -1, -1))
    assert sum(a.delete_at(0) for _ in range(100)) == 4950
    assert a.size == 0 and a.slots == [None] * 100

/** Up to `capacity` items in an array of slots made once; `size` of them are in use. */
export class FixedArray {
  constructor(capacity) {
    this.slots = new Array(capacity).fill(undefined);
    this.size = 0;
  }

  items() {
    return this.slots.slice(0, this.size);
  }

  /** Puts value at position i (0 <= i <= size); returns how many items moved right. */
  insertAt(i, value) {
    throw new Error('write insertAt');
  }

  /** Removes the item at position i (0 <= i < size); returns how many items moved left. */
  deleteAt(i) {
    throw new Error('write deleteAt');
  }
}

import { test, assert } from 'mysmartcopilot:test';
import { FixedArray } from './fixed_array.mjs';

function filled(values, capacity = 8) {
  const a = new FixedArray(capacity);
  for (const v of values) a.insertAt(a.size, v);
  return a;
}

test('inserting into an empty array moves nothing', () => {
  const a = new FixedArray(4);
  assert.equal(a.insertAt(0, 'x'), 0);
  assert.deepEqual(a.items(), ['x']);
});

test('inserting at position i moves the size - i items from i onwards', () => {
  const a = filled([10, 20, 30]);
  assert.equal(a.insertAt(0, 5), 3);
  assert.deepEqual(a.items(), [5, 10, 20, 30]);
  assert.equal(a.insertAt(2, 15), 2);
  assert.deepEqual(a.items(), [5, 10, 15, 20, 30]);
  assert.equal(a.insertAt(5, 35), 0);
  assert.deepEqual(a.items(), [5, 10, 15, 20, 30, 35]);
  assert.equal(a.slots.length, 8);
});

test('deleting at position i moves the items after it and clears the freed slot', () => {
  const a = filled([10, 20, 30, 40]);
  assert.equal(a.deleteAt(1), 2);
  assert.deepEqual(a.items(), [10, 30, 40]);
  assert.equal(a.slots[3], undefined);
  assert.equal(a.deleteAt(2), 0);
  assert.equal(a.deleteAt(0), 1);
  assert.deepEqual(a.items(), [30]);
});

test('a position out of range throws a RangeError and leaves the array as it was', () => {
  const a = filled([1, 2, 3], 4);
  assert.throws(() => a.insertAt(4, 9), RangeError);
  assert.throws(() => a.insertAt(-1, 9), RangeError);
  assert.throws(() => a.deleteAt(3), RangeError);
  assert.throws(() => a.deleteAt(-1), RangeError);
  assert.deepEqual(a.items(), [1, 2, 3]);
  assert.equal(a.size, 3);
});

test('inserting into a full array throws a RangeError and changes nothing', () => {
  const a = filled([1, 2], 2);
  assert.throws(() => a.insertAt(0, 0), RangeError);
  assert.deepEqual(a.items(), [1, 2]);
});

test('building 100 items by inserting at the front moves 4,950 items; deleting from the front moves 4,950 again', () => {
  const a = new FixedArray(100);
  let moved = 0;
  for (let k = 0; k < 100; k++) moved += a.insertAt(0, k);
  assert.equal(moved, 4950);
  assert.equal(a.items()[0], 99);
  moved = 0;
  for (let k = 0; k < 100; k++) moved += a.deleteAt(0);
  assert.equal(moved, 4950);
  assert.equal(a.size, 0);
  assert.ok(a.slots.every((s) => s === undefined));
});

Interview questions

Why is reading a[i] O(1) in an array but O(i) in a linked list? An array stores its items in one block, every slot the same size, so the address of item i is base + i × w: one multiplication and one addition, whatever i is. A linked list stores each item in a separate node that holds the address of the next node, so the only way to reach item i is to start at the head and follow i links, one memory read each, which is O(i). The difference grows with the position: the millionth item of an array costs what the first costs, while in a linked list it costs a million reads. The list wins elsewhere: once you hold a node, inserting after it changes two links and moves no items.

What is the difference between a Python list and an array.array? A list holds references, 8 bytes each on 64-bit CPython, to objects stored elsewhere, so one list can mix numbers, strings and anything else, and each number is a full object of about 28 to 32 bytes. An array.array holds raw values of one C type in one block, such as 4-byte ints for typecode 'i' or 8-byte integers for 'q': a million numbers take about 8 MB as an array('q') against about 40 MB as a list, and the array refuses a value that does not fit. Both index in O(1) and both pay O(n − i) to insert at position i. Choose an array for large amounts of numbers of one type, and a list for everything else.

Key takeaways

• An array is one block of equal slots, so a[i] sits at base + i × w and any index costs one step: O(1).
• Inserting at position i moves the n − i items from i onwards, and deleting moves the n − i − 1 after it; the front is the worst case, the end the best.
• Python lists, Java’s ArrayList<Integer> and JavaScript’s ordinary arrays hold references or values of any kind; array.array, int[], std::vector<int>, []int32 and Int32Array hold the numbers themselves.
• Python raises IndexError but reads negative indexes from the end; Java throws; Go panics; JavaScript returns undefined or grows the array; C++ operator[] checks nothing, and only tools such as AddressSanitizer or library hardening catch the read.