Data Structures · Lesson 2 of 8

Arrays

Contiguous memory, index access, and resize costs.

• Beginner
• 12 min read
• 3 objectives

Before this lessonLesson 1: What Are Data Structures?

An array stores elements one after another in a single block of memory. Because every element takes the same amount of space, the computer can calculate the address of element i directly: start address plus i times the element size. That is why reading arr[i] takes the same tiny amount of time whether the array has ten items or ten million.

The simplest structure: numbered slots

An array is a row of equal-sized boxes stored side by side in memory, each with a number starting at 0. Because the boxes are neighbours and the same size, the computer can jump to box 500 by simple arithmetic (start address plus 500 times the box size) without visiting boxes 0 to 499. That is why reading arr[i] is instant, no matter how big the array is.

What is fast and what is slow

• Read or write by index: O(1).
• Append at the end: O(1) on average.
• Insert or delete in the middle or front: O(n), because everything after it must shift.
• Search for a value in an unsorted array: O(n), since you may check every element.

nums = [10, 20, 30, 40]
print(nums[2])        # O(1) access
nums.append(50)       # O(1) amortized
nums.insert(1, 15)    # O(n) shifts 20, 30, 40, 50
print(nums)

30
[10, 15, 20, 30, 40, 50]

Fixed versus dynamic arrays

In C or Java a plain array has a fixed length. Python lists, Java's ArrayList and JavaScript arrays are dynamic arrays: when they run out of room they allocate a bigger block (usually double), copy everything over and continue. Each resize is O(n), but they are rare, so appends average out to O(1).

Why arrays are fast in practice

Contiguous memory is friendly to the CPU cache. When you read one element, its neighbors come along for free, so scanning an array is often faster than scanning a linked list even when the Big O is the same.

A classic technique: two pointers

Many array problems can be solved with two indexes that move toward each other, avoiding nested loops. Reversing an array in place is the simplest example.

def reverse(a):
    left, right = 0, len(a) - 1
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1
        right -= 1

vals = [1, 2, 3, 4, 5]
reverse(vals)
print(vals)

[5, 4, 3, 2, 1]

This runs in O(n) time and O(1) extra space, because it swaps in place instead of building a second array.

What is cheap and what is costly

nums = [10, 20, 30, 40, 50]

print(nums[3])        # read by index: instant
nums.append(60)       # add at the end: cheap
nums.insert(0, 5)     # add at the front: every item must shift right
print(nums)
nums.pop(0)           # remove from the front: every item shifts left
print(nums)

40
[5, 10, 20, 30, 40, 50, 60]
[10, 20, 30, 40, 50, 60]

Adding at the end is cheap because nothing has to move. Adding or removing at the front is costly because every other item shifts one place, which is O(n) work. Remember this whenever you use a list as a queue.

Worked example: reverse in place

Two markers, one at each end, swap and move inward. No extra list is needed.

def reverse(items):
    left, right = 0, len(items) - 1
    while left < right:
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1

data = [1, 2, 3, 4, 5]
reverse(data)
print(data)

[5, 4, 3, 2, 1]

Worked example: running maximum

temps = [18, 21, 19, 25, 23, 30, 28]
best = temps[0]
for t in temps[1:]:
    if t > best:
        best = t
print("highest:", best)

highest: 30

Common array mistakes

• Off-by-one: valid indexes are 0 to len - 1.
• Modifying a list while looping over it, which skips items. Loop over a copy or build a new list.
• Assuming an empty list has a first item; check if items: first.

Key takeaways

• Arrays give instant access by index because items sit side by side in memory.
• Appending at the end is cheap; inserting or removing at the front shifts everything.
• Two-pointer techniques process an array in one pass without extra memory.

# Write your solution here