IB Computer Science Topic B2.2.2: Constructing Programs That Apply Arrays and Lists Notes

Arrays and Lists: Holding Many Values Under One Name

1. An array and a List both store a numbered sequence of values under a single variable name, so one loop can reach all of them.
2. The difference that shows up in the code is whether the structure can change length while the program runs.

Arrays: Fixed Length, One Data Type

An array is a fixed-size, ordered collection of elements that all share the same data type.

One-Dimensional Arrays

1. A one-dimensional array is a single row of values, reached by a single index.
2. In Java the size is either given by the literal values in braces or stated with new, and it cannot change afterwards.

numbers = [1, 2, 3, 4]
print(numbers[0])        # 1  -> the first element
print(numbers[3])        # 4  -> the last element
print(len(numbers))      # 4  -> how many elements

int[] numbers = {1, 2, 3, 4};
int[] scores = new int[10];   // 10 slots, all holding 0

System.out.println(numbers[0]);      // 1  -> the first element
System.out.println(numbers[3]);      // 4  -> the last element
System.out.println(numbers.length);  // 4  -> how many elements

Indices Start at Zero

1. The first element is at index 0, not index 1.
2. An array of length 4 therefore has valid indices 0, 1, 2 and 3, and its last element is at index length - 1.
3. This is why a counted loop is written with i < length rather than i <= length.

Two-Dimensional Arrays: Rows and Columns

1. A two-dimensional array holds a table of values and needs two indices, the row first and the column second.
2. It is stored as an array whose elements are themselves arrays, which is why matrix[1] gives a whole row and matrix[1][0] gives one value inside it.

matrix = [[1, 2, 3],
          [4, 5, 6]]

print(matrix[1])       # [4, 5, 6]  -> the second row
print(matrix[1][0])    # 4          -> row 1, column 0
print(len(matrix))     # 2          -> number of rows
print(len(matrix[0]))  # 3          -> number of columns

int[][] matrix = { {1, 2, 3},
                   {4, 5, 6} };

System.out.println(matrix[1][0]);      // 4  -> row 1, column 0
System.out.println(matrix.length);     // 2  -> number of rows
System.out.println(matrix[0].length);  // 3  -> number of columns

Traversing a 2D Structure with Nested Loops

1. Reaching every value in a table takes two loops, one inside the other.
2. The outer loop moves down the rows and the inner loop runs across the columns of the current row.
3. The inner loop finishes completely before the outer loop moves on, so a 2 by 3 table is visited in the order (0,0) (0,1) (0,2) (1,0) (1,1) (1,2).
4. Any running total has to be set to 0 before the loops start, not inside them, or it resets on every pass.

matrix = [[1, 2, 3],
          [4, 5, 6]]

total = 0
for row in range(len(matrix)):
    for col in range(len(matrix[row])):
        total = total + matrix[row][col]

print(total)   # 21

int[][] matrix = { {1, 2, 3},
                   {4, 5, 6} };

int total = 0;
for (int row = 0; row < matrix.length; row++) {
    for (int col = 0; col < matrix[row].length; col++) {
        total = total + matrix[row][col];
    }
}

System.out.println(total);   // 21

Lists: Collections That Resize While the Program Runs

A List is an ordered, resizable collection of elements.

1. Python calls this a list and it is the default way to store a sequence.
2. Java calls it an ArrayList, which has to be imported and is declared with the type of its elements in angle brackets.
3. Both are dynamic structures, so the length reported at the end of a run depends on what the program did during it.

Add, Remove and Traverse a Dynamic List

1. Add: append() in Python and add() in Java put a new element on the end.
2. Remove: remove() takes the element out and closes the gap, so every later element shifts down one index.
3. Traverse: a for-each loop reads every element in order without needing an index at all.

fruits = ["apple", "banana"]

fruits.append("cherry")      # add    -> ['apple', 'banana', 'cherry']
fruits.insert(1, "kiwi")     # add at index 1
fruits.remove("banana")      # remove by value

for f in fruits:             # traverse
    print(f)

print(len(fruits))           # 3

import java.util.ArrayList;

ArrayList<String> fruits = new ArrayList<>();

fruits.add("apple");             // add
fruits.add("banana");
fruits.add(1, "kiwi");           // add at index 1
fruits.remove("banana");         // remove by value

for (String f : fruits) {        // traverse
    System.out.println(f);
}

System.out.println(fruits.size());   // 2

Removing by Index or by Value in Java

1. Java has two remove() methods and picks between them by the type of what is passed in.
2. Passing a plain int removes the element at that index.
3. Passing an object removes the first matching value.

Two-Dimensional Lists in Python

1. A two-dimensional List is a list whose elements are themselves lists, so it can grow by rows as well as within a row.
2. Rows do not have to be the same length, which a two-dimensional array in Java does not allow once it has been created with fixed column counts.

seats = []

for row in range(3):                  # add three rows
    seats.append([False] * 4)        # each row has four free seats

seats[0][2] = True                   # book row 0, seat 2

for row in seats:                    # traverse the whole grid
    print(row)

# [False, False, True, False]
# [False, False, False, False]
# [False, False, False, False]

Array or List: What Changes in the Code

1. Reading and changing an element looks almost identical in both, so the choice shows up only when the length has to change.
2. The memory and performance reasoning behind these differences belongs to B2.2.1 and is not repeated here.

Built-in Functions the Paper May Prohibit

1. Built-in functions such as sort, pop, len, max and min are encouraged in normal coursework and in the internal assessment.
2. Some examination questions prohibit specific built-in functions, and those questions say so clearly in the wording.
3. Practise the hand-written version of each one, so that finding the largest value with a loop is available when max() is not.
4. Set the running best to the first element rather than to 0, or a list of negative numbers returns 0 as its maximum.