Concrete Collections

Linked Lists

We used arrays and their dynamic cousin, the Vector class, for many examples in Volume 1. However, arrays and vectors suffer from a major drawback. Removing an element from the middle of an array is very expensive since all array elements beyond the removed one must be moved toward the beginning of the array (see Figure 2-4). The same is true for inserting elements in the middle.

Figure 2-4: Removing an element from an array

Another well-known data structure, the linked list, solves this problem. Whereas an array stores object references in consecutive memory locations, a linked list stores each object in a separate link. Each link also stores a reference to the next link in the sequence. In the Java programming language, all linked lists are actually doubly linked, that is, each link also stores a reference to its predecessor (see Figure 2-5).

Figure 2-5: A doubly linked list

Removing an element from the middle of a linked list is an inexpensive operation--only the links around the element to be removed need to be updated (see Figure 2-6).

Figure 2-6: Removing an element from a linked list

Perhaps you once had a course in data structures where you learned how to implement linked lists. You may have bad memories of tangling up the links when removing or adding elements in the linked list. If so, you will be pleased to learn that the Java collections library supplies a class LinkedList ready for you to use.

The LinkedList class implements the Collection interface. You can use the familiar methods to traverse a list. The following code example prints the first three elements of a list, adds three elements, and then removes the third one.

LinkedList staff = 
     new LinkedList();
staff.add("Angela");
staff.add("Bob");
staff.add("Carl");
Iterator iter = staff.iterator();
for (int i = 0; i < 3; i++)
   System.out.println(iter.next());
iter.remove(); // remove last 
//visited element

interface ListIterator 
        extends Iterator
{  void add(Object);
   . . .
}

In addition, the ListIterator interface has two methods:

Object previous()
boolean hasPrevious()

The listIterator method of the LinkedList class returns an iterator object that implements the ListIterator interface.

ListIterator iter = 
         staff.listIterator();

ListIterator iter = 
       staff.listIterator();
iter.next();
iter.add("Juliet");

Figure 2-7: Adding an element to a linked list

If you call the add method multiple times, the elements are simply added in the order in which you supplied them. They all get added in turn before the current iterator position.

When you use the add operation with an iterator that was freshly returned from the listIterator method and that points to the beginning of the linked list, the newly added element becomes the new head of the list. When the iterator has passed the last element of the list (that is, when hasNext returns false), the added element becomes the new tail of the list. If the linked list has n elements, there are n + 1 spots for adding a new element. These spots correspond to the n + 1 possible positions of the iterator. For example, if a linked list contains three elements A, B, and C, then the four possible positions (marked as |) for inserting a new element are:

|ABC
A|BC
AB|C
ABC|

Unlike the add method, which only depends on the iterator position, the remove method depends on the iterator state.

Finally, there is a set method that replaces the last element returned by a call to next or previous with a new element. For example, the following code replaces the first element of a list with a new value:

ListIterator iter = list.listIterator();
Object oldValue = iter.next(); // returns first element
iter.set(newValue); // sets first element to newValue

LinkedList list = . . .;
ListIterator iter1 = 
        list.listIterator();
ListIterator iter2 = 
        list.listIterator();
iter1.next();
iter1.remove();
iter2.next(); 
// throws ConcurrentModificationException

To avoid concurrent modification exceptions, follow this simple rule: You can attach as many iterators to a container as you like, provided that all of them are only readers. Alternatively, you can attach a single iterator that can both read and write.

Concurrent modification detection is achieved in a simple way. The container keeps track of the number of mutating operations (such as adding and removing elements). Each iterator keeps a separate count of the number of mutating operations that it was responsible for. At the beginning of each iterator method, the iterator simply checks whether its own mutation count equals that of the container. If not, it throws a ConcurrentModificationException.

This is an excellent check and a great improvement over the fundamentally unsafe iterators in the C++ STL framework. Note, however, that it does not automatically make collections safe for multithreading. We discuss thread safety issues later in this chapter.

Now you have seen the fundamental methods of the LinkedList class. You use a ListIterator to traverse the elements of the linked list in either direction and to add and remove elements.

As you saw in the preceding section, there are many other useful methods for operating on linked lists that are declared in the Collection interface. These are, for the most part, implemented in the AbstractCollection superclass of the LinkedList class. For example, the toString method invokes toString on all elements and produces one long string of the format [A, B, C]. This is handy for debugging. Use the contains method to check whether an element is present in a linked list. For example, the call staff.contains("Harry") returns true if the linked list already contains a string that is equal to theString "Harry". However, there is no method that returns an iterator to that position. If you want to do something with the element beyond knowing that it exists, you have to program an iteration loop by hand.

 
LinkedList list = new LinkedList();
list.add(list); 
// add list to itself
String contents = list.toString(); 
// dies with infinite recursion

