Using Collections with JDK 1.2

Print-friendly Version

Articles Index

This article identifies and describes some of the key features of collections, which include frameworks, algorithms, iterators, serialization, concurrency, how to use collections with legacy code, and so on.

Contents

• Collection Frameworks
• Types of Interfaces
• Algorithms
• Comparing Objects
• Iterators
• Serialization
• Exceptions
• Properties of Collections
• Synchronization
• Retrofitting Old Classes and Compatibility
• Programming Tips and API Design
• Performance
• Customization
• More Information

A collection is a group of related data elements, organized into a single object, with operations provided to manipulate the data. Java technology has always offered support for collections, for example via the Vector and Hashtable classes, but in JDK 1.2, a new framework for collections has been defined and implemented. The old classes can still be used, but the new preferred approach has significant advantages.

The advantages include:

• Reduced programming effort.
• Support for software reuse, in that data structures conforming to the collection interfaces are reusable in a wide variety of contexts and applications.
• Easier to design with APIs.
• Easier to pass collections between unrelated APIs.
• Increased program speed.
• Increased program quality (fewer bugs, easier maintenance).

Before getting into a lot of the details of how collections work, it's worth looking at a simple example:

  import java.util.*;

  public class intro1 {
     public static void main(String args[])
     {
       List list = new ArrayList();
       for (int i = 1; i <= 10; i++)
         list.add(i + " * " + i + " = " + i * i);
  
       Iterator iter = list.iterator();
       while (iter.hasNext())
         System.out.println(iter.next());
    }
  }

ArrayList is a collections class, something like Vector, that is used to store lists of objects, with random access. An iterator is used to traverse the list and retrieve the individual values, and operates similarly to the Enumeration interface already found in Java. The example accumulates a list of squares, like:

  5 * 5 = 25 

and displays it.

Other languages also have support for collections, such as the Standard Template Library found in C++.

Collection Frameworks

A collections framework is an architecture for defining and manipulating collections. However, this is a vague statement. To make it concrete, consider first the way in which ArrayList is defined:

  interface Collection {...}

  interface List extends Collection {...}

  abstract class AbstractCollection implements 
      Collection {...}

  abstract class AbstractList extends 
    AbstractCollection
      implements List {...}

  class ArrayList extends AbstractList {...}

Collection is a top-level interface that defines properties that all collections must have, for example, a size method that returns the number of elements currently in the collection.

List is another interface that extends Collection, and adds additional properties that define ordered lists, for example, the ability to retrieve an element based on an index, such as the 17th element.

AbstractCollection is an abstract class that starts to implement some of the functionality of collections. For example, the isEmpty member can be defined as:

public boolean isEmpty()
  {
    return size() == 0;
  }

and there's no need to re-implement this method in subclasses (though a subclass can if it wants to). The same idea applies to AbstractList; it implements much of the functionality of List.

ArrayList is last in the hierarchy, and is a class that can be instantiated and used in a real program. ArrayList is where the decision is made about underlying representation; in this case it's a Java array of Object elements. Many of the List methods are implemented at higher levels of the hierarchy, but a few must be implemented in this class, for example, the method that retrieves (get) an element based on a supplied index.

In this example, the interfaces provide contracts, that is, descriptions of what functionality is supported. They support manipulation of collections independently of the implementation details. For example, if a program has a List reference, the List can be implemented as an ArrayList, LinkedList, or RunArrayList (see below), but the operations on the list are performed using an identical set of operations in each case.

The abstract classes provide implementations of the interfaces, that is, implementations that can be reused or built on.

A third aspect of frameworks is algorithms, methods for performing useful computations on objects of some collection type. An example is sort:

  import java.util.*;
  
  public class sort1 implements Comparator {
  public int compare(Object o1, Object o2)
  {
    String s1 = (String)o1;
    String s2 = (String)o2;
  
    return s1.toLowerCase(
    ).compareTo(s2.toLowerCase());
  }
  
  public static void main(String args[])
  {
      List list = new ArrayList();
  
      list.add("abc");
      list.add("DEF");
      list.add("ghi");
  
      // standard sort
  
      Collections.sort(list);
      Iterator iter = list.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
  
      // sort, ignoring case
  
      Collections.sort(list, new sort1());
      iter = list.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
    }
  }

