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.
# Array
An **array** is a fixed-size sequence of elements of the same type stored in contiguous memory.

The index of an element determines its address: `base + index * sizeof(element)`. This means any element is reachable in O(1) time without traversal, and the memory layout is cache-friendly — iterating over an array touches sequential cache lines rather than chasing pointers.

```c
int a[8] = {10, 20, 30, 40, 50, 60, 70, 80};

a[0]  // 10 — first element
a[7]  // 80 — last element
a[8]  // undefined behaviour — out of bounds
```

Arrays are the foundation of nearly every other data structure. A [[stack]], [[queue]], and [[circular-buffer]] can all be implemented over a fixed array. A [[matrix]] is a 2D array with an index formula that maps row and column to a flat offset. The trade-off is the fixed size: the capacity must be known at allocation time. When the required size is not known in advance, a [[dynamic-array]] grows the backing array as needed.

| Operation | Time |
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Search (sorted, binary search) | O(log n) |
| Insert/delete at end | O(1) |
| Insert/delete at middle | O(n) — elements must shift |