Arrays: How They Sit in Memory and Why That Matters

Arrays are the foundation

Almost every data structure you will learn is either an array underneath, or something built to fix a problem arrays have. So it is worth understanding arrays properly rather than treating them as "lists that hold stuff".

An array is a block of memory holding elements of the same size, laid out one after another with no gaps.

That single sentence explains nearly all array behaviour.

The memory picture

Imagine your computer's memory as a very long row of numbered boxes. Each box has an address: 1000, 1001, 1002, and so on.

When you create an array of 5 integers, the computer reserves 5 consecutive slots. If each integer takes 4 bytes and the array starts at address 1000, then:

index:    0      1      2      3      4
address: 1000   1004   1008   1012   1016
value:    88     72     95     61     79

Now the key question: how does the computer find arr[3]?

It does not search. It calculates:

address of arr[i] = start_address + (i * size_of_one_element)
address of arr[3] = 1000 + (3 * 4) = 1012

One multiplication and one addition. The same two operations whether you ask for index 3 or index 3 million.

That is why array indexing is O(1). It is not an optimisation someone added. It falls straight out of the fact that elements are the same size and packed together.

Indexing in practice

marks = [88, 72, 95, 61, 79]

print("First:", marks[0])
print("Fourth:", marks[3])
print("Last:", marks[-1])
print("Length:", len(marks))

marks[2] = 99
print("After changing index 2:", marks)

Every one of those operations is O(1). Reading and writing at a known index cost the same regardless of list size.

Indices start at 0, not 1. That is not an arbitrary annoyance — it comes from the address formula. Index 0 means "zero elements away from the start".

Why insertion and deletion are expensive

Here is the price you pay for that fast indexing. Elements must stay packed with no gaps. So to insert a value in the middle, everything after it has to shift right:

before:  [88, 72, 95, 61, 79]
insert 50 at index 1
step 1:  [88, __, 72, 95, 61, 79]   shift 72, 95, 61, 79 one place right
step 2:  [88, 50, 72, 95, 61, 79]

Inserting at the front of an array with n elements means moving all n elements. That is O(n).

Deletion is the mirror image: remove an element and everything after it shifts left to close the gap. Also O(n).

Inserting or deleting at the end is different — nothing needs to shift, so it is O(1) on average.

nums = [10, 20, 30, 40]

nums.append(50)              # O(1) - add at end
print("After append:", nums)

nums.insert(1, 15)           # O(n) - everything after index 1 shifts right
print("After insert at 1:", nums)

nums.pop()                   # O(1) - remove from end
print("After pop from end:", nums)

nums.pop(0)                  # O(n) - everything shifts left
print("After pop from front:", nums)

print("Contains 30?", 30 in nums)   # O(n) - has to scan

Traversal patterns you will reuse constantly

Most array problems are one of a small number of shapes. Learn these and you will recognise them everywhere.

1. Simple scan. Touch every element once. O(n).

2. Running accumulator. Carry a value (sum, max, count) through the scan.

3. Two pointers. One index from the left, one from the right, moving toward each other. Useful for reversing, checking palindromes, and pair-sum problems in sorted arrays. O(n) instead of the O(n^2) you would get from nested loops.

4. Sliding window. A left and right index defining a stretch of the array that you grow and shrink. Good for "best subarray of length k" style problems.

scores = [45, 82, 67, 91, 38, 74]

# Pattern 1 and 2: scan with accumulators
total = 0
highest = scores[0]
for s in scores:
    total += s
    if s > highest:
        highest = s
print("Total:", total, "| Highest:", highest, "| Average:", total / len(scores))

# Pattern 3: two pointers to reverse in place, O(n) time, O(1) extra space
arr = [1, 2, 3, 4, 5, 6]
left, right = 0, len(arr) - 1
while left < right:
    arr[left], arr[right] = arr[right], arr[left]
    left += 1
    right -= 1
print("Reversed:", arr)

# Pattern 4: sliding window - biggest sum of any 3 consecutive scores
k = 3
window = sum(scores[:k])
best = window
for i in range(k, len(scores)):
    window = window + scores[i] - scores[i - k]
    if window > best:
        best = window
print("Best sum of", k, "consecutive scores:", best)

Notice the sliding window never re-adds the whole window. It adds the new element and subtracts the one leaving. That turns an O(n * k) approach into O(n).

Common array problems worth doing

• Find the largest and second largest element in one pass.
• Reverse an array in place using two pointers.
• Check whether a string or array is a palindrome.
• Move all zeros to the end while keeping the order of other elements.
• Find the missing number in an array containing 1 to n with one number absent.
• Rotate an array left by k positions.
• Find the maximum sum of any k consecutive elements.

Each of these has an obvious O(n^2) solution and a clever O(n) one. Write the obvious one first, get it correct, then look for the improvement. That order matters more than people admit.

Common mistakes

Off-by-one on the last index. For a list of length n the valid indices are 0 to n-1. Writing for i in range(len(arr) + 1) gives IndexError on the final iteration.

Modifying a list while looping over it. Removing items inside a for loop makes the loop skip elements, because the indices shift under you. Build a new list instead, or loop backwards.

Assuming in is cheap. x in my_list is O(n). Inside a loop that becomes O(n^2). If you need repeated membership checks, use a set.

Confusing the index with the value. for i in range(len(arr)) gives you positions; for x in arr gives you values. Mixing them up produces wrong answers rather than errors, which is worse.

Aliasing instead of copying. b = a makes both names point at the same list, so changing b changes a. Use b = a.copy() or b = a[:] when you want an independent copy.

Practice

Try the array exercises on the practice page — start with the two-pointer ones.