**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 Strings. * 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 Strings, **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 ArrayLists, 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 LinkedLists, see [this LinkedList tutorial](LinkedList.htm).