Picture an Advent calendar: each numbered drawer has a treat, and its number tells you which drawer to open. An array works much the same way. It stores a sequence of elements and lets you reach an element by its position, or index. Unlike a set of separately named variables, it also lets a program choose a position while it runs. section 2.2 section 2.3
A static array has a fixed capacity. In a common language-level implementation, its equally sized elements sit side by side in one block of memory; this makes it possible to compute an element’s location and access it directly. Python-style indexes start at 0, so an array of size n ends at index n−1. Check the bounds: index n is not another drawer. section 2.3 section 2.4
For an unsorted array, the important question is whether the order of its entries matters:
- If you fill it gradually, put each new entry in the first unused position and track how many positions hold meaningful data. Allocated capacity and the number of entries in use are different things. section 2.9
- To find an entry by its value, traverse the array until you encounter it. An index gives direct access to a position; it does not tell you which position contains a particular value. section 2.19 section 2.3
- To remove a middle entry without preserving order, replace it with the last meaningful entry and decrease the tracked size. If order matters, moving later entries to close the gap takes more work. section 2.12
Swapping the entry to be removed with the rightmost one in the array, and then deleting it
The diagram shows why an unsorted array can remove a middle entry by replacing it with the rightmost entry, rather than shifting every later entry. section 2.12
Count dice rolls
Make six counters, initially all zero. When a roll shows k, increment counters[k-1]: a roll of 4 updates counters[3]. After many rolls, traverse the counters to find the largest and smallest counts. Here every position is meaningful from the start, so there is no need to track a gradually filled portion. section 2.16
Fixed capacity is convenient when the number of positions is known, but awkward when a collection must grow. A dynamic array adds resizing by replacing its underlying fixed-size array when needed. Arrays can also back a fixed-capacity queue: they use less memory than linked lists for the same elements, though managing a circular queue takes more code. Choose based on the operations and capacity you need, not just the container’s name. section 5.19 section 9.9
“Array” can describe several levels of detail. At the abstract level, it is an ordered collection accessible by index. A data-structure definition can additionally require constant-time indexed access; a language-level implementation can specify contiguous memory and equally sized, same-type elements. Keep these levels separate when comparing arrays with linked lists. section 7.3
