Arrays and Lists: Storing Many Values in One Name

What is an array?

An array stores many values of the same kind under one name. Think of a row of lockers with numbers on them.

• Each locker is an element.
• Its number is the index. Indexes start at 0.
• The number of elements is the length. Last index = length − 1.

Python:  scores = [72, 85, 90, 64, 78]
Java:    int[] scores = {72, 85, 90, 64, 78};
C++:     int scores[5] = {72, 85, 90, 64, 78};

Read one element: scores[1] gives 85. Change one: scores[3] = 70. Asking for scores[5] is an error (index out of bounds) because there is no sixth box.

In Java, a new array of numbers starts filled with 0; in C++ a local array is not cleared, so give it values first.

Traversing an array with a loop

Traversal means visiting every element once, in order. A loop does it, so the same code works for 5 values or 5,000. That is why lists help us generalise a solution.

Python:  for i in range(len(a)): print(a[i])
Java:    for (int i = 0; i < a.length; i++) { ... }
         for (int x : a) { ... }      // enhanced for
C++:     for (int i = 0; i < n; i++) { ... }

Use i < length, not i <= length, or you step one box past the end. The enhanced for (for-each) reads values but cannot change the array's boxes.

Standard array algorithms

Most array programs are built from a few patterns:

• Sum and average: total = 0, add each element, average = total / length.
• Largest / smallest: start with the first element, replace it when a bigger (smaller) one appears.
• Count: add 1 when an element passes a test (e.g. score ≥ 50).
• Linear search: check each box; return its index when it equals the target, or −1 if never found.
• Reverse, shift, swap: swap a[i] with a[n−1−i] for the first half.
• All / any: are all values positive? Is any value negative?

big = a[0]
for x in a:
    if x > big: big = x

2D arrays: rows and columns

A 2D array is an array of rows. grid[r][c] is the cell in row r, column c (both from 0).

Java:   int[][] g = new int[3][4];   // 3 rows, 4 columns
        g.length = 3, g[0].length = 4
Python: g = [[1, 2, 3], [4, 5, 6]]

Row-major traversal: outer loop over rows, inner loop over columns. Column-major: outer loop over columns. Typical tasks: row totals, column totals, largest in the grid, count matching cells, search a cell.

Arrays, lists and other structures compared

Java's ArrayList stores objects only, so numbers go in as wrapper classes: Integer for int, Double for double. Java changes int to Integer for you (autoboxing) and back (unboxing). Removing items while looping forward skips the next item, so loop backwards when removing.

Other structures: a dictionary/map finds values by key, a set keeps unique items, a stack/queue controls the order you take items out.

Try it: your week of steps

Write down how many steps (or minutes of exercise) you did each day for 7 days. Put them in an array of length 7. By hand, run the loops: total, average, best day (index of the largest), and how many days were above 5,000. Then type it in any language and check your answers.

Key formulas and definitions

• Indexes go from 0 to length − 1
• a[i] reads, a[i] = v changes element i
• average = sum / length
• 2D: g[row][col]; rows = g.length, columns = g[0].length
• Linear search: at most n checks for n elements

Worked examples

Common mistakes

• Starting the index at 1: the first element is a[0].
• Looping with i <= length: this goes one box past the end and crashes.
• Starting "largest" at 0: fails when all values are negative. Start with a[0].
• Mixing up g[row][col] order, or using g.length for columns in a 2D array.