Dynamic Arrays

Note

Objectives

1. Explain the difference between an array and a resizing array list.
2. Compare and contrast at least two ways to implement a resizing array list.

Code: ResizingArrayStack.java

ArrayList is the first of many Java collections that we'll learn about in this course. A collection is an object that represents a group of zero or more objects called elements. In Java, lists, sets, and maps are examples of commonly-used collections.

Let's examine two approaches to implement ArrayList. Consider the following code that shows us how an ArrayList changes over time as we add numbers to it.

List<Integer> nums = new ArrayList<>();
nums.add(1); // [1]
nums.add(2); // [1, 2]
nums.add(3); // [1, 2, 3]

This example provides some insight into one possible approach. The brackets notation printed out after each example is what you get if you have exactly those values stored in an array! We can keep track of this array with a private field called elementData. Read the comments to see what's happening in each step of the constructor and the add method.

// The use of E here indicates the type of elements in the ArrayList.
// Clients can say ArrayList<Integer> to represent a list of integers.
public class ArrayList<E> implements List<E> {
    private E[] elementData;

    public ArrayList() {
        // Create a zero-length array because it has exactly the
        // string representation that we want: []
        elementData = new E[0];
    }

    public void add(E element) {
        // Make space by creating a slightly longer new array.
        E[] newData = new E[elementData.length + 1];

        // Copy everything over from the old array to the new array.
        for (int i = 0; i < elementData.length; i += 1) {
            newData[i] = elementData[i];
        }

        // Add the element to the end of the new array.
        newData[newData.length - 1] = element;

        // Re-assign the private field to the new array.
        elementData = newData;
    }

    public int size() {
        return elementData.length;
    }

    public String toString() {
        return Arrays.toString(elementData);
    }
}

In this approach, our internal representation is exactly identical to the result that's printed-out. So we have a working ArrayList. Job well done, right?

When running this code, clients complain that it's too slow. What could be causing the slowness?

The problem is that it takes too long to make a new elementData array every time we need to add just 1 element. Because arrays in Java have a fixed length, there's not a simple way to make space for another element except by creating a brand new array of the desired length.

While this code works fine when the lists are small, even today's fast computers and smartphones will struggle with lists that have thousands of elements. Imagine scrolling through your feed in an app and waiting a longer and longer time to load each element; as the number of elements increases, so too does the time it takes to copy everything over.

Tip

Optionally, open the preloaded Java Tutor environment and see how it takes 45 steps just to add the numbers 1, 2, 3 into an empty list! This approach takes a lot of time!

To address this inefficiency, we can introduce a second field called size.

public class ArrayList<E> implements List<E> {
    private E[] elementData;
    private int size;

    public ArrayList() {
        // Create a length-10 array to store elements.
        elementData = new E[10];

        // Assign size to 0 for an initially-empty list.
        size = 0;
    }

    public void add(E element) {
        // Add the element to the next space in the array.
        elementData[size] = element;

        // Increment the size to indicate the list has grown.
        size += 1;
    }

    public int size() {
        // Return the current size of the list.
        return size;
    }
}

Initially, size is 0. But, when we call add, the size is incremented by 1 to reflect the new element added to the array. The size tells us which values in the array are actually in-use by the list. Even though elementData has space for 10 elements, a new ArrayList should function as if it were empty. The size variable helps maintain the appearance of a dynamically-resizing list by treating only the first size-number of elements as actually in the list.

Important

Open the preloaded Java Tutor environment and step through to see how the size field changes to match the actual number of elements added into the list. This version only takes 28 steps to add the numbers 1, 2, 3 compared to the 45 steps of the previous version. The difference will only become more significant as the number of elements increases.

This approach avoids creating a new array each time we need to add an element, though this particular implementation is limited to just 10 elements. The actual Java implementation of the ArrayList class contains a little more code to create a new array double the current capacity when more space is needed, which is why we call this data structure the dynamic array.

Why would it be incorrect to implement the size method by returning the length of elementData?

In this second approach, the elementData is no longer exactly what the client sees, so the length of elementData is not the same as the size of the list. Instead, the elementData array will usually contain a lot of empty spaces that won't be filled until the client adds elements to the list.