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.

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)`

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).

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])

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.

← Back to Algorithms