There's also their helper, Iterator. You'll never really see a concrete implementation class for Iterator, because you always get an instance of Iterator from one of the collection classes .iterator() methods. But it actually is an interface.

Sometimes you'll need to use the meta-interface, which you can cast most List or Set implementations to:

(but not Map implementations, though they do seem to have most of the methods you need to meet the Collection interface requirements). Generally you'll run into this when you deal with somebody else's code that returns a Collection instead of something more specific.

And on rare occasions you'll use some specialized interfaces:

Every now and then you'll need the super-specialist interfaces:

Actually, I'm lying about LinkedList, it's not an interface, it's an implementation, but there are times when you have to deal with a LinkedList object as a LinkedList object. (See the LinkedList entry in the Excruciating Detail section, below).

Collection Class Summary

Note: I wrote this for JDK 1.4. A number of collections interfaces and implementations have been added in JDK 1.5 and JDK 1.6. I don't have time to compile a table as above, so for now I'll simply list them and point you at the Collections Framework Change Summary URLs.

JDK 1.5

http://java.sun.com/javase/6/docs/technotes/guides/collections/changes5.html

JDK 1.5 had a bunch of new stuff added, mostly about queues but also some java.util.concurrent related stuff.

• interface Queue
• interface BlockingQueue
• implementation PriorityQueue
• implementation ConcurrentLinkedQueue
• interface ConcurrentMap
• implementation AbstractQueue
• implementation LinkedBlockingQueue
• implementation ArrayBlockingQueue
• implementation PriorityBlockingQueue
• implementation DelayQueue
• implementation SynchronousQueue
• implementation ConcurrentHashMap
• implementation CopyOnWriteArrayList
• implementation CopyOnWriteArraySet
• implementation EnumSet
• implementation EnumMap

http://java.sun.com/javase/6/docs/technotes/guides/collections/changes6.html

"The primary theme of the API changes was better bi-directional collection access."

• interface Deque
• interface BlockingDeque
• interface NavigableSet
• interface NavigableMap
• interface ConcurrentNavigableMap
• implementation ArrayDeque
• implementation ConcurrentSkipListSet
• implementation ConcurrentSkipListMap
• implementation LinkedBlockingDeque
• implementation AbstractMap.SimpleEntry
• implementation AbstractMap.SimpleImmutableEntry

Some day I'd like to come back here and build a huge cross-indexed table of classes and methods, so you can see (for example) what methods LinkedList has that ArrayList doesn't have.

Before We Move On

A couple of tips before we get into the Excruciating Details. First, check out the utility methods on the Collections class. I mentioned them only slightly, but they provide a lot of handy little methods for manipulating collections

Second, why reinvent the wheel when other people have already reinvented it for you?

http://commons.apache.org/collections/

http://code.google.com/p/google-collections/

Also, these are kinda neat:

http://lavender.cime.net/~ricky/constrainedcollections.html

http://code.google.com/p/concurrentlinkedhashmap/

Excruciating Detail

Warning: Beyond This Point Lies Madness (or at least boredom)

Iterating, Enumerating and For Loop

Remember with arrays, you loop through the elements in the array using a for loop:

for (int i=0; i > someArray.length; i++) {
  System.out.println("" + someArray[i]) ;
}

You loop through an ArrayList by using the ArrayList.iterator() method to get an Iterator object, then using the Iterator object's .hasNext() and .next() methods.

You can think of the iterator as sort of an object-oriented version of the contents of the for loop parentheses:

(int i=0; i > someArray.length; i++)

At any given time, the Iterator knows whether its counter is past the end of the ArrayList, which you can find out by calling iterator.hasNext() (which returns a boolean). The iterator.next() method returns the next object and increments the counter.

List foo = new List(10) ;
foo.add("bar") ;
foo.add("bat") ;
foo.add("baz") ;
Iterator it = foo.iterator() ;
while (it.hasNext()) {
  String xyzzy = (String)it.next() ;
  System.out.println("" + xyzzy) ;
}

In fact, I've seen people advocate using both a for loop and an interator:

for (Iterator it = foo.iterator(); it.hasNext(); ) {  // 
  String xyzzy = (String)it.next() ;
  System.out.println("" + xyzzy) ;
}

