Core Java 2, Volume II - Chapter 2: Collections

Print-friendly Version

Books Index

Concrete Collections

Rather than getting into more details about all the interfaces, we thought it would be helpful to first discuss the concrete data structures that the Java library supplies. Once you have a thorough understanding of what classes you will want to use, we will return to abstract considerations and see how the collections framework organizes these classes.

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

However, there is an important difference between linked lists and generic collections. A linked list is an ordered collection where the position of the objects matters. The LinkedList.add method adds the object to the end of the list. But you often want to add objects somewhere in the middle of a list. This position-dependent add method is the responsibility of an iterator, since iterators describe positions in collections. Using iterators to add elements only makes sense for collections that have a natural ordering. For example, the set data type that we discuss in the next section does not impose any ordering on its elements. Therefore, there is no add method in the Iterator interface. Instead, the collections library supplies a subinterface ListIterator that contains an add method:

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

Unlike Collection.add, this method does not return a boolean--it is assumed that the add operation always succeeds.

In addition, the ListIterator interface has two methods:

Object previous()
boolean hasPrevious()

--that you can use for traversing a list backwards. Like the next method, the previous method returns the object that it skipped over.

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

ListIterator iter = 
         staff.listIterator();

The add method adds the new element before the iterator position. For example, the code

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

skips past the first element in the linked list and adds "Juliet" before the second element (see Figure 2-7).

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|

NOTE: You have to be careful with the "cursor" analogy. The remove operation does not quite work like the BACKSPACE key. Immediately after a call to next, the remove method indeed removes the element to the left of the iterator, just like the backspace key would. However, if you just called previous, the element to the right is removed. And you can't call remove twice in a row.

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

As you might imagine, if an iterator traverses a collection while another iterator is modifying it, confusing situations can occur. For example, suppose an iterator points before an element that another iterator has just removed. The iterator is now invalid and should no longer be used. The linked list iterators have been designed to detect such modifications. If an iterator finds that its collection has been modified by another iterator or by a method of the collection itself, then it throws a ConcurrentModificationException. For example, consider the following code:

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

The call to iter2.next throws a ConcurrentModificationException since iter2 detects that the list was modified externally.

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.

NOTE: There is, however, a curious exception to the detection of concurrent modifications. The linked list only keeps track of structural modifications to the list, such as adding and removing links. The set method does not count as a structural modification. You can attach multiple iterators to a linked list, all of which call set to change the contents of existing links. This capability is required for a number of algorithms in the Collections class that we discuss 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.

CAUTION: The Java platform documentation points out that you should not add a reference of a collection to itself. Otherwise, it is easy to generate a stack overflow in the Java virtual machine¹. For example, the following call is fatal:

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

Naturally, this is not a situation that comes up in everyday programming.

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);

Of course, this method is not very efficient. If you find yourself using it, you are probably using the wrong data structure for your problem.

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);
   

is staggeringly inefficient. Each time you look up another element, the search starts again from the beginning of the list. The LinkedList object makes no effort to cache the position information.

NOTE: The get method has one slight optimization: if the index is at least size() / 2, then the search for the element starts at the end of the list.

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
. . .

Note that the call

System.out.println(a);

prints all elements in the linked list 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);
      
   }
}
 

java.util.List

• 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

java.util.ListIterator

• 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.

java.util.LinkedList

• 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()

remove and return the element at the beginning or the end of the list.

• Collection Interfaces
• Concrete Collections
• The Collections Framework
• Algorithms
• Legacy Collections