In the above example an ArrayList object is sorted, using both the natural sorting order, and using a specified Comparator.

The hierarchy of interfaces and classes shown above follows a particular naming convention. For example, AbstractList is an abstract class that partially implements List, and HashMap is a Map implemented as a hash table. A more complete list of these names is:

• ArrayList: List implemented via an array
• LinkedList: List implemented as a linked structure
• HashSet: Set implemented via a hash table
• TreeSet: SortedSet implemented as a tree
• HashMap: Map implemented via a hash table
• TreeMap: SortedMap implemented as a tree

Of these, ArrayList, HashMap, and HashSet are considered the preferred primary implementations.

Types of Interfaces

So what kinds of interfaces are available in collections? The various types are as follows:

• Collection: a group of elements
• Set: a group of elements with no duplicates
• SortedSet: like Set, except the elements are kept in sorted order
• List: ordered collection or sequence
• Map: an object that maps keys to values, with no duplicate keys
• SortedMap: like Map, except the keys are kept in sorted order

These are known as core collection interfaces.

The Collection interface itself does not enforce any policy, such as no duplicates or ordering. Such policies are enforced by subinterfaces. Also, it's possible to define your own subinterface if you have need to establish a different set of policies. Note that Map is at the root of a distinct interface hierarchy; a map is not really a collection of elements, but a mapping of keys to values.

The kinds of methods that are supported depend on the particular interface. Some of the methods common to all collections are:

• add: add a new element
• remove: remove an element
• size: number of elements currently represented
• isEmpty: whether the collection is currently empty
• iterator: obtain an Iterator object
• contains: check whether a collection contains an element
• toArray: return an Object[ ] with all the collection's elements

while operations on lists include additional functionality:

• get: get an element based on an index
• indexOf: find the index of a specified element

and maps have functionality to get a list of all the keys contained in the map object.

The earlier example showed an ArrayList. Here is an example that uses a HashMap:

  import java.util.*;
  
  public class map1 {
    public static void main(String args[])
    {
      Map hm = new HashMap();
      hm.put("Mary", "123-4567");
      hm.put("Larry", "234-5678");
      hm.put("Mary", "456-7890");
      hm.put("Felicia", "345-6789");
  
      Iterator iter = hm.entrySet().iterator();
      while (iter.hasNext()) {
        Map.Entry e = (Map.Entry)iter.next();
        System.out.println(e.getKey() + " "
            + e.getValue());
      }
    }
  }

Note that each entry in the map contains two values; one for the key and the other for the value. A map cannot contain any duplicates, and no ordering is imposed. When this program is run, output is like:

  Larry 234-5678
  Felicia 345-6789
  Mary 456-7890

with the first value for "Mary" overwritten, and with the iterator retrieval order different from the order in which the elements were added to the map.

An example of using HashSet:

  import java.util.*;
  
  public class set1 {
    public static void main(String args[])
    {
      Set hs = new HashSet();
      hs.add("1");
      hs.add("2");
      hs.add("2");
      hs.add("3");
  
      Iterator iter = hs.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
    }
  }

with output of:

  3
  2
  1

Algorithms

An example of using sort was presented above. Note that in the example the actual sorting is done via a static method Collections.sort, that operates on Lists. The alternative to static methods would be to have a sort method declared in the top-level List interface, but this approach requires that all implementers of List define this method, and so the alternative of static methods was chosen, as a means of keeping the interface small.

