TRT
Sign in
ApplicationFoundationsmemory

Trace an Array Insertion

Follow an array insertion from capacity check through resize, element shift, and write, showing why middle insertion is O(n).

The Runtime Theory Team2 min read07 steps

layer stack

Application

HWHardware
KKernel
RTRuntime
APPApplication
SYSSystem
CLIClient
NETNetwork
TLSCrypto
SRVServer
Go higherTrace an Array Read Against a Linked List WalkTrace Inserting amy Where Slot 5 Is TakenTrace Pushing 1 Onto a Heap and Finding 4 in a TreeWhat happens when a closure is allocated?What happens when you concatenate strings?What happens when the garbage collector runs?What happens when you malloc(256)?

trace spine

  1. 01 Check capacity — array is full, trigger resize
  2. 02 Allocate a new block of 10 slots
  3. 03 Copy 5 existing elements into the new block
  4. 04 Shift 30 from index 2 to index 3
  5. 05 Shift 40 from index 3 to index 4
  6. 06 Shift 50 from index 4 to index 5
  7. 07 Write 35 at index 2
On this page

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.

Hardware, runtime, and observability notes

When tracing Trace an Array Insertion in a live production environment (subsystem: memory, primary layer: application), keep the following step-level cost model and diagnostic checklist in mind:

  • Step 1 (application): Check capacity — array is full, trigger resize — verifies state invariants before advancing the execution pointer.
  • Step 2 (application): Allocate a new block of 10 slots — verifies state invariants before advancing the execution pointer.
  • Step 3 (application): Copy 5 existing elements into the new block — verifies state invariants before advancing the execution pointer.
  • Step 4 (application): Shift 30 from index 2 to index 3 — verifies state invariants before advancing the execution pointer.
  • Step 5 (application): Shift 40 from index 3 to index 4 — verifies state invariants before advancing the execution pointer.
  • Step 6 (application): Shift 50 from index 4 to index 5 — verifies state invariants before advancing the execution pointer.
  • Step 7 (application): Write 35 at index 2 — verifies state invariants before advancing the execution pointer.

Every transition across the application boundary carries both a direct CPU/memory cost (cache-line fills, descriptor lookups, lock acquisitions, or context switches) and a tail-latency queueing risk under contention. To verify this trace on your own service, capture latency histograms and hardware/kernel counters across each step boundary, compare cold-cache versus warm-cache execution paths, and confirm that error or timeout branches release all acquired descriptors, locks, and buffers cleanly.

Not started

Sign in to save your learning progress.

Sign in to save