**List Interface** The `List` is implemented by both the `ArrayList` and the `LinkedList`. !!! Warning: This page assumes that you already understand the material on the [Java Collection Framework page](Jcf). # List Interface * The [`List<E>`](http://javadoc.taylorial.com/java.base/util/List.html) interface describes a contract for classes that provide an implementation for storing lists of information. * The `E` between the angle brackets indicates the type of references contained in the list. For example, `List<String>` indicates that the list contains references to `String`s. * The `List<E>` interface is similar to the `Collection<E>` interface but adds the concept of ordering. * Some relevant methods from the `Collection<E>` interface include: + [`add(E)`](http://javadoc.taylorial.com/java.base/util/List.html#add%28E%29) -- adds an object to the end of the list. + [`clear()`](http://javadoc.taylorial.com/java.base/util/List.html#clear%28%29) -- removes all elements from the list. + [`contains(E)`](http://javadoc.taylorial.com/java.base/util/List.html#contains%28E%29) -- returns true if the specified element is found in the list. + [`isEmpty()`](http://javadoc.taylorial.com/java.base/util/List.html#isEmpty%28%29) -- returns true if no elements are in the list. + [`size()`](http://javadoc.taylorial.com/java.base/util/List.html#size%28%29) -- returns the number of elements in the list. * Some relevant methods added by the `List<E>` interface include: + [`add(int, E)`](http://javadoc.taylorial.com/java.base/util/List.html#add-int-E-) -- inserts the specified element at the specified position in the list. + [`get(int)`](http://javadoc.taylorial.com/java.base/util/List.html#get%28int%29) -- returns the element at the specified location in the list. + [`set(int, E)`](http://javadoc.taylorial.com/java.base/util/List.html#set%28int,E%29) -- replaces the element at the specified location with the specified element. * The following method does some silly stuff with a list of strings: ~~~~ Java public static void silly(List<String> words) { if(!words.isEmpty()) { String word = words.get(0); words.add(word.trim()); words.set(words.size()-1, "I'm last"); } for(String word : words) { System.out.println(word); } } ~~~~ * . + Here I've used the enhanced for loop, a.k.a., the for-each loop. In case you've forgotten how it works, if you read it like this: "For each `String`, **word**, in the `List` of `String`s, **words**, do the following: { blah blah blah }" you'll pretty much know what it does. + The loop will run `words.size()` times. + The first time in the loop, **word** is a reference to the first element in the list. + The second time in the loop, **word** is a reference to the second element in the list. + ... + The last time in the loop, **word** is a reference to the last element in the list. * Of course, all of this is pretty useless if we don't know about any classes that implement the `List<E>` interface, since we can't do: ~~~~ Java List<String> words = new List<>(); ~~~~ # ArrayList Implementation * The Java Collections Framework provides an array-based implementation of the `List<E>` interface as the [`ArrayList<E>`](http://javadoc.taylorial.com/java.base/util/ArrayList.html) class. * The `ArrayList<E>` has two instance variables: + `elementData` -- an array of `Object` references that holds references to the elements in the list. + `size` -- an `int` representing the size of the list, i.e., the number of elements in the list. * The length of the array is the capacity of the list. * For efficiency reasons, the JCF implementation starts with a capacity of 10 even though the list is empty. * This allows `add(E)` to be called ten times before a new array needs to be allocated. * Whenever `add(E)` is called and the capacity and size of the list are the same, a larger array must be allocated and the references in the old array must be copied to the new array. * Accessing an arbitrary element within the list can be done quickly because the references to each element are stored in an array and determining where the reference is located is a simple math operation. * Suppose that each reference requires 8 bytes to store. If we wish to access the reference of the fifth element in the array, we can add 32 bytes ($4 \times 8$ bytes) to the address of the first reference in the array. * Since the time required to access an element in an `ArrayList` is independent of the size of the list, we consider this to be easy. For formally, we'll refer to this as a contant-time or $O(1)$ algorithm, but discuss that more later. * You may have noticed that the `ArrayList<E>` implements the [`RandomAccess`](http://javadoc.taylorial.com/java.base/util/RandomAccess.html) interface. + The `RandomAccess` interace is a **marker** interface -- an interface that does not declare any methods. + By implementing the `RandomAccess` interface the `ArrayList<E>` is declaring that accessing elements in the list is fast. * For more information on `ArrayList`s, see [this `ArrayList` tutorial](ArrayList). # LinkedList Implementation * The [`LinkedList<E>`](http://javadoc.taylorial.com/java.base/util/LinkedList.html) doesn't use an array to store the data internally. * We will study the internal structure of the `LinkedList<E>` [later in this course](LinkedList.htm). * For now, it is sufficient to know that the `LinkedList<E>` class implements the `List<E>` interface and does not implement the `RandomAccess` interface. * Since it does not implement the `RandomAccess` interface, we are not guaranteed fast access to elements in the list; however, there are other operations that are faster with a `LinkedList<E>` than with an `ArrayList<E>`. * Depending on your application, you may find that it is better to use an `ArrayList<E>` while other times it is better to use a `LinkedList<E>`. * Since both class implement the `List<E>` interface, you can easily modify which implementation you use by just changing the `new` operation. * The following code shows how you can use the `silly()` method implemented above with either of these classes: * For more information on `LinkedList`s, see [this `LinkedList` tutorial](LinkedList.htm).