Similar to sorting, Collections.binarySearch is used to search an ordered list. For example, this program generates random numbers and adds them to a list if not already there:

  import java.util.*;
  
  public class search1 {
    public static void main(String args[])
    {
      List lst = new ArrayList();
      Random rn = new Random();
  
      for (int i = 1; i <= 25; i++) {
        int n = (int)(rn.nextFloat() * 10 + 1);
        Integer ival = new Integer(n);
        int pos = 
          Collections.binarySearch(lst, ival);
        if (pos < 0)
          lst.add(-pos-1, ival);
      }
      Iterator iter = lst.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
    }
  }

Collections.binarySearch returns a position indicating where a not-found element would be inserted. This position is used to add the element after an unsuccessful search.

Shuffling is another algorithm, that might be considered the opposite of sorting. It takes a list and scrambles it using an internally-supplied random number generator, for example:

  import java.util.*;
  
  public class shuffle1 {
  public static void main(String args[])
  {
      List list = new ArrayList();
  
      list.add("abc");
      list.add("def");
      list.add("ghi");
      list.add("jkl");
  
      Collections.shuffle(list);
  
      Iterator iter = list.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
    }
  }

If you want to exercise finer control over the shuffling process, you can also specify a Random object.

Another algorithm is list reversal:

  import java.util.*;
  
  public class reverse1 {
    public static void main(String args[])
    {
      List list = new ArrayList();
      for (int i = 1; i <= 10; i++)
        list.add(
        i + " * " + i + " = 
          " + i * i);
  
      Collections.reverse(list);
  
      Iterator iter = list.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
    }
  }

Most of the algorithms operate on lists, because of the assumption of ordering. For example, a set has no order imposed on its elements, and so reversing a set doesn't make any sense. But one algorithm applicable to all types of collections is min/max:

  import java.util.*;
  
  public class max1 {
    public static void main(String args[])
    {
      Set hs = new HashSet();
      hs.add("1");
      hs.add("2");
      hs.add("3");
      hs.add("2");
  
      Iterator iter = hs.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
  
      System.out.println("max = " 
        + Collections.max(hs));
    }
  }

The maximum value printed in this example is 3.

Collections.fill is used to overwrite elements in a list with the specified element, serving to re-initialize a list. Collections.copy copies one list to another, overwriting elements. The copy operation is different from making a brand-new copy of a list, which can be done via constructor:

  import java.util.*;
  
  public class copy1 {
    public static void main(String args[])
    {
      List list = new ArrayList();
      for (int i = 1; i <= 10; i++)
        list.add(i + " * " + i 
          + " = " + i * i);
  
      List copy = new ArrayList(list);
  
      Iterator iter = copy.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
    }
  }

In C++ this would be called a "copy constructor". The list copy is shallow, and references the same underlying elements as the original list.

Comparing Objects

Suppose you have the following code:

  import java.util.*;
  
  class test {
    private int x;
    public test(int i) {x = i;}
  }
  
  public class compare1 {
    public static void main(String args[])
    {
      List list = new ArrayList();
      list.add(new test(5));
      list.add(new test(10));
      Collections.sort(list);
    }
  }

and you run it. What happens? This example gives an exception, caused by failure to specify any means of comparing instances of the test class. Such comparisons are done when sorting, and there's no automatic way to order objects.

One way of ordering is illustrated in the sort example above, using the Comparator interface. Another approach is to use the Comparable interface, for example:

  import java.util.*;
  
  class test implements Comparable {
    private int x;
    public test(int i) {x = i;}
    public int compareTo(Object o)
    {
      int val = ((test)o).x;
      if (x < val)
        return -1;
      else if (x > val)
        return 1;
      else
        return 0;
    }
  }
  
  public class compare2 {
    public static void main(String args[])
    {
      List list = new ArrayList();
      list.add(new test(5));
      list.add(new test(10));
      Collections.sort(list);
    }
  }

The Comparator interface specifies a compare method that takes two Object arguments, and returns a value -1, 0, or 1 to indicate the ordering of the objects. A class that implements Comparator may have a dummy object created, solely for the purpose of passing the object to a method for purposes of controlling comparisons. The form of the comparison call is thus:

  dummy.compare(obj1, obj2)

In contrast, Comparable is more "built in" to a class, such that the form of a call is:

  obj1.compareTo(obj2)

Comparator is more flexible than Comparable but Comparable is a better choice when the objects to be compared have a "natural" ordering. Classes like String, and wrapper classes such as Integer, all implement the Comparable interface, and there's no need to use Comparator for comparing objects of these types, unless you wish to override the natural ordering.

The Comparable interface also implies a more restrictive sort of ordering, for example the requirement that the property of transitivity be met:

 x > y && y > z => x > z

Iterators

Several of the examples above demonstrate the use of iterators, to retrieve elements in turn. One issue that comes up with iterators is this: what happens if you modify a collection while simultaneously iterating over it? An example is:

  import java.util.*;
  
  public class iterator1 {
    public static void main(String args[])
    {
      List list = new ArrayList();
      list.add("abc");
      list.add("def");
      list.add("ghi");
  
      ListIterator iter1 = list.listIterator();
      boolean first = true;
      while (iter1.hasNext()) {
        System.out.println(iter1.next());
        //list.add("xyz");
        if (first) {
          iter1.add("xyz");
          first = false;
        }
      }
    }
  }

If the obvious approach of adding a new element is followed, as illustrated by the commented-out line, then an exception is thrown (ConcurrentModificationException). And the exception is immediately triggered, a property known as fail-fast iterators. Fail-fast is much cleaner than having a failure at some indeterminate future point.

But there is a way to avoid this failure, and that is to effect the modification via the iterator itself, as the example illustrates. That is, add is called on the iterator instead of on the list that the iterator is traversing. This allows the modification to be done in an orderly way.

The Iterator interface itself does not support adding additional elements, but simply allows for the last element returned by the iterator to be removed from the collection. But a subinterface of Iterator, ListIterator, supports add, set, and remove, and also allows for the list to be traversed backwards. For example:

  import java.util.*;
  
  public class iterator2 {
    public static void main(String args[])
    {
      List list = new ArrayList();
      list.add("abc");
      list.add("def");
      list.add("ghi");
  
      ListIterator iter = 
        list.listIterator(list.size());
      while (iter.hasPrevious())
        System.out.println(iter.previous());
    }
  }

Output is:

  ghi
  def
  abc

Serialization

Serialization of collection objects is supported in the usual way. For example, the following two programs write a HashMap object to a file test.ser and then restore it:

  import java.io.*;
  import java.util.*;
  
  public class serial1 {
    public static void main(String args[])
    {
      Map hm = new HashMap();
      hm.put("Mary", "123-4567");
      hm.put("Larry", "234-5678");
      hm.put("Mary", "456-7890");
      hm.put("Felicia", "345-6789");
  
      try {
        FileOutputStream fos =
            new FileOutputStream("test.ser");
        ObjectOutputStream oos =
            new ObjectOutputStream(fos);
        oos.writeObject(hm);
        oos.close();
      }
      catch (Throwable e) {
        System.err.println(e);
      }
    }
  }

  import java.io.*;
  import java.util.*;

  public class serial2 {
    public static void main(String args[])
    {
      Map hm = null;
  
      try {
        FileInputStream fis =
           new FileInputStream("test.ser");
        ObjectInputStream ois =
           new ObjectInputStream(fis);
        hm = (Map)ois.readObject();
        ois.close();
      }
      catch (Throwable e) {
        System.err.println(e);
      }
  
      if (hm != null) {
        Iterator iter = hm.entrySet().iterator();
        while (iter.hasNext()) {
          Map.Entry e = (Map.Entry)iter.next();
          System.out.println(e.getKey() + " "
             + e.getValue());
        }
      }
    }
  }

Exceptions

ConcurrentModificationException was mentioned above in connection with iterators. Another type of exception is UnsupportedOperationException. A subclass of, for example, AbstractList, is not required to re-implement all methods. For example, if the implementation is of an unmodifiable list, then the add, remove, and set methods are not needed. The implementations of these in AbstractList throw the exception UnsupportedOperationException, and a class like ArrayList, that supports modification, overrides these methods.

Properties of Collections

The discussion on exceptions leads to another topic, that of collection properties. One important property is fixed-size:

  import java.util.*;
  
  public class wrapper2 {
    public static void main(String args[])
    {
      String list1[] = {"abc", 
        "def", "ghi"};
  
      List list2 = Arrays.asList(list1);
  
      //list2.add("xyz");
  
      list2.set(1, "xyz");
  
      for (int i = 0; i < list1.length; i++)
        System.out.println(list1[i]);
    }
  }

Arrays.asList takes a conventional array and turns it into a list, so that the array elements can be manipulated via list operations. Such a list is fixed-size, and cannot be extended via add (which causes an UnsupportedOperationException). But elements in the list can be modified, just like a regular array. Arrays.asList is called a convenience implementation.

Another property is unmodifiable:

  import java.util.*;
  
  public class wrapper1 {
    public static void main(String args[])
    {
      List list = new ArrayList();
      list.add("abc");
      list.add("def");
      list.add("ghi");
  
      list = Collections.unmodifiableList(list);
  
      list.add("xyz"); 
      // triggers exception
    }
  }

In this example, the list has a wrapper put on it, and from then on is not modifiable at all. A wrapper takes a collection and returns another collection, one with particular properties imposed on it. Collections.unmodifiableList is a wrapper implementation.

Synchronization

Another example of using wrappers concerns synchronization. Collections classes are not by default thread-safe (in contrast to the existing Vector implementation). If you want to make them so, you can use the following idiom:

  import java.util.*;
  
  public class sync1 extends Thread {
    public static void main(String args[])
    {
      List lst = new ArrayList();
      lst.add("abc");
      lst.add("def");
      lst.add("ghi");
  
      lst = Collections.synchronizedList(lst);
  
      synchronized (lst) {
        Iterator iter = lst.iterator();
        while (iter.hasNext())
          System.out.println(iter.next());
      }
    }
  }

Collections.synchronizedList turns a list into a synchronized one, for purposes of adding and removing elements. An explicit synchronized call must be used for list iteration, because iteration is a multistep process (repeatedly calling hasNext and then next).

Retrofitting Old Classes and Compatibility

You may be convinced by now that collections are a good thing, but what if you're trying to maintain a lot of old code that uses Hashtable and Vector and Enumeration and so on, or that even uses simple arrays to represent groupings of elements?

One answer to this question is to note that some of the old classes, for example Vector, have been retrofitted to work with the collections framework. Vector is now a subclass of AbstractList, and implements List. It's still better to use ArrayList if you can, but Vector will continue to work.

Another answer is to say that the collections system has a number of features in it to convert old to new and vice versa. The following example illustrates some of the conversion paths:

  import java.util.*;
  
  public class retro1 {
    public static void f1(Vector vec)
    {
      for (int i = 
      0; i < vec.size(); i++)
        System.out.println(
        vec.elementAt(i));
    }
  
    public static void f2(List list)
    {
      Iterator iter = list.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
    }
  
    public static void main(String args[])
    {
      List list1 = new ArrayList();
      list1.add("abc");
      list1.add("def");
      list1.add("ghi");
  
      // ArrayList -> Vector
  
      f1(new Vector(list1));
  
      // ArrayList -> String[]
  
      String slist[] =
          (String[])list1.toArray(new String[0]);
      for (int i = 0; i < slist.length; i++)
        System.out.println(slist[i]);
  
      // ArrayList -> Enumeration
  
      Enumeration e = 
      Collections.enumeration(list1);
      while (e.hasMoreElements())
        System.out.println(e.nextElement());
  
      // String[] -> List
  
      String list2[] = 
        new String[]{"abc", 
        "def", "ghi"};
      f2(Arrays.asList(list2));
    }
  }

You might also have an old legacy API, one that implements collections in some totally different way. One solution to this issue is to use an adapter class that implements one of the core collection interfaces, and translates method calls found in that interface into your old API methods. In other words, intercept and translate calls.

Programming Tips and API Design

There are several rules of thumb to consider when using collections.

One rule is to program in terms of interface types rather than implementation types. For example:

  List lst = new ArrayList();

is preferable to:

  ArrayList lst = new ArrayList();

because it lessens dependence on particular implementations. For instance, ArrayList might later change to LinkedList, or a program might come to depend on added methods found only in ArrayList and not in the List interface.

Another rule, especially applicable when passing collection types as parameters to some called method, is to use the least specific type, for example, Collection instead of List, or List instead of ArrayList. This promotes generality and again works against depending on added methods.

For method return types, it's acceptable and even desirable to use specific implementation types. For example, ArrayList has very different performance characteristics than LinkedList, and because of this, the user of a method needs to know just what type of data structure is being returned. The return type can always be converted to a more general type, for example:

 ArrayList f() {...}

  void g()
  {
    List lst = f();
  }

Performance

The sorting and searching algorithms have execution performance proportional to N * log(N) and log2(N) respectively. Sorting is done by mergesort, which is stable, that is, does not reorder equal elements, and its performance is guaranteed not to be worse than N * log(N) (which quicksort cannot guarantee).

ArrayList is implemented in terms of an underlying array of objects, and so is space efficient with constant time positional access (random access). By contrast, LinkedList used a linked structure, and so requires more space, and is slow at random access. But it comes out ahead in cases where you are doing heavy editing (adding and removing elements) in the middle of the list.

HashSet is much faster than TreeSet (constant vs. log(N)), but does not offer any guarantees on ordering, and similarly for HashMap and TreeMap.

One performance tip is to use iterators whenever you can to access the elements of a list, rather than depending on positional access. This is a big gain, for example, if the underlying list is a LinkedList.

Customization

Wrappers, adapter classes, and convenience implementations, described above, illustrate several ways of customizing collections. But what if these are not adequate? What if for reasons of performance or desire for enhanced functionality you need to go further?

There are at least three alternatives available:

• Implement a core collection interface.
• Subclass a primary implementation such as ArrayList.

• Extend an abstract class such as AbstractList.

The first of these is beyond the scope of this paper. However, the second can be illustrated by a simple example, one that enforces a policy such that only String objects can be added to an ArrayList:

  import java.util.*;
  
  class StringArrayList extends ArrayList {
    public StringArrayList()
    {
      super();
    }
  
    // other constructors ...
  
    public boolean add(Object o)
    {
      if (o instanceof String)
        return super.add(o);
      else
        throw new UnsupportedOperationException();
    }
  
    // other add() and set() methods ...
  }
  
  public class extend1 {
    public static void main(String args[])
    {
      StringArrayList list = new StringArrayList();
      list.add("abc");
      list.add("def");
      list.add("ghi");
      //list.add(new Object());
  
      Iterator iter = list.iterator();
      while (iter.hasNext())
        System.out.println(iter.next());
    }
  }

This scheme works simply by intercepting calls and checking whether the element to be manipulated is an instance of String. The superclass (ArrayList) does all the work.

Another alternative, a much more ambitious illustration, is extending AbstractList to implement run-length encoding. Such encoding refers to efficiently representing adjacent identical elements. For example, a photograph, represented in a data structure, might have long runs of identical color elements that represent a stretch of blue sky.

RunArrayList is an implementation of List, based on extending AbstractList. It stores elements in slots, with each slot representing a range of contiguous element indices, with all indices in the slot referring to the same element.

When runs of identical elements with average length of 25 are inserted into a RunArrayList, the time and space requirements are only 5-10% of those required by ArrayList. When elements are inserted randomly, the worst case, RunArrayList requires about twice the time and space as ArrayList.

Here is the implementation of RunArrayList:

  import java.util.*;
  
  /*
  Implements List via a run-length encoding data 
  structure. The structure is divided into slots, 
  each slot representing   one or more contiguous 
  elements that are equivalent, using equals() for 
  comparison.
  
  The highest index for each slot is stored in the 
  "sublist" array, and the element values 
  themselves in "objlist".
  */
  
  public class RunArrayList extends AbstractList
      implements Cloneable, java.io.Serializable {
  
    // highest index for each slot
    private int sublist[];
  
    // element value for each slot
    private Object objlist[];
  
    // highest current valid slot number
    private int currmax;
  
    // find the lowest valid index for a slot
    private int slotlo(int index)
    {
      return (index == 0 ? 0 : 
        sublist[index - 1] + 1);
    }
  
    // find the highest valid index for a slot
    private int slothi(int index)
    {
      return sublist[index];
    }
  
    // check whether two objects are equivalent 
    // (handles null)
    private static boolean 
      equals(Object obj1, Object obj2)
    {
      return (obj1 == null ? (obj2 == null) :
          obj1.equals(obj2));
    }
  
    // make room for a new slot, and push up others
    private void makeslot(int slot, int n)
    {
      if (currmax + n >= sublist.length)
        growlist();
  
      if (slot < currmax) {
        System.arraycopy(sublist, slot + 1,
            sublist, slot + 1 + n, currmax - slot);
        System.arraycopy(objlist, slot + 1,
            objlist, slot + 1 + n, currmax - slot);
      }
  
      currmax += n;
    }
  
    // grow the subscript and object lists
    private void growlist()
    {
      int len = sublist.length * 2;
  
      int newsub[] = new int[len];
      System.arraycopy(sublist, 0, newsub, 0,
          sublist.length);
      sublist = newsub;
  
      Object newobj[] = new Object[len];
      System.arraycopy(objlist, 0, newobj, 0,
          objlist.length);
      objlist = newobj;
    }
  
    // find the slot corresponding to an index
    private int findslot(int index)
    {
      int lo = 0;
      int hi = currmax;
  
      // binary search
  
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (index < slotlo(mid))
          hi = mid - 1;
        else if (index > slothi(mid))
          lo = mid + 1;
        else
          return mid;
      }
  
      // should never get here
  
      throw new Error();
    }
  
    // default constructor
    public RunArrayList()
    {
      sublist = new int[10];
      objlist = new Object[10];
      currmax = -1;
    }
  
    // constructor from a Collection
    public RunArrayList(Collection c)
    {
      this();
      Iterator iter = c.iterator();
      while (iter.hasNext())
        add(iter.next());
    }
  
    // number of elements currently in the list
    public int size()
    {
      return currmax == -1 ? 0 : 
        sublist[currmax] + 1;
    }
  
    // get an element value based on an index
    public Object get(int index)
    {
      if (index < 0 || index >= size())
        throw new IndexOutOfBoundsException();
  
      return objlist[findslot(index)];
    }
  
    // set an element to a new value
    public Object set(int index, Object element)
    {
      // remove then add
  
      Object obj = remove(index);
      add(index, element);
      return obj;
    }
  
    // add a new element, pushing up other elements
    public void add(int index, Object element)
    {
      int sz = size();
      if (index < 0 || index > sz)
        throw new IndexOutOfBoundsException();
  
      // adding to the end of the list?
  
      if (index == sz) {
        if (sz > 0 &&
            equals(objlist[currmax], element)) {
  
          // same as current last element
  
          sublist[currmax]++;
        }
        else {
  
          // not same, append to end
  
          if (currmax + 1 == sublist.length)
            growlist();
          currmax++;
          sublist[currmax] = sz;
          objlist[currmax] = element;
        }
      }
      else {
        int slot = findslot(index);
        int startincr = slot;
        if (!equals(objlist[slot], element)) {
          if (index == slotlo(slot)) {
  
            // push current slot up
  
            makeslot(slot, 1);
            sublist[slot + 1] =
                sublist[slot];
            sublist[slot] = index;
            objlist[slot + 1] =
                objlist[slot];
            objlist[slot] = element;
            startincr++;
          }
          else {
  
            // split current slot
  
            makeslot(slot, 2);
            sublist[slot + 2] =
                sublist[slot]; 
            sublist[slot + 1] = index;
            sublist[slot] = index - 1;
            objlist[slot + 2] =
                objlist[slot];
            objlist[slot + 1] = element;
            startincr += 2;
          }
        }
  
        // bump up max indices
  
        for (int i = startincr; i <= currmax; i++)
          sublist[i]++;
      }
    }
  
    // remove an element
    public Object remove(int index)
    {
      if (index < 0 || index >= size())
        throw new IndexOutOfBoundsException();
  
      int slot = findslot(index);
      Object obj = objlist[slot];
  
      // if this index is the only one in the slot,
      // delete the slot and shift down
  
      if (slotlo(slot) == slothi(slot)) {
        if (slot < currmax) {
          System.arraycopy(sublist, slot + 1,
              sublist, slot, currmax - slot);
          System.arraycopy(objlist, slot + 1,
              objlist, slot, currmax - slot);
        }
        objlist[currmax--] = null;
      }
  
      // decrement indices
  
      for (int i = slot; i <= currmax; i++)
        sublist[i]--;
  
      return obj;
    }
  }

