An array is an ordered collection of values stored in contiguous memory, where every element can be accessed in O(1) time by its integer index, computed as base_address + (index * element_size).
The fundamental sequential data structure
What you'll learn: What an array is (contiguous memory, indexed access), zero-based indexing (why arrays start at 0), and the difference between static arrays (fixed size) and dynamic arrays (grow automatically).
How to read this tab: Python's list is a dynamic array. The concepts here explain what's happening under the hood when you use a list.
An array is a numbered list where every slot has a fixed address — slot 0, slot 1, slot 2 — and you can jump to any slot instantly, no matter how long the list.
An array is contiguous memory — elements stored one after another. Because they're contiguous, accessing any element is O(1): address = start + (index × element_size). This is the fundamental advantage of arrays over other data structures. Python's list achieves this by storing references (pointers) contiguously, even though the objects themselves may be scattered in memory.
What an array is
An array is an ordered collection of values stored in a contiguous block of memory. Every element has an index — a number starting at 0. To find any element: compute base_address + index * element_size. One arithmetic operation, regardless of array length. This is why random access is O(1).
fruits = ["mango", "apple", "banana"]
print(fruits[0]) # "mango"
print(fruits[-1]) # "banana" (negative index from end)
print(fruits[0:2]) # ["mango", "apple"] — slice: copy of subset
fruits.append("guava") # O(1) amortised
fruits.insert(1, "pear") # O(n) — shifts elements rightIndexing starts at 0 because of pointer arithmetic. In C, array[i] means *(array + i*size) — the offset from the start. The first element is at offset 0. If arrays started at 1, every access would require an extra subtraction. Most languages (Python, C, Java, JavaScript) use 0-based indexing for this reason. MATLAB and R start at 1 — their historical context is mathematics, not systems programming.
Zero-based indexing
Arrays start at index 0 in C, Java, Python, JavaScript, Go, and Rust. The address calculation explains why: 0 bytes from the start is the first element. Lua, MATLAB, R, and Fortran use 1-based indexing by language convention.
Python lists are dynamic — they grow automatically. When you append to a list and it runs out of space, Python allocates a new larger block of memory, copies everything over, and discards the old block. This is called resizing. To avoid resizing on every append, Python allocates extra space in advance (over-allocation). The resizing strategy is to double the allocated size, which gives amortised O(1) append.
Static vs. dynamic arrays
A static array has a fixed size set at creation. C arrays, Java primitive arrays. A dynamic array (Python list, JavaScript Array, Rust Vec) can grow. It allocates extra capacity and copies to a larger allocation when full — giving O(1) amortised append.
C: int arr[5] = {1, 2, 3, 4, 5}; // static, fixed size
Java: int[] arr = {1, 2, 3, 4, 5}; // static; use ArrayList for dynamic
Python: arr = [1, 2, 3, 4, 5] # dynamic list
JavaScript: arr = [1, 2, 3, 4, 5] # dynamic array
Rust: let arr = [1, 2, 3, 4, 5]; // static; use Vec for dynamic
Go: arr := [5]int{1, 2, 3, 4, 5} // static; use slice for dynamic✅ Beginner tab complete — check your understanding
- I know what zero-based indexing is and why it exists
- I know the difference between a static array (fixed size) and a dynamic array (grows automatically)
- I know Python lists are dynamic arrays — they grow automatically as you append
O(1) access, amortised O(1) append, and NumPy
What you'll learn: Why array access is O(1) (memory address arithmetic). How dynamic arrays achieve amortised O(1) append (doubling strategy). NumPy's typed arrays and why vectorised operations are so much faster.
How to read this tab: The amortised analysis section explains why Python list.append() is O(1) on average even though it occasionally copies the whole array. This is a fundamental computer science concept that appears in interviews.
O(1) access is the reason to choose arrays over other structures. Given the start address and an index, the CPU computes the element's address in one multiplication and one addition — regardless of array size. This is why looking up an element by index is equally fast whether the array has 10 or 10 million elements. Contrast with a linked list, where reaching element 1000 requires following 1000 pointers.
Memory layout and O(1) access
Array element at index i is at address B + i*s where B is the base address and s is element size. One multiply and one add — constant regardless of n. A linked list requires i pointer dereferences to reach element i — O(n). For sequential access, arrays are 5–50× faster than linked lists due to CPU cache: a 64-byte cache line holds 16 integers, prefetching subsequent elements automatically.
The doubling trick makes append O(1) on average. When the array is full, allocate twice the space and copy everything. This copy costs O(n) — but it happens rarely. If you append n items, the total copies are n/2 + n/4 + n/8 + ... = n (geometric series). n copies spread over n operations = O(1) per operation on average. This is amortised O(1) — the average cost over many operations.
Dynamic arrays: amortised analysis
When capacity is exceeded, the array doubles in size and copies all elements — O(n). But this happens so infrequently that the amortised cost per append is O(1). Over n appends, total copy work is n + n/2 + n/4 + ⋯ = O(n), so O(1) average per operation.
| Operation | Static array | Dynamic array |
|---|---|---|
| Access by index | O(1) | O(1) |
| Append to end | N/A | O(1) amortised |
| Insert at index i | N/A | O(n) |
| Delete at index i | N/A | O(n) |
| Search (unsorted) | O(n) | O(n) |
| Search (sorted) | O(log n) | O(log n) |
NumPy arrays store typed data contiguously — like C arrays. A NumPy array of floats stores raw float bytes side by side. Operations on the array are implemented in C and applied to all elements at once (vectorisation). This is why np.array([1,2,3]) * 2 is ~100x faster than [x*2 for x in [1,2,3]] at scale — no Python loop, no Python objects, just C operating on contiguous memory.
NumPy and vectorised operations
NumPy arrays store typed values directly (not Python object references), laid out contiguously in memory. This enables SIMD vectorisation — a single CPU instruction operates on 4, 8, or 16 elements at once. arr * 2 on a NumPy array of 1 million elements is ~100× faster than a Python loop.
a[1:3] returns a new list. NumPy slices return a view — modifying the slice modifies the original.✅ Intermediate tab complete — check your understanding
- I can explain why array access is O(1): start_address + index * element_size
- I know that list.append() is amortised O(1) because the list doubles in size when full
- I know why NumPy arrays are faster than Python lists for numerical operations
Pointer arithmetic, ISO C17, and cache performance
What you'll learn: Pointer arithmetic in C as the basis for array indexing. C17's rules on undefined behaviour with arrays. Why arrays outperform linked lists in practice (cache locality).
How to read this tab: Read when studying C, systems programming, or when optimising Python with C extensions.
In C, arrays and pointers are deeply connected. array[i] is syntactic sugar for *(array + i) — dereference the pointer at offset i. This is why you can iterate a C array with a pointer: for (int *p = array; p < array + n; p++). ISO C17 specifies that pointer arithmetic outside array bounds is undefined behaviour — accessing array[-1] or array[n] is not guaranteed to do anything predictable.
Pointer arithmetic and ISO C17
ISO C17 §6.5.6: adding integer n to pointer p advances it by n × sizeof(*p) bytes. Array indexing a[i] is defined as *(a + i). The array name decays to a pointer to its first element in most contexts. Accessing a[n] where n ≥ size is undefined behaviour — the compiler may assume UB never occurs and produce semantically incorrect optimisations if it does (GCC -O2 will eliminate bounds checks it proves can't be reached).
Cache performance: arrays vs. linked structures
An L1 cache hit costs ~1 ns; an L1 miss costs ~60 ns. Arrays are cache-friendly: iterating fills cache lines sequentially. Linked list nodes are scattered across the heap — each traversal step likely causes a cache miss. For n = 10 million, array traversal typically runs in < 10 ms; linked list traversal takes > 1 second on modern hardware, despite both being O(n) algorithmically.
ISO C17 §6.5.6 — Additive operators. Python Language Reference §3.3.6 — Sequence types. Java Language Specification §10 — Arrays. NumPy internals: numpy.org/doc/stable/reference/arrays.ndarray.html.
✅ Expert tab complete
- I know that pointer arithmetic is how C implements array indexing at the CPU level
- I can explain cache locality and why arrays are faster than linked lists for sequential access