Arrays & Dynamic Arrays — Data Structures Course

What you'll learn

The array is the most fundamental data structure — a block of elements laid out back-to-back in memory. That simple layout is what gives arrays their superpower (instant indexing) and their weakness (costly insertion in the middle).

By the end you'll be able to:

Explain why array indexing is O(1)
See why inserting or deleting in the middle is O(n)
Describe how a dynamic array grows, and what "amortized O(1)" means

Contiguous memory & O(1) indexing

An array's elements sit in contiguous memory — one right after another. Because every element is the same size, the computer finds element i with pure arithmetic: address = start + i × element_size. No searching, no matter how big the array — that's why arr[i] is O(1).

Key idea

Random access in constant time is the array's defining strength. The cost is that the block has a fixed position and size in memory — which is exactly what makes inserting in the middle expensive.

Insert & the shifting cost

To insert into the middle (or front), there's no free space — every following element has to shift over by one to make room. Watch inserting 5 at the front of [10, 20, 30]:

Inserting at the front shifts everything

insert(0, 5)

insert 5▼

1/5Insert 5 at index 0. But index 0 is taken — every element must shift right first.

Deleting from the middle is the mirror image — everything after shifts left.

Dynamic arrays & resizing

A raw array has a fixed size. A dynamic array (Python's list, Java's ArrayList, C++'s vector) hides that: when it fills up, it quietly allocates a bigger array — usually double the size — copies everything over, and continues. Step through it:

Growing a dynamic array

Appending past capacity

1/6A dynamic array with 4 items and capacity 4 — it is completely full.

Occasional O(n) copies, spread across many O(1) appends, average out to O(1) per append.

Note

Amortized analysis: a single append is occasionally O(n) (when it copies), but because capacity doubles, those copies get rarer and rarer. Averaged over many appends, each is O(1). We'll prove this properly in Module 30.

Arrays in code

Language

arrays.py

nums = [3, 1, 4, 1]      # a dynamic array (Python list)

print(nums[2])           # O(1) indexing -> 4
nums.append(5)           # amortized O(1) append
nums.insert(0, 9)        # O(n): shifts everything right
print(len(nums))         # 6

Complexity

Operation	Time	Why
`access arr[i]`	O(1)	Direct address arithmetic
`search (unsorted)`	O(n)	May scan every element
`append (end)`	O(1) amortized	Occasional resize copy
`insert / delete (middle)`	O(n)	Must shift the rest
Space	O(n)	One slot per element (plus spare capacity)

Recap & quick check

Key takeaways

Arrays store elements contiguously, so arr[i] is O(1) via address arithmetic.
Inserting or deleting in the middle is O(n) because elements must shift.
Dynamic arrays grow by allocating a bigger array (usually 2×) and copying.
Appending to a dynamic array is amortized O(1) — rare copies averaged over many cheap appends.
Great for indexed access and iteration; poor for frequent middle insertion.

Quick check

1. Why is accessing arr[i] O(1)?

2. Inserting an element at the front of an array of n items is:

3. What does a dynamic array do when it runs out of capacity?

4. Appending to a dynamic array is described as:

Arrays are fast to index but rigid to reshape. Next, the opposite trade-off: Next up: Module 5 — Singly Linked Lists.