An array stores elements next to one another in memory. An index gives direct access to any element, making arrays useful when a program repeatedly looks up or updates values by position. Their contiguous layout also gives them better cache locality than linked lists. section 1.1 section 1.5
The cost of adding elements depends on the kind of array:
- A fixed-size array cannot simply grow. Adding an element requires allocating a new array and copying the existing elements, an O(n) operation. section 1.1
- A dynamic array reserves extra space. Adding an element is O(1) on average, but an addition that triggers resizing costs O(n). Java ArrayList, C++ std::vector, and Go slices are examples. section 1.1
A linked list makes a different tradeoff: its nodes need not be adjacent, and each carries a pointer. Given a reference to the insertion point, insertion takes O(1); finding that point can take O(n). An array instead offers O(1) indexed access without pointer overhead. Choose according to the operations that matter most, not just whether the collection must grow. section 1.1 section 1.5
A graph stored in an array
An adjacency matrix uses a two-dimensional array: a[i][j] records whether an edge runs from vertex i to vertex j. This makes an edge lookup O(1), but the matrix uses O(V²) space for V vertices—even when the graph has few edges. section 1.3















































