07 Arrays and Collections

Arrays, Size, and Indexes

An array groups related values under one variable while preserving their order. Every element has the same declared element type, and the array's size is fixed when the array object is created.

For example, an integer array can represent five test scores. Java arrays use zero-based indexing: the first element is at index $0$, and an array with length $n$ has its final element at index $n-1$. This makes the valid-index rule central to nearly every array operation.

A declaration specifies the type of elements that the variable may reference, but it does not create the array object by itself. Creating an array with new supplies its capacity. Java initializes new elements with default values: numeric elements receive $0$, boolean elements receive false, and reference elements such as String receive null.

An array may also be initialized directly with a list of values. The number of supplied values becomes the array's length. The length field reports that number, and it is written as array.length, not array.length().

Takeaway: An array is ordered, homogeneous, and fixed-size; its indexes begin at $0$, and its length is available through the length field.

Accessing and Traversing Elements

Read an element with square-bracket notation, such as scores[i], and update it by assigning a new value to that position. The index must be at least $0$ and less than the array's length.

If an index is negative or is equal to or greater than the length, Java throws an ArrayIndexOutOfBoundsException at runtime. A safe access pattern checks both bounds before reading or updating:

• Confirm that the index is greater than or equal to $0$.

• Confirm that the index is less than array.length.

• Only then use array[index].

A traditional for loop is appropriate when the index matters. Start the loop at $0$, continue while the index is less than the length, and increase the index after each iteration. The condition must use <, not <=, because array.length is one position beyond the final valid index.

A for-each loop is convenient when only the values are needed. Its loop variable receives each value, but assigning a new value to that variable does not update the corresponding array element. To modify the array, use an indexed loop and assign through array[i].

Takeaway: Use an index when position or modification matters; use a for-each loop when you only need to process each value.

Searching Arrays

Searching an array means determining whether a target occurs and, when needed, finding its position.

A Linear search examines elements from the beginning toward the end. It does not require sorted data, and it can stop as soon as it finds the target. A common pattern initializes a result index to -1; because valid indexes are nonnegative, -1 can represent “not found.” In the worst case, linear search examines every element, so its running time grows as $O(n)$.

A Binary search is appropriate when the searched range is already sorted. It compares the target with a middle element and discards the half that cannot contain the target, repeatedly reducing the search range. Its typical running time is $O(\log n)$, but using it on unsorted data does not provide a reliable result. Sorting the data first also has a cost, so binary search is most useful for sorted data or repeated searches where maintaining sorted order is worthwhile.

Takeaway: Linear search works on any array; binary search is faster for large sorted data but depends on the sorted-order requirement.

Aggregate Computations

An aggregate computation combines values during a traversal. The general pattern is:

1. Initialize an accumulator, counter, minimum, or maximum.

2. Visit each relevant element.

3. Update the running result when the element contributes.

4. Use or return the final result.

For a sum, initialize an accumulator to $0$ and add each element. To compute an average from integer values, convert either the sum or one operand to double before division; otherwise, integer division can discard the fractional part.

For a minimum or maximum, initialize from the first element rather than from an arbitrary value. Then compare the remaining elements with the current result and replace it when a smaller or larger value is found. This approach assumes that the array is not empty. An empty-array policy must be defined separately because there is no first element from which to initialize the result.

Counting follows the same pattern: start a counter at $0$, test each element against a condition, and increment the counter when the condition is true.

Takeaway: Most array summaries are systematic one-pass algorithms built from initialization, traversal, and conditional updates.

Updating and Copying Arrays

Arrays are mutable: an operation can replace existing element values even though the array's length remains fixed. A method that receives an array and assigns to its elements changes the same array object supplied by the caller. That behavior is useful for in-place updates, but it should be clear when the original data will be modified.

To preserve the original values, create a separate copy before updating. Java's Arrays utility class supports common operations such as copying, filling, sorting, and searching. A copied array can be changed independently of the original array.

When selecting an update strategy, ask whether the caller wants mutation or a new result. In-place changes can avoid extra storage, while copying protects the original data and can make later comparisons or reuse safer.

Takeaway: Fixed length does not mean fixed values; array elements can change, and copying is the standard way to preserve the original contents.

Multidimensional and Jagged Arrays

A multidimensional array uses more than one index. In Java, a two-dimensional array is an array of arrays, so the first index selects a row and the second selects an element within that row.

For a rectangular table, every row may contain the same number of elements. The number of rows is available from table.length, while the number of columns in a particular row is table[row].length. Nested loops can visit every element: the outer loop advances through rows, and the inner loop advances through the current row.

Because each row is a separate array, rows can also have different lengths. This arrangement is called a jagged array. When rows may differ, the inner loop must use the current row's length rather than assuming one shared column count. The same rule makes nested traversal safe for both rectangular and jagged structures.

Takeaway: Treat each row as its own array; use the current row's length whenever row sizes may differ.

Arrays, Collections, and Reliable Problem Solving

An array is a good choice when the number of elements is known and fixed or when direct indexed storage is the main requirement. A collection is often better when the program frequently adds or removes elements or needs collection-oriented operations.

For example, an ArrayList<String> can grow as names are added and can remove an existing name. Its size changes during execution, unlike an array's fixed length. Both structures can support related tasks such as traversal, searching, updating, and aggregate calculations, but their trade-offs differ.

Before choosing a structure, consider:

• Whether the number of elements is fixed.

• Whether insertion and removal are frequent.

• Whether direct indexed access is important.

• Whether the available library operations match the problem.

• Whether the program should modify shared data or work on a copy.

A useful debugging checklist is to verify the valid index range, consider whether the array can be empty, decide whether an index is needed, confirm that binary search receives sorted data, and check whether a for-each loop is being mistaken for an update mechanism.

Takeaway: Choose arrays for fixed-size indexed data and collections for data whose size or operations need to change.