Arrays

The Problem

You store a thousand temperature readings in a list and need the 500th one. You write readings[500] and get the value instantly. The operation looks trivial, but the speed depends on a detail most tutorials skip: how the array sits in memory.

If the data were scattered across arbitrary memory addresses (like a linked list), finding the 500th element would require walking through 499 pointers. The array avoids that by placing every element in a single contiguous block. The address of element i is computed directly — no traversal needed.

What an Array Is

An array is a contiguous block of memory divided into equal-sized slots. Each slot holds one element. The address of element i follows a fixed formula:

The CPU computes this in a single instruction. No traversal, no conditionals.

Example 1 — access by index. Suppose an array starts at memory address 0x1000 and stores 4-byte integers:

Each access jumps directly to the address. There is no "search for the third slot" — the math gives you the exact location. Time: O(1). Space: O(1).

Example 2 — access with negative index. Python allows negative indexing: arr[-1] means "last element." The formula adjusts:

Address = 0x1000 + (6 - 1) × 4 = 0x1014. Same address as arr[5].

Example 3 — out of bounds. If you try arr[10] on a 6-element array, the formula gives 0x1000 + 10 × 4 = 0x1028. That address exists in memory — it just does not belong to your array. In C this is undefined behavior (reads whatever happens to be there). In Python it raises IndexError because the runtime checks the bound before computing.

arr = [10, 20, 30, 40, 50, 60]
print(arr[10])  # IndexError: list index out of range

Insertion and the Cost of Shifting

Inserting an element at an arbitrary position requires shifting every element after that position one slot to the right. The array is contiguous — there is no "splice" operation in hardware.

Example 4 — insert at middle. Insert 99 at index 2 in [10, 20, 30, 40, 50]:

Three elements shifted right. Each shift is a memory copy. For a 10,000-element list, inserting at the front copies all 10,000 elements.

Example 5 — insert at head. Insert 99 at index 0:

Every element shifts one position right. This is the worst case.

Example 6 — insert at tail (append). Insert 99 at index 5 (the end):

Zero shifts. This is the best case and the reason append() is O(1) amortized.

Code: insert_at

def insert_at(arr, index, value):
    for i in range(len(arr) - 1, index, -1):
        arr[i] = arr[i - 1]
    arr[index] = value

Assume arr has capacity for the extra element (the resize step is covered in the next two posts).

Line-by-line walkthrough:

• for i in range(len(arr) - 1, index, -1) — iterate from the last occupied index down to just after the target index. The step -1 means moving backward through the list. The loop excludes index itself because that slot will receive the new value directly.
• arr[i] = arr[i - 1] — copy each element one position to the right. The element at i overwrites the one at i + 1 (which was already shifted in the previous iteration).
• arr[index] = value — the target position is now free because its old occupant was shifted right.

Code trace — insert_at([10, 20, 30, 40, 50, None], 2, 99):

Assume arr has length 6 (capacity 6, size 5). The loop runs backwards from index 5 to 3:

Loop ends at i = 3. Then arr[2] = 99:

Each element from index 2 onward moved right by one. The old value at index 2 (30) is now at index 3.

Time: O(n) — every element after the insertion point shifts. In the worst case (insert at head), all n elements move. Space: O(1) — no extra allocation.

Time: O(n) — every element after the insertion point shifts. In the worst case (insert at head), all n elements move. Space: O(1) — no extra allocation.

Deletion and Shifting Left

Deleting an element shifts everything after it one position left. The same O(n) cost, mirrored.

Example 7 — delete at middle. Delete at index 1 in [10, 20, 30]:

Example 8 — delete at tail. Delete at index 2 (last):

Zero shifts. This is the best case.

Code: delete_at

def delete_at(arr, index):
    removed = arr[index]
    for i in range(index, len(arr) - 1):
        arr[i] = arr[i + 1]
    arr[len(arr) - 1] = None
    return removed

Line-by-line walkthrough:

• removed = arr[index] — save the value before overwriting.
• for i in range(index, len(arr) - 1) — iterate from target index up to second-to-last.
• arr[i] = arr[i + 1] — copy each element one position left.
• arr[len(arr) - 1] = None — the last slot still holds the last element's old value. Clearing it helps garbage collection (and prevents logical errors if the slot is read).

Code trace — delete_at([10, 20, 30, 40, 50, None], 1):

Assume arr has length 6 with size 5. The fifth slot holds 50, the sixth is empty.

Loop ends. Then arr[5] = None (already None). Returns 20.

The three elements after index 1 each shifted one position left. The duplicate 50 at the end was cleaned up by setting the last slot to None.

Time: O(n) — every element after the deletion point shifts left. Space: O(1).

Searching by Value

Searching an unsorted array requires checking every element from left to right until a match is found.

Example 9 — target found. Search for 40 in [10, 80, 30, 40, 50]:

Example 10 — target not found. Search for 99 in the same array:

Code: linear_search

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Line-by-line walkthrough:

• for i in range(len(arr)) — iterate over every valid index from 0 to len(arr) - 1.
• if arr[i] == target — compare the element at the current index with the target.
• return i — the value was found at this index; return immediately.
• return -1 — the loop completed without finding the target.

Code trace — linear_search([10, 80, 30, 40, 50], 40):

Two more iterations than binary search would need (binary search finds it in at most 3 comparisons for 5 elements, but requires sorted input).

Time: O(n) — every element compared in the worst case. Space: O(1).

Why Arrays Are Cache-Friendly

When you access arr[0], the CPU loads a cache line — typically 64 bytes — that contains arr[0] through arr[15] (for 4-byte integers). Accessing arr[1] immediately after hits the cache instead of main memory. For linked lists, each node could be anywhere in memory; every access is a potential cache miss.

This is why arrays often outperform linked lists for sequential traversal, even though both are O(n). The constants differ by an order of magnitude.

Closing

The array is the data structure every other structure is compared against. Its strength — O(1) random access via a cheap address computation — comes from contiguous memory. Its weakness — O(n) insert and delete — comes from the same contiguity. Every element that moves costs a copy.

Understanding this tradeoff at the memory level is what separates knowing arr[i] works from knowing why it works and when it does not.