A brief look at the interfaces in the java collections framework

Prior to JDK 1.2, the data structures provided by the Java platform included certain limitations that could complicate application development. For example, deleting or adding to an array would require reshuffling, and sorting required extra code. To improve on these issues, The Java Collections Framework was created; you can access it by importing java.util.

There's a lot to say about this Framework. The tools here are incredibly useful. Questions about this Framework often provide the first filter in technical interviews.

Let's take a look at the six interfaces contained in this Framework.

Collection (extends Iterable)

The Collection interface serves as the main root of the framework hierarchy. A collection simply represents a group of objects known as its elements. Some types of collections allow duplicate elements, others don't. Some order their elements, and some don't. Notice how the Collection interface extends Iterable. We'll come back to this later.

Set (extends Collection)

A Set is a Collection that doesn't allow for duplicate elements.

SortedSet (extends Set)

A SortedSet is still a Set, so it also doesn't allow for duplicate elements. In addition, it maintains its elements in some kind of ascending order. The rules that define this order are part of each particular implementation.

Map

If you've used Hashtable, you're familiar with the idea of a Map. The Map collection lets you store pairs of elements, termed "keys" and "values". A Map can't contain duplicate keys; each key maps to at most one value.

SortedMap (extends Map)

A SortedMap is a Map that maintains its mappings in ascending key order.

List (extends Collection)

A List is an ordered Collection that allows for duplicates. A List allows each element to be accessed by its integer index, giving precise control over where each element is inserted.

Queue (extends Collection)

The Queue interface implements the Collection interface and usually supports a FIFO (First In First Out) ordering. Along with the basic Collection operations, a Queue also includes additional insertion, extraction, and inspection operations.

The FIFO ordering doesn't always get implemented. A priority queue is an example of this, which orders elements according to some kind of priority structure. However the ordering is implemented, the head of the queue is always defined as the element that is next removed. In a FIFO queue, new elements are inserted at the tail of the queue, but that's not the case for other kinds of queues. Every implementation of Queue must specify its own ordering rules.

-----

Earlier we noted that the Collection interface extends an interface named Iterable. This detail can create some initial confusion, so let's unpack this.

There are two separate interfaces to keep track of here, one is named Iterable, and the other is named Iterator.

Iterable includes just one method, named "iterator", which returns an Iterator object over a set of elements. The point here is that if you're creating an object from a class that extends Iterable, you can be sure that there's a rule for iterating through these objects.

Iterator is an interface that defines an iterator over a collection. This Iterator ensures that you have the basic methods you need for this iteration. There are just three methods:

hasNext();

next();

remove();

What does this buy us? The answer is more elegant code.

Since all Collections extend this Iterable interface, we can create an enhanced version of the for loop that uses an Iterator to iterate through the objects contained in a Collection. We'll cover this in the next post.

You should note that Map and SortedMap do not extend Collection, and hence are not inherently Iterable. As a result, Maps do not provide an iterator() method. A Set of keys can be obtained from the Map, and one can iterate over that. This means that the ordering depends on the type of Map you're working with.

TreeMap elements are ordered by key.

HashMap elements will be in an unpredictable order.

LinkedHashMap elements will be ordered by entry order or last reference order, depending on the type of LinkedHashMap.

---------------------------------------------
Here are some review questions to help ground this theory with a few example situations:

For each of the following types of data, what interface should be used?

* Names of people standing in line

* Words used in a book, and their associated frequencies

* Names randomly chosen from a lottery

* A list of conference rooms in a building

* People waiting to receive a liver donation

* A schedule of classes

* A shuffled deck of cards

Challenge: See if you can write the code for an implementation of one these interfaces.