Notice that the third chunk of the for loop (innards) is missing above. The normal pattern is (initialize; test; increment), but in this case we leave the increment portion blank, because calling it.next() in the body of the loop increments the iterator.

People argue about which way is better. Using the for loop limits the Iterator to inside the scope of the loop, which is nice. But there's a case that the while loop is more legible. Personally, while I favor legibility, I also favor expressing intent cearly. A while loop seems to say "we're going to loop until we find some condition we're looking for". A for loop seems to say "we're going to loop across the whole thing."

Sure, the contents of the for loop parentheses could be cleaner, but if your for loop parentheses are commonly so cluttered that you can't tell at a glance whether a given example is using an iterator or doing something clever, you should move your cleverness out to a separate method (unless that loop is a vital piece of high-performance code, which it rarely is).

Having said all that, I've never gotten in the habit of using for loops with iterators. I'll have to work on that.

Casting

Either way you go, notice that cast to (String). The ArrayList just contains objects, it has no way of knowing (or caring) what class the object has in it, so you have to cast the object to String when you assign it to a String variable. See the section on Wrapper Classes, below.

With the pre-1.2 Vector and Hashtable you use an Enumeration instead:

Vector foo = new Vector(10) ;
foo.add("bar") ;
foo.add("bat") ;
foo.add("baz") ;
Enumeration en = foo.elements() ;
while (en.hasMoreElements()) {
  String xyzzy = (String)en.nextElement() ;
  System.out.println("" + xyzzy) ;
}

If you're using a synchronized List that you got via java.util.Collections.synchronizedList(), you have to be careful when iterating. If some other thread modifies the List while you're iterating, your next call to an Iterator method will get you an exception.

LinkedList

LinkedList builds the list as a linked list (each object is stored inside a holder object, which has a reference to the next holder object and the previous holder object). For most List purposes, it works the exact same way as ArrayList:

List foo = new LinkedList();
String monday = "monday" ;
foo.add(monday) ;
String tuesday = "tuesday" ;
foo.add(tuesday) ;
String wednesday = "wednesday" ;
foo.add(wednesday) ; 
String thirdDay = (String)foo.get(3) ;
System.out.println(thirdDay) ;

There are one or two operations that you can only do with a LinkedList, they're not part of the standard List interface. They have to do with inserting and removing, and generally other stuff that you can do more easily with a LinkedList than with an ArrayList.

Also, besides the normal .iterator() method, LinkedList has a .listIterator() method, that returns a special ListIterator object instead of a normal Iterator. Okay, to be specific, ArrayList has a .listIterator() method too, but that returns a limited ListIterator that will throw UnsupportedOperationException at the drop of a hat, if you try to use ListIterator methods like remove(), set(), or add().

A ListIterator is sort of like a WonkaVator. With a normal Iterator, you can't mess with the contents of the List while you're iterating over it. With a ListIterator, you can iterate forward, or backwards, or remove elements while iterating.

Sets: HashSet and TreeSet

A Set is like a mathematical set - it's a bag of objects, and you can be sure that there's only one of each object in the bag. Unlike a List, it's not ordered, and if you try to add a value that's already in it, it ignores it.

Generally you'll use a HashSet, which is named that because it builds a Set by using a HashMap underneath.

A TreeSet builds a Set by using a "red-black tree", which means that the elements of the set will automatically be sorted when you add them - it'll add each object to the Set in the right place.

Synchronization

As mentioned repeatedly above, these collections are not synchronized, they are not thread-safe. If you need synchronization, you have two choices.

1) Use the java.lang.Collections.synchronizedFoo() methods on your collection (see the javadocs for java.lang.Collections for more info, also check the java tutorial).

2) Use a Vector or Hashtable instead.

Equality, Identity and Comparison

As said above, classes in the Collections API are supposed to use the .equals() method when they're checking for objects. If you do someArrayList.indexOf(object), or if you do someHashMap.containsKey(object), those classes should be calling object.equals() on each of their objects to see if that object matches.

For a great many objects in the core java API, .equals() does what you would hope it would do. For example, String.equals() returns true if both Strings represent the same sequence of letters. Integer.equals() returns true if both Integers represent the same int value:

