Contiguous Memory and Array Indexing: O(1)

After This Topic

You will be able to mathematically explain why arrays have O(1) index access, understand the advantages and disadvantages of contiguous memory, and grasp the performance differences between arrays and linked lists.

Why are Arrays Fast?

numbers = [10, 20, 30, 40, 50]
print(numbers[3])  # 40 — Instant access!

Whether it's 5 elements or 5 million, the time to access an element by index is always the same. This is O(1) — constant time access.

Why is this possible? Because arrays are stored contiguously in memory.

Contiguous Memory: The Secret of Arrays

Memory Address:  1000  1004  1008  1012  1016
Value:          [10]  [20]  [30]  [40]  [50]
Index:          0     1     2     3     4

Each element of the array is stored right next to each other in memory. If each integer occupies 4 bytes:

• numbers[0] → Address 1000
• numbers[1] → Address 1004
• numbers[2] → Address 1008
• numbers[3] → Address 1012

Indexing Formula

Element Address = Starting Address + (Index × Element Size)

numbers[3] = 1000 + (3 × 4) = 1012

This calculation involves one addition and one multiplication. It doesn't matter if the array has 5 elements or 5 billion elements. Therefore, it's O(1).

Comparison with Linked Lists

In a linked list, each node stores the address of the next node. The nodes are scattered in memory.

Memory:  [10|→1500]  ...  [20|→2300]  ...  [30|→1800]  ...  [40|→2100]

To find the 3rd element:
  Node 0 (1000) → Follow the pointer
  Node 1 (1500) → Follow the pointer
  Node 2 (2300) → Follow the pointer
  Node 3 (1800) ← Here!

To find the 3rd element, you have to traverse from the 0th element. To find the nth element, you have to traverse n times → O(n).

The Reality of Python Lists

Python's list is different from a C array. It's an array of pointers.

Python list:  [ptr0][ptr1][ptr2][ptr3]
                ↓     ↓     ↓     ↓
              [10]  ["hi"] [3.14] [[1,2]]

Pointers (addresses) have a fixed size (8 bytes on a 64-bit system), so the pointer array itself is stored in contiguous memory. The indexing formula still applies, making it O(1).

# Python list — Can store different types (because it's an array of pointers)
mixed = [42, "hello", 3.14, [1, 2, 3]]
print(mixed[2])  # 3.14 — O(1)

However, the actual data is scattered throughout memory, so it's less cache-efficient than a C array.

NumPy Arrays: True Contiguous Memory

import numpy as np

# NumPy stores data contiguously, like a C array
arr = np.array([1, 2, 3, 4, 5], dtype=np.int32)
# Memory: [00000001 00000002 00000003 00000004 00000005]
#         4 bytes each, stored contiguously

One of the reasons NumPy is tens of times faster than Python lists is this contiguous memory layout.

Cache Friendliness

When the CPU retrieves data from memory, it also loads the data around the requested address into the cache line (usually 64 bytes).

Sequential array access:
  Access arr[0] → Loads arr[0]~arr[15] into the cache
  Access arr[1] → Cache hit! (Already loaded)
  Access arr[2] → Cache hit!
  ...

Linked list access:
  Access node0 → Loads surrounding data into the cache
  Access node1 → Different address! Cache miss → Re-loads from memory
  Access node2 → Another different address! Cache miss
  ...

Arrays have a high cache hit rate because they are contiguous, while linked lists have frequent cache misses because they are scattered. In modern CPUs, a cache miss is more than 100 times slower than a cache hit.

Limitations of Arrays: Insertion and Deletion

Insertion in the middle of an array (insert 25 at index 2):

Before: [10][20][30][40][50]
                 ↓
Step 1: [10][20][  ][30][40][50]  ← Shift 30, 40, 50 one position to the right
Step 2: [10][20][25][30][40][50]  ← Insert 25 into the empty space

All the elements after the insertion point must be moved, resulting in O(n). Deletion is the same — you have to move the elements forward to fill the empty space.

Memory Layout of 2D Arrays

Row-major (C, Python, NumPy default):
[[1, 2, 3],     Memory: [1][2][3][4][5][6]
 [4, 5, 6]]     → Stored in row order

Column-major (Fortran, MATLAB):
[[1, 2, 3],     Memory: [1][4][2][5][3][6]
 [4, 5, 6]]     → Stored in column order

import numpy as np

arr = np.array([[1, 2, 3], [4, 5, 6]])

# C order (row-major, default)
print(arr.flags['C_CONTIGUOUS'])  # True

# Fortran order
arr_f = np.asfortranarray(arr)
print(arr_f.flags['F_CONTIGUOUS'])  # True

If you have many row-wise traversals, Row-major is more cache-efficient. If you have many column-wise traversals, Column-major is more cache-efficient. NumPy uses C order (Row-major) by default. This is why row-wise operations (axis=1) are often faster than column-wise operations (axis=0) — because the memory access pattern is more cache-friendly.

Dynamic Arrays: Arrays that Grow

Arrays have a fixed size. Python lists are dynamic arrays, which allocate and copy a larger array when they are full.

import sys

items = []
prev_size = 0
for i in range(20):
    items.append(i)
    size = sys.getsizeof(items)
    if size != prev_size:
        print(f"len={len(items):2d}, capacity changed: {prev_size} → {size} bytes")
        prev_size = size

# len= 1, capacity changed: 56 → 88 bytes
# len= 5, capacity changed: 88 → 120 bytes
# len= 9, capacity changed: 120 → 184 bytes
# len=17, capacity changed: 184 → 248 bytes

Python typically allocates space that is 1.125 times the current size plus a constant. If it allocated one element at a time, it would have to copy everything every time (O(n)). However, by allocating in multiples, it achieves amortized O(1).

Key Takeaways

The reason arrays are O(1) is the simple mathematics of "contiguous memory + one multiplication." Understanding this principle naturally connects to why NumPy is faster than Python lists, why databases use indexes, and why cache optimization is important.

In practice: If you need a lot of index access, use an array. If you need a lot of insertions/deletions, use a linked list. Python lists are suitable for most cases, but if you're doing numerical calculations, using NumPy is tens of times faster — because it uses true contiguous memory.