## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 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); ...`

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required