Arrays and Lists

Imagine you need to store the grades of 30 students. With what you know about variables, you would need to create grade1, grade2, grade3 ... grade30 — 30 separate variables. An array solves this: a single variable 'grades' that can hold 30 values, each accessible by a numeric position called an index.

An array is an ordered collection of elements of the same type, stored in contiguous positions in memory. The index is the address of each element within the array. In almost all programming languages, indices start at zero — the first element is at position 0, the second at position 1, and so on.

This detail of starting at zero confuses many beginners. If an array has 5 elements, the valid indices are 0, 1, 2, 3, and 4. Trying to access index 5 causes an 'index out of bounds' error — one of the most common bugs in programming.

Pseudocode to create an array of integers with 5 positions: grades = [8, 7, 9, 6, 10]. To access the third element: grades[2] (remember: index 2 = third position). To modify: grades[2] = 9.5.

Arrays can also be created empty with a defined size and filled later. This is useful when the values will only be known during execution, such as when reading data from a user or a file.

To traverse all elements of an array, combine it with a for loop: FOR i FROM 0 TO size - 1 DO process grades[i]. The size of the array is usually accessible through a property like 'length' or 'size'.

The most frequent operations are: calculating the sum, finding the maximum and minimum, counting elements that satisfy a condition, and searching for a specific element.

To find the largest value: maximum = grades[0]; FOR i FROM 1 TO size - 1 DO IF (grades[i] > maximum) THEN maximum = grades[i]. We start by assuming the first element is the largest and update whenever we find a larger one.

For linear search (checking whether a value exists): FOR i FROM 0 TO size - 1 DO IF (grades[i] == searchValue) THEN display 'Found at ' + i AND BREAK. In the worst case, it traverses all elements. For sorted arrays, binary search is much more efficient.

Traditional arrays have a fixed size defined at creation. If you create an array for 10 elements and need an 11th, you have a problem. This makes them efficient in memory and access, but rigid in size.

Dynamic lists (ArrayList in Java, list in Python, Array in JavaScript) grow and shrink automatically. You can add and remove elements at any time. Internally, many implementations use arrays that are reallocated when necessary.

The choice between array and dynamic list depends on the case: if the size is fixed and known, an array is more efficient. If the size varies, a dynamic list is more convenient. In practice, beginners often start with dynamic lists for their flexibility.

Arrays can have more than one dimension. A two-dimensional array is like a table with rows and columns — think of a spreadsheet or a game board. To access an element: table[row][column].

Example: a 3x3 grid for tic-tac-toe. table[0][0] is the top-left corner; table[1][1] is the center; table[2][2] is the bottom-right corner. To traverse the entire grid, you need two nested loops: one for rows, another for columns within each row.

Three-dimensional and higher arrays exist but are rarely used directly. When you need complex data structures, there are usually specific structures (matrices, tensors in libraries like NumPy) that offer better support.