Lists as abstractions

Abstractions in computer science hide details so programmers can focus only on what matters now.

Commonly used abstractions include:

In Java, a list could mean an array or an ArrayList. A Java array has a fixed length. A Java ArrayList has a size that can be changed. For this discussion, the advantages are the same.

A programmer can write code once that executes for each element in a list. In many cases, the code will work regardless of the number of elements in the list. (The programmer does not need to know exactly how many elements will be in the list before they can write the code.)

The examples below are also available as Lists as abstractions in AP CSP Language.

Example 1: Finding an average

With a list (Java ArrayList)

public static double findAverage(ArrayList<Double> scores)
{
    double sum = 0;
    
    for(int i = 0; i < scores.size(); i++)
    {
        sum += scores.get(i);
    }
    
    return sum / scores.size();
}

The findAverage method, called with the list [90.0, 100.0, 80.0], returns 90.0.

The findAverage method, called with the list [90.0, 100.0, 80.0, 70.0], returns 85.0.

The statement sum += scores.get(i); executes once for each element in scores. The expression sum / scores.size() divides by the number of elements in scores. As long as there is at least 1 element in scores, the method correctly returns the average.

(The behavior of findAverage, called with an empty list, is more complex. Java handles division by zero differently depending on type and depending on the numerator. See Division operations for additional details.)

Without a list

public static double findAverage(double s1, double s2, double s3)
{
    double sum = 0;
    
    sum += s1;
    sum += s2;
    sum += s3;
    
    return sum / 3;
}

The call findAverage(90.0, 100.0, 80.0) returns 90.0. The method correctly finds the average of exactly 3 scores.

(The code inside the method could be written on a single line. The approach above more clearly illustrates the point.)

This code might initially appear less complex than the solution that uses a list. Consider what happens if the programmer wants to find the average of 4 scores, instead of 3.

public static double findAverage(double s1, double s2, double s3, double s4)
{
    double sum = 0;
    
    sum += s1;
    sum += s2;
    sum += s3;
    sum += s4;
    
    return sum / 4;
}

The method header must be modified (or a new method written) to accept an additional parameter. The additional value must be added to sum. The computation of the average must be modified to account for the new value.

Consider what happens if the programmer wants to find the average of anywhere between 3 and 10 values. The programmer must write 8 methods, each of which must take the correct number of parameters. The programmer must ensure that each method correctly adds each parameter to sum and that the calculation of the average divides by the correct number of parameters.

The list manages complexity

Using a list manages complexity by removing the need for the programmer to consider the exact number of values. It allows the programmer to focus on the (simple) algorithm to calculate the average.

The example below is slightly more complex.

Example 2: Finding the largest

With a list (Java array)

public static int findMax(int[] arr)
{
    int max = arr[0];

    for(int i = 1; i < arr.length; i++)
        if(arr[i] > max)
            max = arr[i];
    
    return max;
}

As long as arr contains at least 1 element, the method correctly returns the largest value in arr. The programmer does not need to worry about how many elements might be in arr nor does the programmer need to manually handle each element. The programmer can focus on the algorithm.

See Finding the minimum or maximum for more details.

Without a list

public static int findMax(int a, int b, int c)
{
    int max = a;

    if(b > max)
        max = b;
    
    if(c > max)
        max = c;
    
    return max;
}

Method findMax correctly returns the maximum of exactly 3 integers.

The code to handle each parameter is more complex than in findAverage. Adding additional parameters requires writing more significant additional code without error.

The list manages complexity

When designing and implementing an algorithm that processes multiple values of the same type in the same way, a list (array or ArrayList in Java) is a natural choice. The list allows the programmer to focus on how the algorithm should process a single value, rather than on how many values are to be processed and on correctly duplicating the code to handle each value.

Example 3: Collecting values

Example 1 demonstrates finding the average of scores. Consider the problem of accepting input of scores.

If the exact number of scores is known before the program is written, a list offers a relatively minor advantage. If the number of scores is not known, a list offers a much bigger advantage. The solutions below work when the number of scores is not known.

With a list (Java ArrayList)

Scanner fromKeyboard = new Scanner(System.in);

ArrayList<Double> scores = new ArrayList<Double>();

System.out.print("Score (-1 when done): ");
double score = fromKeyboard.nextDouble();

while(score != -1)
{
    scores.add(score);
    
    System.out.print("Score (-1 when done): ");
    score = fromKeyboard.nextDouble();
}

System.out.println(scores);

The code segment prompts the user to enter scores and to enter a sentinel (-1) to indicate no more scores. (The code does not attempt to ensure at least 1 score, nor does it attempt to validate each score.)

Each score is stored in the scores list. The code works correctly. Each score entered by the user is added to scores. The -1 entered to signal no more input is not added.

(double values are typically compared using a tolerance, not using == or !=. See Floating point roundoff error. In this case, != is acceptable since the sentinel value is exactly -1.)

Without a list

Scanner fromKeyboard = new Scanner(System.in);

double s1 = 0, s2 = 0, s3 = 0;
int count = 0;

System.out.print("Score (-1 when done): ");
double input = fromKeyboard.nextDouble();

while(input != -1)
{
    count++;
    
    if(count == 1)
        s1 = input;
    else if(count == 2)
        s2 = input;
    else
        s3 = input;
    
    if(count < 3)
    {
        System.out.print("Score (-1 when done): ");
        input = fromKeyboard.nextDouble();
    }
    else
        input = -1;
}

System.out.println(count);
System.out.println(s1);
System.out.println(s2);
System.out.println(s3);

Without a list, a variable must be declared for each possible score. This code segment declares s1, s2, and s3 to store up to 3 scores. The variable count makes the code segment easier to understand.

The code segment correctly accepts and stores input of zero, one, two, or three scores.

The list manages complexity

Without a list, accepting more than 3 scores requires modifying the code segment. With a list, any number of scores can be accepted with the same code segment.

Without a list, conditional statements determine which variable should store the current input. With a list, the current input is simply added to the end of the list. (If the solution with a list used an array, the current input could be stored at a calculated index, such as count - 1.)

Additional examples

Help & comments

Get help from AP CS Tutor Brandon Horn

Comment on Lists as abstractions