The library also supplies a number of methods that are, from a theoretical perspective, somewhat dubious. Linked lists do not support fast random access. If you want to see the nth element of a linked list, you have to start at the beginning and skip past the first n - 1 elements first. There is no shortcut. For that reason, programmers don't usually use linked lists in programming situations where elements need to be accessed by an integer index.

Nevertheless, the LinkedList class supplies a get method that lets you access a particular element:

Object obj = list.get(n);

You should never use this illusory random access method to step through a linked list. The code

for (int i = 0; i < list.size(); i++)
   do something with list.get(i);
   

The list iterator interface also has a method to tell you the index of the current position. In fact, because Java iterators conceptually point between elements, it has two of them: the nextIndex method returns the integer index of the element that would be returned by the next call to next; the previousIndex method returns the index of the element that would be returned by the next call to previous. Of course, that is simply one less than nextIndex. These methods are efficient--the iterators keep a count of the current position. Finally, if you have an integer index n, then list.listIterator(n) returns an iterator that points just before the element with index n. That is, calling next yields the same element as list.get(n). Of course, obtaining that iterator is inefficient.

If you have a linked list with only a handful of elements, then you don't have to be overly paranoid about the cost of the get and set methods. But then why use a linked list in the first place? The only reason to use a linked list is to minimize the cost of insertion and removal in the middle of the list. If you only have a few elements, you can just use an array or a collection such as ArrayList.

We recommend that you simply stay away from all methods that use an integer index to denote a position in a linked list. If you want random access into a collection, use an array or ArrayList, not a linked list.

The program in Example 2-1 puts linked lists to work. It simply creates two lists, merges them, then removes every second element from the second list, and finally tests the removeAll method. We recommend that you trace the program flow and pay special attention to the iterators. You may find it helpful to draw diagrams of the iterator positions, like this:

|ACE   |BDFG
A|CE   |BDFG
AB|CE  B|DFG
. . .

System.out.println(a);

Example 2-1: LinkedListTest.java

import java.util.*;

public class LinkedListTest
{  public static void main(
                  String[] args)
   {  List a = new LinkedList();
      a.add("Angela");
      a.add("Carl");
      a.add("Erica");
      
      List b = new LinkedList();
      b.add("Bob");
      b.add("Doug");
      b.add("Frances");
      b.add("Gloria");
      
      // merge the words from b into a
      
      ListIterator aIter = a.listIterator();
      Iterator bIter = b.iterator();
      
      while (bIter.hasNext())
      {  if (aIter.hasNext()) aIter.next();
         aIter.add(bIter.next());
      }
      
      System.out.println(a);
      
      // remove every second 
      //word from b
      
      bIter = b.iterator();
      while (bIter.hasNext())
      {  bIter.next(); 
      // skip one element
         if (bIter.hasNext()) 
         {  bIter.next(); 
         // skip next element
            bIter.remove(); 
            // remove that element
         }
      }
      
      System.out.println(b);
      
      // bulk operation: remove all 
      //words in b from a
      
      a.removeAll(b);
      
      System.out.println(a);
      
   }
}
 

• ListIterator listIterator()
  returns a list iterator for visiting the elements of the list.
• ListIterator listIterator(int index)
  returns a list iterator for visiting the elements of the list whose first call to next will return the element with the given index. Parameters: index the position of the next visited element
• void add(int i, Object element)
  adds an element at the specified position.
  Parameters: index the position of the new element element the element to add
• void addAll(int i, Collection elements)
  adds all elements from a collection to the specified position.
  Parameters: index the position of the first new element
  elements the elements to add
• Object remove(int i)
  removes and returns an element at the specified position.
  Parameters: index the position of the element to remove
• Object set(int i, Object element)
  replaces the element at the specified position with a new element and returns the old element.
  Parameters: index the replacement position
  element the new element
• int indexOf(Object element)
  returns the position of the first occurrence of an element equal to the specified element, or -1 if no matching element is found. Parameters: element the element to match

• void add(Object element)
  adds an element before the current position. Parameters: element the element to add
• void set(Object element)
  replaces the last element visited by next or previous with a new element. Throws an IllegalStateException if the list structure was modified since the last call to next or previous.
  Parameters: element the new element
• boolean hasPrevious()
  returns true if there is another element to visit when iterating backwards through the list.
• Object previous()
  returns the previous object. Throws a NoSuchElementException if the beginning of the list has been reached.
• int nextIndex()
  returns the index of the element that would be returned by the next call to next.
• int previousIndex()
  returns the index of the element that would be returned by the next call to previous.

• LinkedList()
  constructs an empty linked list.
• LinkedList(Collection elements)
  constructs a linked list and adds all elements from a collection.
  Parameters: elements the elements to add
• void addFirst(Object element)
  
• void addLast(Object element)
  add an element to the beginning or the end of the list.
  Parameters: element the element to add
• Object getFirst()
• Object getLast()
  return the element at the beginning or the end of the list.
• Object removeFirst()
• Object removeLast()