07. Lists, Arrays, and Sequential Data

Collections, Elements, and Positions

A collection lets a program keep related values under one name instead of creating a separate variable for every value. A list is an ordered sequence of elements, and an array is another common name for a similar structure.

For example, a collection of scores can contain the values $82$, $95$, and $71$. The collection has one identity, while each score remains a separate element. This organization reduces repeated code and makes it easier to process many values with the same algorithm.

Positions and boundaries

An index identifies an element's position. In zero-based indexing, the first element has index $0$, the second has index $1$, and so on. For a collection with length $n$, the usual valid indexes are

The length counts elements; it is not itself usually a valid index. Thus, a collection of length $4$ has last valid index $3$. Attempting to access index $4$ is an out-of-range access in many languages.

Some languages provide negative indexes. In Python, for example, index $-1$ refers to the final element.

Takeaway: Think of length as a count and an index as a position. In a zero-based collection, the last position is one less than the length.

Creating and Modifying Collections

A collection may begin with values or may begin empty. An existing element can be replaced by assigning a new value to its index. Replacing an element normally changes the value at that position without changing the collection's length.

Common collection operations include:

• Append: add an element at the end.

• Insert: add an element at a specified position.

• Remove: delete an element by value or position.

• Clear: delete all elements.

The operation names and exact behavior vary by language. For example, Python provides operations including append, insert, remove, pop, and clear.

Reading versus changing

When a program only reads values, a value-based loop is often sufficient. When it must assign a replacement back into the collection, it generally needs an index. Updating every negative value to zero, for example, requires identifying each element's position before assigning the replacement.

Changing an existing collection is mutation. Creating a separate result collection preserves the original data. This distinction matters when multiple variables refer to the same collection: an in-place change may be visible through every reference to that collection.

Takeaway: Choose operations deliberately: read values when calculating, use indexes when assigning, and decide whether the result should mutate the original collection or be stored separately.

Traversing and Accumulating

Traversal means visiting collection elements systematically. A value-based traversal is appropriate when the algorithm needs each value but not its position. An index-based traversal is appropriate when the algorithm needs positions, must update elements, or must compare neighboring elements.

A typical index range for a collection of length $n$ begins at $0$ and ends at $n-1$. Stopping at $n$ would attempt one access beyond the final element.

Building results during traversal

An accumulator begins with an initial value and is updated as elements are processed. To total the values $4$, $8$, and $15$, initialize the total to $0$, then add each element:

• After processing $4$, the total is $4$.

• After processing $8$, the total is $12$.

• After processing $15$, the total is $27$.

The same pattern can count elements satisfying a condition, calculate an average, or build a result collection. A count of passing scores, for instance, starts at $0$ and increases by $1$ whenever a score is at least $60$.

Takeaway: A traversal supplies the repeated processing step, while an accumulator preserves the result built so far.

Selecting, Transforming, and Updating

Many collection algorithms can be understood as one of three related patterns.

Selecting elements

Filtering keeps only elements that satisfy a condition. To create a collection of passing scores, examine each score and append it to the result when the score is at least $60$. The original scores remain available if the passing results are stored separately.

Producing corresponding values

Transformation creates one output value for each input value. If the input values are $2$, $5$, and $7$, multiplying each by $2$ produces $4$, $10$, and $14$. A new collection is useful when the original values must be preserved.

Finding an extreme value

To find the largest value in a nonempty collection, initialize the candidate maximum with the first element. Compare the remaining elements with that candidate and replace it when a larger value is found. Initializing the maximum to $0$ is unsafe if all valid inputs might be negative.

Updating in place

An index-based traversal can replace each element directly. For example, multiplying every element by $2$ changes the original collection rather than creating a separate doubled collection.

Takeaway: Selecting keeps some elements, transforming creates corresponding results, and in-place updating changes existing elements. The intended result determines which pattern to use.

Searching and Combining Operations

A sequential search examines elements in order until it finds a target or reaches the end. A useful search procedure returns the matching index when the target is found and returns $-1$ when it is absent.

For the collection $[12, 7, 19, 4]$, searching for $19$ returns index $2$. Searching for $10$ returns $-1$. The nonnegative result communicates success, while $-1$ communicates failure.

A sequential search has worst-case running time $\mathrm{O}(n)$, where $n$ is the collection's length, because it may inspect every element. A sorted collection may support a binary search with fewer comparisons, but binary search is a different strategy and depends on maintaining sorted data.

Search and update can be combined. For example, an algorithm can traverse a collection and replace every negative value with $0$. Because the algorithm assigns values back into the original positions, it needs indexes rather than only copied element values.

Takeaway: A search needs a clear result convention, and an update needs a way to identify the position being changed.

Nested Data and Reliable Boundaries

A collection can contain other collections. This creates a row-and-column structure suitable for tables, grids, game boards, and spreadsheets. For example, a two-row table can contain the rows $[80, 90, 85]$ and $[75, 88, 92]$.

The first index selects a row, and the second index selects a column. In this example, row index $0$ and column index $1$ identify the value $90$. Processing every cell requires a loop for the rows and an inner loop for the elements of each row.

If a rectangular table has $r$ rows and $c$ columns, visiting every cell requires approximately $r \times c$ element visits. Each loop must respect the valid bounds of the collection it traverses.

Boundary and correctness checks

Test collection algorithms with:

• An empty collection.

• A one-element collection.

• A target at the first position.

• A target at the last position.

• A target that does not occur.

• Duplicate values.

• Negative values when they are allowed.

• An attempted index equal to the collection length.

Frequent errors include starting at index $1$ and skipping the first element, accessing index $n$ instead of stopping at $n-1$, initializing an extreme-value search with an unsuitable constant, changing collection length during traversal, and unintentionally mutating shared data.

Takeaway: Boundary cases reveal off-by-one errors and unsafe assumptions that ordinary examples may hide.

• linear search