And here is a test driver program that exercises RunArrayList:

  import java.util.*;
  
  public class testrl1 {
    static Random rn = new Random();
  
    // return a random integer, 
      lo <= integer <= hi
    static int rand(int lo, int hi)
    {
      return lo + (int)((hi - lo + 1) * 
        rn.nextFloat());
    }
  
    // do random operations on a RunArrayList 
    // and on an 
    // ArrayList, and periodically compare the 
    // results
    static void test()
    {
      List rl = new RunArrayList();
      List al = new ArrayList();
  
      final int LISTRNG = 5;
      final int LISTSZ = 50;
      for (int i = 1; i <= 10000000; i++) {
        if (i % 10000 == 0) {
          System.out.println(i);
          if (!al.equals(rl)) {
            System.out.println(
            "equals");
            break;
          }
        }
        int sz = al.size();
  
        // create an object to add, 
        and occasionally
        // make it null
  
        int r = rand(1, LISTRNG);
        Object obj = new Integer(r);
        if (rand(1, 25) == 1)
          obj = null;
  
        // bias toward adding if list is small,
        // else toward removing
  
        boolean add = 
          (sz <= LISTSZ && 
          rand(1, 3) >= 2
            || sz > LISTSZ && 
              rand(1, 3) < 2);
  
        // do a random get()
  
        if (sz > 0) {
          int pos = rand(0, sz - 1);
          Object o1 = al.get(pos);
          Object o2 = rl.get(pos);
          boolean b = (o1 == null ?
              (o2 == null) : o1.equals(o2));
          if (!b) {
            System.out.println("get");
            break;
          }
        }
  
        // add
  
        if (add) {
          int choice = rand(1, 3);
          if (choice == 1) {
            rl.add(obj);
            al.add(obj);
          }
          else if (choice == 2) {
            int pos = rand(0, sz);
            rl.add(pos, obj);
            al.add(pos, obj);
          }
          else if (sz > 0) {
            int pos = rand(0, sz - 1);
            rl.set(pos, obj);
            al.set(pos, obj);
          }
        }
  
        // remove
  
        else if (sz > 0) {
          int pos = rand(0, sz - 1);
          rl.remove(pos);
          al.remove(pos);
        }
      }
    }
  
    public static void main(String args[])
    {
      test();
    }
  }

This is a production-quality implementation, except perhaps for making a change to override the default iterator. The default uses get, which has time log2(N), and an overriding version could implement iterators in constant time.

More Information

For more information about collections, see the following references:

• The Java Collections Framework
  A paper giving the design rationale for collections.
• The Java Platform 1.2 Interface Collection
  A complete API description for collections.

Glen McCluskey has 15 years of experience, and has focused on programming languages since 1988. He consults in the areas of Java and C++ performance, testing, and technical documentation.