Dr. Chris Taylor

Tutorials

List Interface

Storing collections (groups) of similar objects is a common programming task.
- A text document is a collection of paragraphs. Each paragraph is a collection of words. Each word is a collection of characters.
- The computer's file system is a collection of files.
- A browser's bookmark list contains a collection of URLs.
- etc...
You have already seen one mechanism for storing collections of objects: the array.
The Java Collections Framework provides a number of classes that can be used to store collections of data.
In this page we will:
- Briefly review arrays, discussing some disadvantages
- Review the concept of an interface in Java
- Review one interface and one class and introduce a new class that are part of the Java Collections Framework:
  - The List<E> interface.
  - The ArrayList<E> class.
  - The LinkedList<E> class.

Arrays

An array is a collection of similar objects. Actually, one of two things:
1. A collection of primitives, all of the same type
```
int[] integers;
integers = new int[20];
```
  - The first line declares a reference to an array of ints, called integers.
  - The second line allocates space for an array of twenty ints and makes integers point to this newly allocated array.
2. A collection of references, all of the same type
```
Integer[] integers;
integers = new Integer[20];
```
  - The first line declares a reference to an array of Integer references, called integers.
  - The second line allocates space for an array of twenty references to Integer objects and makes integers point to this newly allocated array.
  - Each element in the array is currently referencing null since we haven't created any Integer objects.
  - The following loop will create twenty Integer objects and assign the references in the array to point to the newly created Integer objects:
```
for(int i=0; i<integers.length; ++i) {
  integers[i] = new Integer(i);
}
```
Arrays are nice because they allow you to store a collection of items in a group and act on all of the items in the group in the same way. For example, consider the following method:
```
public static void display(String[] names, PrintStream out) {
  for(int i=0; i<names.length; ++i) {
    out.println(names[i]);
   }
}
```
- We can call display as follows:
```
String[] names = {"Peter", "Paul", "Mary-Anne"};
display(names, System.out);  // Note: System.out is a PrintStream object
```
- The method will display all three names. If names had twenty names in it, all twenty would be displayed.
- If we wanted to do the same thing without an array, we'd need to hard-code the number of names, like this...
```
public static void display(String name1, String name2, String name3, PrintStream out) {
  out.println(names1);
  out.println(names2);
  out.println(names3);
}
```
- I'm not going to show you what it would look like if we had twenty names because I don't want you to lose your lunch, but just thinking about it probably enough to make you nauseous.

Arrays are not so nice because they cannot be resized easily. If we need to add an element to an array that is already full, we would need to create a larger array like this:

Create a new, larger, array
Copy over all the primitive values/references in the old array

Reassign the reference to the original array so that it now points to the new array

/**
  * Resizes an array of Strings
  * @param array Array to be resized
  * @param size Desired size for the array
  * @return A reference to the newly sized array
  */
public static String[] resize(String[] array, int size) {
  String[] newArray = new String[size];
  // Since the size could be less than array.length, we need to make sure
  //  we only go up to the smaller of the two values.
  for(int i=0; i<array.length && i<size; ++i) {
    newArray[i] = array[i];
  }
  return newArray;
}

Wait, wouldn't it be nice if we could just start out with an empty array and then just add elements to it as needed? Keep reading because the girls and boys at Sun Microsystems have already fulfilled your wildest dreams!¹⁾

Interfaces

The Java language includes a concept known as interfaces.
It's a fairly simple concept that we'll need in order to better understand collection types that are part of the Java Collections Framework.
An interface is basically a promise or contract.
An interface is a list of method signatures (method name, parameters passed to the method, and the type returned by the method, if anything).
- When a class is declared, it may promise to implement the interface.
- You've already seen interfaces in action...
  - An event handler class must implement an interface (the EventListener interface or some other interface related to it).
  - A class declaration like the following promises that the class will implement the ActionListener interface:
```
private class ButtonEventHandler implements ActionListener {
```
  - The ActionListener interface specifies that the following method must be implemented:
```
  public void actionPerformed(ActionEvent event)
```
  - The compiler makes sure that the ButtonEventHandler class fulfills its promise by refusing to compile unless the ButtonEventHandler class implements that method.
