[ Home ] [ Up ] [ Collection Interface ] [ List Interface ] [ Iterator Interface ] [ ListIterator Interface ] [ ArrayList/Iterator Example ] [ LinkedList Example ] [ Stack Class ]

Another concrete implementation of a List is LinkedList:

Object
    AbstractCollection (implements Collection)
        AbstractList (implements List)
            AbstractSequentialList
                LinkedList
            ArrayList
            Vector
                Stack
        AbstractSet (implements Set)
            HashSet
            TreeSet (implements SortedSet)
    AbstractMap (implements Map)
        HashMap
        TreeMap (implements SortedMap)
        WeakHashMap
    Dictionary
        Hashtable (implements Map)
            Properties

LinkedList implements the List, as you might expect, as a linked list of nodes.  As a result, the performance of insertions into the middle of the list is expected to be better than that of the ArrayList.  On the other hand, the performance of retrieving a particular entry in the list is expected to be better for ArrayList than for LinkedList.

When designing an application, it is very important to choose an appropriate implementation for the performance demands of your application.  This choice can make a significant difference, sometimes by orders of magnitude!

Here's an example of how one could use an instance of class LinkedList.  It will run only under JDK 1.2 and beyond:

package examples;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class LinkedListExample
{
  public static void main(String[] args)
  {
    List list = new LinkedList();
    list.add("Mary");
    list.add("Frank");
    list.add("Joe");
    list.add("Sylvia");
    list.add("Vanessa");

    for (int i = 0; i < list.size(); i++)
    {
      String name = (String) list.get(i); // Note required cast
      System.out.println(i + ": " + name);
    }

    for (ListIterator iter = list.listIterator(); iter.hasNext(); )
    {
      String name = (String) iter.next(); // Note required cast
      System.out.println(name);
    }
  }
}

Note the fact that I have changed the code in a somewhat subtle way:

List list = new LinkedList();

as opposed to:

LinkedList list = new LinkedList();

Why did I do this?  Why might it be a good thing?

This program produces the output:

0: Mary
1: Frank
2: Joe
3: Sylvia
4: Vanessa
Mary
Frank
Joe
Sylvia
Vanessa

The output is exactly the same as for the earlier ArrayList example.

Again, note the two ways of obtaining the elements of the list:

• Access each element by its index, using the get(int index) method
• Access each element through an ListIterator object, supplied by the LinkedList. (Remember, ListIterator is an interface.)

This page was last modified on 02 October, 2007