Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# Dynamic array
A **dynamic array** is a resizable sequence backed by a heap-allocated [[array]]. It provides O(1) indexed access like a fixed array, but grows automatically when capacity is exceeded. When the backing array is full and a new element is appended, the implementation allocates a larger array (typically 2×), copies all elements over, and frees the old allocation. The amortised cost of appending is O(1) because the copying work is spread across all the inserts that preceded the resize.

```c
struct vec {
    int   *data;
    size_t len;
    size_t cap;
};

void push(struct vec *v, int val) {
    if (v->len == v->cap) {
        v->cap  = v->cap ? v->cap * 2 : 4;
        v->data = realloc(v->data, v->cap * sizeof *v->data);
    }
    v->data[v->len++] = val;
}
```

The 2× growth factor keeps the total number of copies linear: each element is copied at most O(log n) times across all resizes, giving O(1) amortised per push. A smaller factor (e.g. 1.5×) wastes less memory at the cost of more frequent copies; a larger factor wastes more memory but copies less often. The standard libraries of most languages use values between 1.5 and 2.

`realloc` in C attempts to extend the allocation in place before copying, which avoids a copy in many cases. Inserting or deleting at a position other than the end shifts subsequent elements and costs O(n).

| Operation | Time |
|---|---|
| Access by index | O(1) |
| Append | O(1) amortised |
| Insert/delete at end | O(1) amortised |
| Insert/delete at middle | O(n) |
| Search (unsorted) | O(n) |