Skip to main content
IBM 
ShopSupportDownloads
IBM HomeProductsConsultingIndustriesNewsAbout IBM
IBM : developerWorks : Java : Education - online courses
Java Collections Framework
Download tutorial zip fileView letter-sized PDF fileView A4-sized PDF fileE-mail this tutorial to a friend
Main menuSection menuGive feedback on this tutorialPreviousNext
3. Collection interfaces and classes
  


List interface page 5 of 8


The List interface extends the Collection interface to define an ordered collection, permitting duplicates. The interface adds position-oriented operations, as well as the ability to work with just a part of the list.

UML Diagram for List Interface

The position-oriented operations include the ability to insert an element or Collection, get an element, as well as remove or change an element. Searching for an element in a List can be started from the beginning or end and will report the position of the element, if found.

  • void add(int index, Object element)
  • boolean addAll(int index, Collection collection)
  • Object get(int index)
  • int indexOf(Object element)
  • int lastIndexOf(Object element)
  • Object remove(int index)
  • Object set(int index, Object element)

The List interface also provides for working with a subset of the collection, as well as iterating through the entire list in a position-friendly manner:

  • ListIterator listIterator()
  • ListIterator listIterator(int startIndex)
  • List subList(int fromIndex, int toIndex)

In working with subList(), it is important to mention that the element at fromIndex is in the sublist, but the element at toIndex is not. This loosely maps to the following for-loop test cases:

for (int i=fromIndex; i<toIndex; i++) {
  // process element at position i
}

In addition, it should be mentioned that changes to the sublist (like add(), remove(), and set() calls) have an effect on the underlying List.

ListIterator interface

The ListIterator interface extends the Iterator interface to support bi-directional access, as well as adding or changing elements in the underlying collection.

UML Diagram for ListIterator Interface

The following source code demonstrates looping backwards through a list. Notice that the ListIterator is originally positioned beyond the end of the list (list.size()), as the index of the first element is 0.

List list = ...;
ListIterator iterator = list.listIterator(list.size());
while (iterator.hasPrevious()) {
  Object element = iterator.previous();
  // Process element
}

Normally, one doesn't use a ListIterator to alternate between going forward and backward in one iteration through the elements of a collection. While technically possible, calling next() immediately after previous() results in the same element being returned. The same thing happens when you reverse the order of the calls to next() and previous().

The add() operation requires a little bit of explanation also. Adding an element results in the new element being added immediately prior to the implicit cursor. Thus, calling previous() after adding an element would return the new element and calling next() would have no effect, returning what would have been the next element prior to the add operation.

ArrayList and LinkedList classes

There are two general-purpose List implementations in the Collections Framework: ArrayList and LinkedList. Which of the two List implementations you use depends on your specific needs. If you need to support random access, without inserting or removing elements from any place other than the end, then ArrayList offers the optimal collection. If, however, you need to frequently add and remove elements from the middle of the list and only access the list elements sequentially, then LinkedList offers the better implementation.

Both ArrayList and LinkedList implement the Cloneable interface. In addition, LinkedList adds several methods for working with the elements at the ends of the list (only the new methods are shown in the following diagram):

Partial UML Diagram for LinkedList Class

By using these new methods, you can easily treat the LinkedList as a stack, queue, or other end-oriented data structure.

LinkedList queue = ...;
queue.addFirst(element);
Object object = queue.removeLast();
LinkedList stack = ...;
stack.addFirst(element);
Object object = stack.removeFirst();

The Vector and Stack classes are historical implementations of the List interface. They will be discussed in Vector and Stack classes.

List usage example

The following program demonstrates the use of the concrete List classes. The first part creates a List backed by an ArrayList. After filling the list, specific entries are retrieved. The LinkedList part of the example treats the LinkedList as a queue, adding things at the beginning of the queue and removing them from the end.

import java.util.*;

public class ListExample {
  public static void main(String args[]) {
    List list = new ArrayList();
    list.add("Bernadine");
    list.add("Elizabeth");
    list.add("Gene");
    list.add("Elizabeth");
    list.add("Clara");
    System.out.println(list);
    System.out.println("2: " + list.get(2));
    System.out.println("0: " + list.get(0));
    LinkedList queue = new LinkedList();
    queue.addFirst("Bernadine");
    queue.addFirst("Elizabeth");
    queue.addFirst("Gene");
    queue.addFirst("Elizabeth");
    queue.addFirst("Clara");
    System.out.println(queue);
    queue.removeLast();
    queue.removeLast();
    System.out.println(queue);
  }
}

Running the program produces the following output. Notice that unlike Set, List permits duplicates.

[Bernadine, Elizabeth, Gene, Elizabeth, Clara]
2: Gene
0: Bernadine
[Clara, Elizabeth, Gene, Elizabeth, Bernadine]
[Clara, Elizabeth, Gene]

AbstractList and AbstractSequentialList classes

There are two abstract List implementations classes: AbstractList and AbstractSequentialList. Like the AbstractSet class, they override the equals() and hashCode() methods to ensure two equal collections return the same hash code. Two sets are equal if they are the same size and contain the same elements in the same order. The hashCode() implementation is specified in the List interface definition and implemented here.

Besides the equals() and hashCode() implementations, AbstractList and AbstractSequentialList provide partial implementations of the remaining List methods. They make the creation of concrete list implementations easier, for random-access and sequential-access data sources, respectively. Which set of methods you need to define depends on the behavior you wish to support. The following table should help you remember which methods need to be implemented. One thing you'll never need to provide yourself is an implementation of the Iterator iterator() method.

AbstractListAbstractSequentialList
unmodifiable

Object get(int index)
int size()

ListIterator listIterator(int index)
- boolean hasNext()
- Object next()
- int nextIndex()
- boolean hasPrevious()
- Object previous()
- int previousIndex()
int size()
modifiable

Object get(int index)
int size()
Object set(int index, Object element)

ListIterator listIterator(int index)
- boolean hasNext()
- Object next()
- int nextIndex()
- boolean hasPrevious()
- Object previous()
- int previousIndex()
int size()
ListIterator
- set(Object element)
variable-size and modifiable

Object get(int index)
int size()
Object set(int index, Object element)
add(int index, Object element)
Object remove(int index)

ListIterator listIterator(int index)
- boolean hasNext()
- Object next()
- int nextIndex()
- boolean hasPrevious()
- Object previous()
- int previousIndex()
int size()
ListIterator
- set(Object element)
ListIterator
- add(Object element)
- remove()

As the Collection interface documentation states, you should also provide two constructors, a no-argument one and one that accepts another Collection.


Main menuSection menuGive feedback on this tutorialPreviousNext
PrivacyLegalContact