An array stores a finite sequence of elements, associating each element with an index. Accessing array[1] retrieves the element at position 1, making position-based or random access its defining operation. section 1.1.1
A static array has fixed capacity. Its abstract behavior specifies indexed storage and access, while its concrete implementation places elements in a contiguous memory block. With a known starting address, an element address can be calculated from the base address plus its index. section 1.1.1
Character array
For array = ['C', 'A', 'R'], array[1] is 'A'. The index identifies the position rather than describing the character's value. section 1.1.1
Array performance depends on how the structure is maintained and what operation is required:
- An unsorted array can be created without extra work, append a new entry in amortized O(1) time when capacity remains, and remove an entry in O(1) time. section 4.4.1
- Searching an unsorted array requires scanning entries and therefore takes O(n) time in the dictionary example. section 4.4.1
- Priority queues can use unsorted arrays, sorted arrays, or balanced trees; the choice trades insertion and retrieval costs. section 2.5.1
Figure 1.1 The (simplified) internal representation of an array. Each element of the array in the picture corresponds to a byte of memory,2 whose address is shown below it. Each element’s index is shown above it. An array is stored as a contiguous block of memory, and each element’s address can be obtained by adding its index within the array to the offset of the first element. For instance, the fourth character of the array (array[3], empty in the figure), has address 0xFF00 + 3 = 0xFF03.
Inspect the memory layout to see indices above contiguous elements and addresses derived from the first element's offset. section 1.1.1
Arrays can also provide auxiliary indexing for another structure. In a list-based disjoint-set representation, each array element stores a pointer to a linked-list head; merging sets may then require updating many array entries. section 5.4
