Fundamental Data Structures

O(1). An array stores elements in contiguous memory, so the address of element i is base + i * elementSize, computed in constant time.

Because all elements after the insertion/deletion point must be shifted by one position to keep the array contiguous, requiring up to n element moves.

A dynamic array is an array that resizes automatically. When full, it allocates a larger buffer (typically doubling capacity) and copies existing elements over.

Amortized O(1). Although a single resize copies n elements, geometric growth spreads the total copy cost so that n pushes cost O(n) overall, i.e. O(1) each on average.

Growing by a constant c each time makes n pushes cost O(n^2) total (each resize copies an ever-larger array). Geometric (multiplicative) growth gives amortized O(1) per push.

A sequence of nodes where each node stores a value and a pointer to the next node. The list is traversed in one direction from head to tail.