In much the same way as we can create a reference to an object, we can create a reference to an interface.
The reference acts as the gatekeeper for accessing the object to which the reference points. Consider the following code:
```
  String word = new String("nonsense");
  CharSequence charSeq = word;
```
- The first line creates a reference to a String and makes it point to a newly created String object.
- The second line creates a reference to a CharSequence and makes it point to the same String object as word.
- Since the String class implements the CharSequence interface, the second line is a valid statement.
- Both word and charSeq refer to the same object, but we can only access methods known to the CharSequence interface when using the charSeq reference.
- The CharSequence consists of four methods:
- The following indicates which lines are illegal. All of the legal lines of code function identically regardless of whether the method is called through word or charSeq.
```
  word.toString();
  word.endsWith("sense");
  word.length();
  word.subSequence(1, 3);
  word.substring(1, 3);
  charSeq.toString();
  charSeq.endsWith("sense");  // ILLEGAL
  charSeq.length();
  charSeq.subSequence(1, 3);
  charSeq.substring(1, 3);    // ILLEGAL
```

Java Collections Framework

Because manipulating collections of objects is such a common task, Sun provides the Java Collections Framework.
The framework contains a number of interfaces and classes that various ways of storing and interacting with collections of data.

List Interface

The List<E> 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.
Some relevant methods include:
- add(E) — adds an object to the end of the list.
- clear() — removes all elements from the list.
- contains(E) — returns true if the specified element is found in the list.
- get(int) — returns the element at the specified location in the list.
- isEmpty() — returns true if no elements are in the list.
- set(int, E) — replaces the element at the specified location with the specified element.
- size() — returns the number of elements in the list.
The following method does some silly stuff with a list of strings:
```
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:
```
List<String> words = new List<String>();
```

List Implementations

The JCF provides a few classes that implement the List<E> interface.

The ArrayList<E> class.

This is basically a souped up array.
You can think of this class as containing one field that is a reference to an array and a number of methods that implement the List<E> interface.

The actual ArrayList<E> implementation is more involved, but a simplified version of the ArrayList<E> class might look something like this:

public class ArrayList<E> implements List<E> {
  private E[] array;
  
  @Override
  public boolean isEmpty() {
    return (null == array);
  }
  
  @Override
  public void clear() {
    array = null;
  }
  
  @Override
  public E get(int index) {
    return array[index];
  }
  
  @Override
  public E set(int index, E value) {
    E retVal = array[index];
    array[index] = value;
    return retVal;
  }
  
  @Override
  public int size() {
    return array.length;
  }
  
  @Override
  public boolean contains(Object target) {
    boolean found = false;
    for(int i=0; !found && i<array.length; ++i) {
      found = array[i].equals(target);
    }
    return found;
  }
  
  @SuppressWarnings("unchecked")
  @Override
  public boolean add(E value) {
    E[] newArray = (E[])new Object[array.length+1];
    for(int i=0; i<array.length; ++i) {
      newArray[i] = array[i];
    }
    newArray[newArray.length-1] = value;
    array = newArray;
    return true;
  }
  
  // Other methods of the List interface ...
  
} // end of ArrayList class

Again, this is a very simplified version of what really goes on.

The LinkedList<E> class.
- This class also implements the List interface.
- Although you can interact with the class in the same way you would interact with an ArrayList<E>, the way that each class implements the functionality described by the List interface is quite different.
- The LinkedList<E> doesn't use an array to store the data internally.
- We will study the internal structure of the LinkedList<E> later in this course.
- For now, it is sufficient to know that the LinkedList<E> class implements the List interface.
Depending on your application, you may find that it is better to use a ArrayList<E> while other times it is better to use an LinkedList<E>.
Since both class implement the List 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:

List<String> words = new ArrayList<String>();
// do a bunch of .add calls to populate the list
silly(words);
  
words = new LinkedList<String>();
// do a bunch of .add calls to populate the list
silly(words);

Collection Interface

The Collection<E> interface is more general that the List<E> interface.
In fact, the List interface extends the Collection interface, so, if you know the List interface, you already know the Collection interface.
The main difference is that there are some methods declared by the List interface that are not part of the Collection interface. In particular: the Collection interface does not declare get and set methods.
If you don't need get and set, you're better off using a Collection reference instead of a List reference. That way you have an even wider choice of classes that implement the interface.
Classes that implement the Collection interface but not the List interface include:
We'll discuss the first two later in the course.

¹⁾assuming your wildest dreams are about easily adding elements to a collection of items

Last modified: Monday, 15-Feb-2016 23:33:18 CST

List Interface

The List is implemented by both the ArrayList and the LinkedList.

Arrays

Interfaces

Java Collections Framework

List Interface

List Implementations

Collection Interface

The `List` is implemented by both the `ArrayList` and the `LinkedList`.