Lesson 5.12

Fixed-size arrays versus growable lists

Part 5: Text, lists, stacks and queuesReading, about 7 min2 exercises in this lesson

Fixed-size arrays and growable lists

By the end of this you will be able to say whether a structure has a fixed size or can grow, compare the two on memory, flexibility and speed, and choose one for a task with a reason.

You have met two kinds of list already. A Java array, such as int[], keeps the same length from the moment it is made. A Python list and a Java ArrayList can grow while the program runs. This lesson is about when that difference matters.

Two kinds of structure

A structure whose size is set when it is made, and cannot change after that, is called static. Its values can still be changed; its number of places cannot. A structure that can grow and shrink while the program runs is called dynamic.

A Java array is static.
A Python list is dynamic.
A Java ArrayList is dynamic.

This "static" has nothing to do with the word static in public static void main. It is the same English word used for a different idea.

Making a list with a set number of places

So far you have made a list by writing its values. You can also make one with a set number of places and fill them in later.

counts = [0] * 5
print(counts[0])
print(len(counts))

public static void main(String[] args) {
    int[] counts = new int[5];
    System.out.println(counts[0]);
    System.out.println(counts.length);
}

When it runs:

0
5

In Python, [0] * 5 makes a list of five zeros. In Java, new int[5] makes an array with five places, and Java puts 0 in each one. The 5 is the length, so the indexes are 0 to 4.

Now try to write a sixth value.

counts = [0] * 5
counts[5] = 1

public static void main(String[] args) {
    int[] counts = new int[5];
    counts[5] = 1;
}

Python stops with IndexError: list assignment index out of range. Java stops with an ArrayIndexOutOfBoundsException. Writing to an index does not make a list longer. It can only change a place that is already there.

The difference is what happens next. A Python list can still grow with append. A Java array cannot grow at all: it has no add, and its length stays 5 for as long as it exists.

When an array is full

To keep one more value than a full array holds, you make a new, bigger array and copy every value across.

old = [4, 8, 15]
bigger = [0] * 4
for i in range(len(old)):
    bigger[i] = old[i]
bigger[3] = 16
print(bigger)

public static void main(String[] args) {
    int[] old = {4, 8, 15};
    int[] bigger = new int[4];
    for (int i = 0; i < old.length; i++) {
        bigger[i] = old[i];
    }
    bigger[3] = 16;
    for (int value : bigger) {
        System.out.println(value);
    }
}

The new array ends up holding 4, 8, 15 and 16. Copying three values is quick. Copying a million values to add one more is not, and the old array and the new one both take up memory while the copy runs.

In Python you would not write this out: old.append(16) does it. In Java, an ArrayList does it for you, which is the next section.

How a growable list grows

Inside, a Python list and a Java ArrayList keep their values in an array with some spare places at the end. Adding a value at the end fills a spare place, which is quick. When no spare place is left, the list gets a bigger array with room for more values, copies the values across, and carries on.

So most additions at the end are quick, and once in a while one takes longer because the values may have to be copied. The list does that work so that your program does not have to.

The price is memory. A growable list usually holds spare places it is not using yet. A fixed-size array has exactly the places you asked for, no more.

Inserting in the middle

A growable list can also take a new value at any index, not only at the end.

values = [12, 30, 41]
values.insert(1, 25)
print(values)

import java.util.ArrayList;

public static void main(String[] args) {
    ArrayList<Integer> values =
        new ArrayList<>();
    values.add(12);
    values.add(30);
    values.add(41);
    values.add(1, 25);
    System.out.println(values);
}

When it runs, it prints:

[12, 25, 30, 41]

In Python, insert(1, 25) puts 25 at index 1. In Java, add with two values does the same: the first is the index, the second is the value.

Every value after the new one moves up one index, the opposite of what happens when a value is removed. Here 30 and 41 each move up one. Inserting at index 0 of a list of 100,000 values moves all 100,000 of them. Adding at the end moves none.

Reading by position

Reading or replacing the value at an index is quick for both kinds. The places sit side by side in memory, so the computer works out where index 500 is from where the list starts. It does not step past the first 500 places to get there.

What each costs

Task	Fixed-size array	Growable list
Read or replace by index	quick	quick
Add at the end	only if a place is free; when full, make a bigger array and copy	quick, now and then a copy
Insert in the middle	only if a place is free, and every later value moves up; when full, make a bigger array and copy	possible; every later value moves up
Memory	exactly the places asked for	the values plus spare places
Size known in advance	needed when it is made	not needed

Choosing one

Ask one question first: is the number of values known when the structure is made, and will it stay the same?

If yes, a fixed-size array fits. For example, the temperature at each of the 24 hours of one day: there are always 24, so an array of 24 has no wasted places and never needs to grow.
If no, a growable list fits. For example, the names a user types until they type a blank line: the program cannot know how many there will be, and a list can take one more each time.

Picking a size "big enough" in advance does not fix the second case. Too small, and the program runs out of room. Too big, and most of the places are wasted.

In Python you will nearly always use a list, because that is what Python gives you. In Java you choose between an array and an ArrayList every time, and the question above is how to choose.

To justify a choice in a written answer, do three things:

Name the structure you chose.
Link it to a fact about the task: is the number of values known, and does it change?
Say what that gains, or what the other choice would cost: wasted memory, running out of room, or copying.

A common mistake: saying an array is "faster" with no more said. Reading by index is quick in both. An array's gain is that it uses exactly the memory it needs when the size is known. A list's gain is that it can grow.

Now try it yourself on the questions below.

Exercise 5.12.15.12.1 · Answer itFull array of times

A Java program keeps the finishing times of a race, in seconds, in an array made with int[] times = new int[10];. All 10 places hold a time. Then an 11th runner finishes.

(a) Explain why the program cannot store the 11th time by writing it to times[10]. [2]

(b) Explain what the program must do so that an array holds all 11 times. [2]

[4]

Your answer

Exercise 5.12.25.12.2 · Answer itSeats or waiting list

A cinema has 120 seats, and the number of seats never changes. One part of its booking program stores the price paid for each seat at tonight's film. Another part keeps a waiting list of names for tickets that are handed back. Names are added to the end of the waiting list all evening, and nobody knows how many people will join it.

(a) Explain why a fixed-size array suits the seat prices. [2]

(b) Explain why a growable list suits the waiting list better than a fixed-size array. [2]

[4]

Your answer