Array

An array is a contiguous block of memory holding a fixed-size sequence of equally-sized elements, indexed by position. Python's list is a dynamic array (ArrayList in other languages) — O(1) random access, amortized O(1) append.

1. Complexity

Average				Worst				Space
Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion	Worst
`Θ(1)`	`Θ(n)`	`Θ(n)`	`Θ(n)`	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`

2. How it works

Elements live at consecutive memory addresses, so address(arr[i]) = base + i × element_size — instant access. Search must scan unless the array is sorted (then binary search is O(log n)). Insert/delete in the middle requires shifting all elements after the index, which is O(n).

3. Python implementation

# Python list = dynamic array. O(1) index, O(1) amortized append.
arr = [10, 20, 30, 40]
print(arr[2])         # 30      — O(1) access
arr.append(50)        # O(1) amortized
arr.insert(0, 5)      # O(n)    — shifts everything right
arr.pop(2)            # O(n)    — shifts everything left
print(arr)


# Hand-rolled fixed-size array using ctypes for the contiguous semantics.
import ctypes

class Array:
    def __init__(self, capacity, default=0):
        self._n = capacity
        self._a = (ctypes.py_object * capacity)()
        for i in range(capacity):
            self._a[i] = default
    def __getitem__(self, i):  # O(1)
        return self._a[i]
    def __setitem__(self, i, v):  # O(1)
        self._a[i] = v
    def __len__(self):
        return self._n


a = Array(5)
a[0] = 100
print(a[0])

4. Trade-offs

O(1) random access — the gold standard for index lookup.
Cache-friendly: contiguous memory, sequential reads are fast.
Insert/delete in the middle is O(n) due to shifts; append is amortized O(1).
Fixed element type in low-level languages; Python lists hold heterogeneous references.

5. Memory layout

Because elements are equal-sized and adjacent, the address of any element is a single arithmetic expression, which is the source of O(1) random access. Adjacency also matters for performance beyond Big-O: CPUs fetch memory in cache lines (commonly 64 bytes), so scanning an array sequentially loads several neighbouring elements per fetch, and hardware prefetchers predict the pattern. A linked list with the same asymptotic scan cost is usually much slower in practice because each node may live in a different cache line.

Python's list stores pointers to objects rather than the objects themselves, so the pointer array is contiguous but the values are not. For dense numeric data, array.array or NumPy arrays store raw values contiguously and use far less memory.

6. Insertion shifts and dynamic growth

Inserting at index i requires moving every element after i one slot to the right, which is O(n - i); deleting moves them left. Appending at the end needs no shifting. When a dynamic array runs out of capacity it allocates a larger block (CPython grows by roughly 1.125x plus a constant; many other runtimes double) and copies everything over. That copy is O(n), but it happens rarely enough that the total cost of n appends is O(n), so append is O(1) amortised.

7. Worked example: two-pointer techniques

def remove_duplicates_sorted(a):
    # in-place, O(n) time, O(1) extra space
    if not a:
        return 0
    w = 1
    for r in range(1, len(a)):
        if a[r] != a[w - 1]:
            a[w] = a[r]
            w += 1
    del a[w:]
    return w

def reverse_in_place(a):
    i, j = 0, len(a) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i, j = i + 1, j - 1

nums = [1, 1, 2, 3, 3, 3, 4]
remove_duplicates_sorted(nums); print(nums)  # [1, 2, 3, 4]
reverse_in_place(nums); print(nums)          # [4, 3, 2, 1]

Index arithmetic with a read pointer and a write pointer is the characteristic array technique: it avoids the O(n) cost of repeated insert or pop(i) by compacting in a single pass.

8. Arrays versus other linear structures

Need	Best fit
Index access, iteration, numeric work	Array / Python list / NumPy
Frequent insert/delete at both ends	`collections.deque`
Frequent insert/delete in the middle via a held reference	Doubly linked list
Membership tests	Hash set; or a sorted array with `bisect`

The table hides an important practical point: for small and medium n, arrays often beat structures with better asymptotic bounds. Inserting into the middle of a 1,000-element Python list moves pointers with a single memmove, which is very fast, while walking to the middle of a linked list chases hundreds of scattered pointers. Measure before replacing a list with a linked structure. Sorted arrays combined with binary search (bisect) also give O(log n) lookup with excellent memory density, which is why databases and search engines store sorted runs of keys in arrays inside their pages and segments.

Multi-dimensional arrays add a layout choice. Row-major order (C, NumPy default) stores each row contiguously; column-major order (Fortran, many linear-algebra libraries, and columnar file formats such as Parquet) stores each column contiguously. Iterating along the contiguous dimension is markedly faster, so loops and query engines are written to follow the storage order.

9. Pitfalls

[[0] * 3] * 3 creates three references to the same inner list; use a comprehension for 2-D arrays.
Deleting from a list while iterating over it skips elements; iterate over a copy or build a new list.
x in lst is a linear scan; repeated membership checks on a large list are a common hidden O(n²).

Also watch slicing: a[i:j] copies the slice, so slicing inside a loop (for example recursive binary search written as search(a[mid:])) adds O(n) copying per call. Pass indexes instead, or use memoryview or NumPy views when you need zero-copy windows over the same buffer.

← Back to Algorithms