HashMap foo = new HashMap() ;
Integer one = new Integer(1) ;
foo.put(one, "Right") ; 
Integer anotherOne = new Integer(1) ;
foo.put(anotherOne, "Wrong") ;
System.out.println(foo.get(one) ;

Unless I'm on crack (which I could be) this should print out: "Wrong". However, I've never particularly set out to break things in this way. Give it a try and see what happens (and email me to let me know).

However, .equals() doing what you hope it will do is NOT universally true. The default Object.equals() implementation just checks to see if the object reference you pass in is the same as that object's reference. This is seldom what you want. Check the javadocs and make sure it'll work the way you want it to work before you rely on it.

A related gotcha is that you have to be careful not to use == when you should use .equals(). For example, this does work:

int foo = 5 ;
int bar = 5 ;
if (foo == bar) {
  System.out.println("Yes!") ;
} else {
  System.out.println("No") ;
}

But this does not work:

Integer foo = new Integer(5) ;
Integer bar = new Integer(5) ;
if (foo == bar) {
  System.out.println("Yes!") ;
} else {
  System.out.println("No") ;
}

In this case, == just tells you whether foo and bar are the same object, not if they have the same int value.

For those cases where you actually do want to keep track of things by object reference, read up on IdentityHashMap.

If you're working with a class that doesn't have Comparable already implemented on it (see below), you can either add your own compareTo() method to that class, or you can put the comparison logic on a separate object that implements the Comparator interface. TreeMap uses a default Comparator that just calls the key objects' .compareTo() methods, but it may not be convenient for you to go muck about, adding compareTo() everywhere.

Many of the objects in java.lang already have Comparable implementations - see java.lang.Comparable in your javadocs for an up to date list, but in my javadocs (for 1.4.1) it says the following (but I've ordered the list according to how often I seem to run into these classes in coding):

• String
• Date
• Integer
• Float
• Long
• Short
• Double
• Byte
• Character
• File
• URI
• BigDecimal
• BigInteger
• IntBuffer
• LongBuffer
• ShortBuffer
• FloatBuffer
• DoubleBuffer
• ByteBuffer
• CharBuffer
• Charset
• CollationKey
• ObjectStreamField

Wrapper Classes

One big difference between a java array primitive and the Collection classes is that array works with primitive data types (int, boolean, char, byte, short, long, float, double). You can have, for example, an array of ints. Collection classes only know about objects (or more specifically, object references), so you can't have, for example, an ArrayList of boolean primitives, you need to use an ArrayList of Boolean object references.

Note: For each primitive type, there's a corresponding wrapper class in java.lang, e.g. java.lang.Integer, java.lang.Boolean, java.lang.Character, etc.

On the other end of the equation, another limitation of the Collections is that they only know about objects, not about classes, so your code has to remember what class of object you stuck in there, and cast the object reference back to that class when you pull it out.

So you have to do a lot of casting when you pull objects out of an ArrayList, and you have to be careful only to put the right (same) class of object into an ArrayList. And sometimes you have to wrap primitive values in their corresponding java.lang wrapper class before sticking it in, and then (after casting the object reference you get back from the ArrayList) pull the primitive value out and return it. Anywhere you're going to be doing a lot of this sort of stuff, it's a good idea to build a wrapper class that has the ArrayList as an instance variable, and makes sure you put the right class of object in, and casts the outgoing objects back to that class.

The same goes for any other Collections API class, of course.

One place where wrappers are essential is anywhere you're dealing with keys or values that are primitive types, i.e int, float, etc. These aren't "real" objects, so you can't just stick them in an ArrayList or HashMap. Instead, you have to wrap each one in an instance of its matching java.lang class (e.g. Integer or Float) and stick that in the Collection. Then when you pull the object out, you have to extract the primitive value from it. After you've done this a few times, you'll probably want to just create a wrapper class that does the dirty work for you.

Note: Java 1.5 has a feature called "autoboxing" that should make it a lot easier to use primitive types with Collection API classes.

Before I get into an example of how to do this yourself, there's also this library, developed by a regular on freenode.org's #java:

http://lavender.cime.net/~ricky/constrainedcollections.html

Here's an example of a wrapper for ArrayList, for handling File objects:

public class FileList() {
    public List fileList ;
    public List getFileList() {
        if (null == this.fileList) {
          this.fileList = new ArrayList() ;
        }
        return this.fileList
    }
    public void add(File file) {
        getFileList().add(file) ;
    }
    public File get(int index) {
        return (File)(getFileList().get(index)) ;
    }
    public boolean contains(File file) {
        return getFileList().contains(file) ;
    }
    public int indexOf(File file) {
        return getFileList().indexOf(file) ;
    }
    public int size() {
        return getFileList().size() ;
    }
}

Don't go overboard - add the delegation methods as you find you need them. I do this a fair bit, but I've never gone as far as creating a wrapper Iterator. It wouldn't be that hard - just have a wrapper.iterator() method that instantiates a special wrapper Iterator around the object returned by the ArrayList.iterator():

public class FileList {
 ...see example above...
    public FileListIterator iterator() {
        return new FileListIterator(getFileList().iterator()) ; 
    }
}
public class FileIterator {
    public FileIterator(Iterator iterator) {
      this.iterator = iterator ;
    }
    public Iterator iterator = null ; 
    public boolean hasNext() {
        return this.iterator.hasNext() ;
    }
    public File next() {
        return (File)(this.iterator.next()) ; 
    }
}

Unfortunately, because the whole point of our specialized FileList and FileIterator is to accept and return File class objects, we can't declare the classes themselves as implementing List and implementing Iterator.

Note: Java 1.5 has generics, which are supposed to make it easy to create typed Collections, so for example you'd create an ArrayList that just contains Strings. I haven't used it yet, so I couldn't comment on how well it works.

Meta Collection Objects

There are a few recurring patterns of Collection wrapper objects that I see:

If I find time, I'll come back here and put some boilerplate implementations of these up for your convenience. It's kinda annoying that they aren't part of the standard Collections API, but I guess they had enough to do by that point. Meanwhile, before you go reinventing the wheel, check the links above in the section Before We Move On to see if there's already one.

That's all (so far)

Please feel free to email me with comments, questions, clarifications, suggestions, or just plain old ego-stroking.

The java Collections API classes are the third or fourth most important thing you should learn about, when learning java. This is an attempt to give a really quick intro to them.

When the Collections API first came out, there were a zillion articles on it, but they all got bogged down in explaining the various Interfaces first. For example, this article at javaworld:

http://www.javaworld.com/javaworld/jw-11-1998/jw-11-collections-p2.html

The article is three pages long but the first page and a half are about interfaces!

It took me years to get around to really learning to use the Collections API, and even now I sometimes revert to old reflexes and use Vector or Hashtable instead, in a crunch. I still routinely run into otherwise-competent programmers who don't "get" Collections at all. So this tutorial is going to try a different approach. I'm going to ignore all those Interfaces and get right to the Concrete stuff (I can hear the screams of anguished OO gurus from here :-).

Note: However, I do recommend you take a look at the javaworld article after you finish reading this article. It also has a nifty little HTML table telling you what concrete Collection classes implement what Collection interfaces.

Or you may want to jump straight to:

http://java.sun.com/docs/books/tutorial/collections/index.html

As I wrote in the intro, these paragraphs were originally in the intro. Well, several years have gone by and the java Collections stuff has been around long enough that we can pretty much forget about that old stuff, unless you run into it in old code or tutorials. Hopefully by now Vector and Hashtable are kinda irrelevant. So I moved them down here. Enjoy.

In the first few releases of java, they just had Vector and Hashtable. For those of you familiar with perl, Vector is similar to a perl list (or array), and Hashtable is similar to a perl hash (or associative array). For those of you not familiar with perl, a Vector is like an array, except it grows and shrinks as needed. A Hashtable is a set of key/value pairs, which lets you put in a key and get back a value (a Hashtable also grows and shrinks as needed).

Both Vector and Hashtable are considered fairly heavyweight and old-fashioned nowadays. For one thing, they're both inherently synchronized, which makes them thread-safe, but back in the day, was relatively performance-expensive, especially if you were using them in a situation where you didn't really need synchronization -- i.e. if only a single thread is using a particular Vector or Hashtable instance. However, I hear that these days, uncontested synchronization is actually quite cheap and fast. But if you need a synchronized list or map, use java.util.Collections.synchronizedList() and java.util.Collections.synchronizedMap() (see further down).

Somewhere during Java 1.1 they came up with the Collections API, and by Java 1.2 the Collections API were made part of the core java APIs (earlier than that, they were available as a separate downloadable jar).