Think Data Structures

Chapter 3. ArrayList

This chapter kills two birds with one stone: I present solutions to the previous exercise and demonstrate a way to classify algorithms using amortized analysis.

Classifying MyArrayList Methods

For many methods, we can identify the order of growth by examining the code. For example, here’s the implementation of get from MyArrayList:

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return array[index];
    }

Everything in get is constant time, so get is constant time. No problem.

Now that we’ve classified get, we can classify set, which uses it. Here is our implementation of set from the previous exercise:

    public E set(int index, E element) {
        E old = get(index);
        array[index] = element;
        return old;
    }

One slightly clever part of this solution is that it does not check the bounds of the array explicitly; it takes advantage of get, which raises an exception if the index is invalid.

Everything in set, including the invocation of get, is constant time, so set is also constant time.

Next we’ll look at some linear methods. For example, here’s my implementation of indexOf:

    public int indexOf(Object target) {
        for (int i = 0; i<size; i++) {
            if (equals(target, array[i])) {
                return i;
            }
        }
        return -1;
    }

Each time through the loop, indexOf invokes equals, so we have to classify equals first. Here it is:

 private boolean equals(Object target, Object element) { if (target == null) { return element == null; } else { return target.equals(element); ...