02 Arrays and Dynamic Arrays

The array model and indexed access

An array stores an ordered sequence of elements, and each element is identified by an integer index. In zero-based indexing, the first element is at index $0$, the second is at index $1$, and an array of length $n$ ends at index $n-1$.

For an array $A = [17, 4, 29, 8]$, the value at $A[2]$ is $29$. The index $2$ identifies a position; it is not the same thing as the value stored there. Index $4$ is outside the valid range of this four-element array.

In a conventional array, elements of the same type occupy adjacent memory locations. If the first element begins at address $B$, each element uses $w$ bytes, and the requested index is $i$, then the address is:

Because this calculation does not depend on the array's length, reading or updating a known index typically takes $O(1)$ time. Searching for an unknown value is different: the program may need to inspect up to $n$ elements, so a linear search can take $O(n)$ time.

Takeaway: Arrays provide fast positional access because an index can be converted directly into a memory address.

Traversal and basic array algorithms

Traversal visits elements one after another, commonly from index $0$ through index $n-1$. It supports tasks such as printing values, computing a total, finding a maximum, validating data, or applying the same operation to every element.

A running-total traversal can be described as follows:

• Set a total to $0$.

• For each valid index $i$, add $A[i]$ to the total.

• Return the total after the final element.

A traversal of $n$ elements takes $O(n)$ time. If the algorithm stores only a running total and a loop index, its additional space usage is $O(1)$.

Takeaway: Visiting every element is linear in the number of elements, even though accessing each individual element is constant time.

Insertion, deletion, and shifting

Insertion preserves the order of existing elements by making room for a new value. To insert at index $i$, elements from the end toward index $i$ must move one position to the right. Moving from right to left prevents a value from being overwritten before it is copied.

For example, inserting $25$ at index $2$ changes $[10, 20, 30, 40]$ to $[10, 20, 25, 30, 40]$. The values $30$ and $40$ shift right. Inserting at the beginning or middle can require moving $O(n)$ elements, so the worst-case time is $O(n)$. Appending at the end is $O(1)$ when unused capacity is available.

Deletion removes an element and closes the gap by shifting later elements one position to the left. Deleting index $1$ from $[10, 20, 30, 40]$ produces $[10, 30, 40]$. Deleting from the beginning or middle can take $O(n)$, while deleting the final element takes $O(1)$ because no other element must move.

Takeaway: Arrays are efficient for access and end operations, but insertions and deletions near the beginning or middle are expensive because of shifting.

Fixed storage and dynamic growth

A fixed-length array has storage determined at creation time. It is appropriate when the required number of elements is known and stable, such as a fixed-size lookup table. Its predictable storage can be useful when memory requirements must remain stable.

A dynamic array uses an ordinary array as backing storage while tracking two quantities. Size is the number of elements currently stored. Capacity is the number of elements that fit in the allocated storage. For example, a dynamic array can have size $4$ and capacity $8$: four slots contain logical elements and four slots remain available for future appends.

When a dynamic array becomes full, it generally allocates a larger backing array, copies the existing elements, replaces the old backing array, and then inserts the new element. A common policy multiplies capacity by a constant factor, such as $2$, but the exact growth policy depends on the implementation.

Takeaway: Fixed-length arrays prioritize stable, predetermined storage; dynamic arrays trade some extra capacity for the ability to grow.

Amortized cost of appending

An append to a dynamic array normally takes $O(1)$ time when capacity is available. During a resize, copying the existing $n$ elements takes $O(n)$ time, so one particular append can be expensive.

Amortized analysis explains why the long-run cost remains small. If capacity grows geometrically, resizes occur less frequently as the structure becomes larger. Across many appends, the total copying work is proportional to the total number of inserted elements, so the average cost per append is amortized $O(1)$.

The main trade-off is memory: unused capacity improves future append performance but can occupy more storage than the current size. Implementations may offer operations such as ensureCapacity to reserve space or trimToSize to reduce unused capacity.

For the broader operation profile:

• Indexed access and indexed update are typically $O(1)$.

• Traversal takes $O(n)$.

• Insertion or deletion at the beginning or middle takes $O(n)$.

• Appending is amortized $O(1)$, but worst-case $O(n)$ during a resize.

Takeaway: Amortized performance describes the sequence-level cost, not the cost of every individual append.

Multidimensional arrays and matrix layout

A multidimensional array uses more than one index. A two-dimensional array can represent rows and columns, for example:

With zero-based indexing, $M[1][2] = 6$: row $1$, column $2$. Traversing a rectangular matrix uses nested loops. If the matrix has $r$ rows and $c$ columns, visiting every element takes $O(r \times c)$ time.

A rectangular matrix can also be flattened into one one-dimensional array. With $c$ columns, the row-major mapping is:

For row $1$, column $2$ in a matrix with $3$ columns, the flat index is $1 \times 3 + 2 = 5$. Nested arrays can be easier to read and can support rows of different lengths, sometimes called a jagged array. Flat storage makes the layout explicit and can improve memory locality.

Takeaway: Choose nested or flat multidimensional storage according to whether readability, variable row lengths, or a compact layout matters most.

Choosing an array-based structure

Arrays are a strong choice when data is ordered, frequently accessed by position, or repeatedly traversed. Common uses include scores, measurements, sensor readings, character sequences, table rows, pixels, grids, matrices, lookup tables, and precomputed values. Arrays also provide a foundation for structures such as stacks, queues, and heaps.

Choose a fixed-length array when the size is known in advance, the number of elements will not change, and predictable memory use is important. Choose a dynamic array when the collection grows or shrinks and fast indexed access remains important. Dynamic arrays are particularly suitable when appending is more common than inserting or deleting near the beginning or middle.

Consider another data structure when frequent middle operations dominate the workload, because shifting can make those operations $O(n)$. The central design question is whether the workload benefits more from fast indexed access and compact traversal or from efficient changes to the collection's interior.

Final takeaway: Use an array-based structure when ordered storage, fast access by index, and efficient traversal are central requirements; select fixed or dynamic storage based on whether the collection's size is stable or changing.