# Arrays, Dynamic Arrays and Linked Lists — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/d-linear

> Know the cost of common operations on arrays and linked lists.

## Where elements live determines the cost

An **array** stores elements contiguously, so **indexing** `a[i]` is **O(1)**: the address is computed directly. **Inserting or deleting in the middle** is **O(n)**, because later elements must shift. A **dynamic array** (Python `list`, Java `ArrayList`, C++ `vector`) appends at the end in **amortised O(1)** time: occasionally it must allocate a larger block and copy everything, but by growing geometrically (for example doubling) the copying averages out to a constant per append. Inserting or removing at the **front** is O(n). A **linked list** stores nodes connected by pointers: inserting or deleting **at a known node** is O(1), but **finding** the i-th element or a value is O(n), and its poor memory locality makes it slower in practice than arrays for most workloads. A **deque** (double-ended queue, such as Python's `collections.deque`) supports O(1) appends and pops at **both** ends, making it the right choice for queues.

## Contiguous versus linked storage

Arrays sit in one block of memory; linked lists scatter nodes connected by pointers.

![Top: a row of adjacent equal boxes. Bottom: boxes scattered at different heights connected by curved arrows.](assets/figures/big-o/section-6-map.svg) — Figure 6.1 — Array layout compared with a linked list.

## Costs of common sequence operations (typical implementations)

Big-O for Python list, deque and a singly linked list.

```text
operation                     Python list   collections.deque   singly linked list
----------------------------  ------------  ------------------  ------------------
index a[i]                    O(1)          O(n)*               O(n)
append at end                 O(1) amort.   O(1)                O(1) with tail ptr
pop from end                  O(1)          O(1)                O(n) (need prev)
insert / pop at front         O(n)          O(1)                O(1)
insert in middle (by index)   O(n)          O(n)                O(n) to find + O(1)
search by value (x in s)      O(n)          O(n)                O(n)

* deque indexing is O(1) near the ends and O(n) towards the middle
```

## list.pop(0) in a loop is quadratic

Using a Python list as a queue with `pop(0)` shifts every remaining element each time, so processing n items costs O(n²). Use `collections.deque` and `popleft()` for O(n) total.

**Quiz:** What is the amortised cost of appending to a dynamic array that doubles its capacity when full?

- [ ] O(n)
- [ ] O(log n)
- [x] O(1)
- [ ] O(n²)

*Answer:* O(1). Occasional O(n) copies average out to a constant per append because capacity grows geometrically.