liveBook · Manning

Array

As explained in The Coder Cafe

An array is a collection whose elements occupy contiguous memory locations and are accessed by index.

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

How The Coder Cafe covers it

How deep it goes
Defines contiguous storage and compares fixed-size and dynamic-array operation costs without detailing a resizing implementation.
Examples
Uses Java ArrayList, C++ std::vector, Go slices, and a two-dimensional adjacency matrix.
What it assumes
Introduces arrays and linked lists from their memory layouts while using indexing and O(n) complexity notation.
What you can do after
Evaluate/understand when indexed access favors an array and when growth or graph density changes the tradeoff.
How it connects
Connects arrays to linked lists, cache locality, and graph adjacency matrices.

Also explained in

Compare how 48 books explain array →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.