Naming the Implementations

We now have three things: the List ADT, and two classes that implement it.

Think about the name DynamicArray, the one we gave our growable array back in Chapter 1. That name describes a behavior. The array grows on demand. That was fine on its own. But now that we see this class as one implementation of the List ADT, there is a more useful way to name it: name an implementation after the data structure that backs it.

Our node-based list is backed by linked nodes, and we named it LinkedList. Our growable-array list is backed by an array, so we will call it an ArrayList. So from here on, we rename DynamicArray to ArrayList.

This convention splits naming into two parts:

The ADT postfix says what the thing is. A List is a list, however it is built.
The implementation prefix says how it is built. ArrayList and LinkedList name their internal structure.

Java’s Collections Framework

This is not a convention I invented. Java’s own standard library, java.util, is built the same way. You have very likely used it already in your first programming course. It provides a List interface, an ArrayList class, and a LinkedList class that implement it, plus several other implementations. What we have built by hand in this chapter is a small version of Java’s own Collections Framework.

Remember the difference in cost: the same selectionSort ran in $O (n^{2})$ on one list and $O (n^{3})$ on the other, entirely because of how get was implemented. When the name of an implementation tells you its structure, it also tells you something about its costs. If the class is called ArrayList, you can expect get to be $O (1)$ . If it is called LinkedList, you can expect get to traverse the nodes.