Trace an Array Insertion

You have a dynamic array of 5 integers at full capacity: [10, 20, 30, 40, 50]. You want to insert the value 35 at index 2.

1. Check capacity — array is full, trigger resize

The array holds 5 elements in a 5-slot block. Before inserting, the dynamic array must allocate a new block and copy existing elements. Most dynamic arrays double the capacity, so it allocates 10 slots.

2. Allocate a new block of 10 slots

A new contiguous block of memory is allocated — 10 × 4 bytes = 40 bytes. The old 5-element block and the new 10-element block coexist temporarily.

3. Copy 5 existing elements into the new block

The five existing values are copied: 10 → index 0, 20 → index 1, 30 → index 2, 40 → index 3, 50 → index 4.

4. Shift 30 from index 2 to index 3

To make room at index 2, every element from index 2 onward must shift one position to the right. Move 30 from index 2 to index 3.

5. Shift 40 from index 3 to index 4

Move 40 from index 3 to index 4.

6. Shift 50 from index 4 to index 5

Move 50 from index 4 to index 5. Three elements have been shifted.

7. Write 35 at index 2

All elements have shifted right. Write 35 at index 2. The array now reads [10, 20, 35, 30, 40, 50].

Why This Matters

One resize (5→10, O(n) copy) plus three element shifts. The resize happens rarely (capacity doubles each time), so it is amortized O(1). But the shift happens on every middle insertion: inserting at index k shifts n − k elements. This is why inserting into the middle of an array is O(n).

See how a linked list avoids shifting — it only needs to update two pointers.