Dynamic array
The default sequence: indexed reads and appends at the end.
| Time | Index O(1); append O(1) amortized; insert or delete in the middle O(n) |
|---|---|
| Space | O(n) |
Why it costs this much
When the array is full, capacity grows by a constant factor (often 1.5× or 2×), so a full copy of n items happens only after a number of cheap appends proportional to n. Spread across those appends, the cost is O(1) each.
Code
items = []
for x in range(n):
items.append(x) # usually O(1); occasionally copies the whole list
items[0] # O(1): direct index
items.insert(0, -1) # O(n): shifts every element rightPython is the baseline example used across the site.
Common pitfalls
Inserting or deleting near the front shifts every later item, which is O(n). A single append can still cost O(n) when it triggers a resize.
Operation by operation
| Operation | Best | Average | Worst | Space |
|---|---|---|---|---|
| Array index (read or write) | O(1) | O(1) | O(1) | O(1) |
| Dynamic array append | O(1) | O(1) amortized | O(n) on a resize | O(1) amortized extra |
| Dynamic array insert or delete in the middle | O(1) at the end | O(n) | O(n) | O(1) |
Array index (read or write). Random access into contiguous memory. Linked lists have no O(1) index. Reaching position k takes O(k).
Dynamic array append. Capacity grows by a constant factor, such as 1.5× or 2×. A single append can copy the whole array. Growing by a fixed amount instead of a factor makes appends O(n) amortized.
Dynamic array insert or delete in the middle. Elements after the position shift by one. Inserting at the front is the worst position. A deque or linked list is better for front operations.