Java Collections: Interfaces

Interfaces are the most essential artifacts of Java Collections Framework.  To use the collections framework one needs to know the interfaces because Java programs use interfaces wherever possible. Programming to Java Collections interfaces allows you to change an underlying implementation of a data structure without impacting client code. In the last article we saw that interfaces, implementations and algorithms are three pillars of Java Collections Framework. We will analyze all three starting with interfaces in this article.

Java Collections Interfaces’ Hierarchy

There are two distinct sub-hierarchies inside collections framework. The Collection interface represents a bag like container. A number of objects can be put inside a Collection. There are number of sub-interfaces and these represent specialized data structures.

Map represents a hashtable like data structure that comprises of a key mapped to a value. Maps are different from Collection because Collections store a group of objects whereas Maps store a group of mappings.

Note that all interfaces are generic i.e. you have the type indicator after the interface declaration. This mechanism gives you runtime type safety and yet keeps the number of interfaces to manageable number. Also note that checks for generic types is made at compile time and therefore has no extra runtime overhead. Although Java Collections Framework don’t make it mandatory to use generics, it makes little sense not to. Therefore, if you use the interfaces without generics you will receive a compile time warning.

The Collection Interface

java.util.Collection is the root of the interface hierarchy for all bag like data structures. In essence it represents a group of objects of same type. Here is how it is declared in JDK –

java.util.Collection defines a very broad bag like structure. It is so general in its definition that there is no concrete implementation of this interface. The interface defines the following methods –

Set Interface

A Set is a sub-interface of Collection. A Set is a container that does not allow duplicates. Sets are surprisingly common. For example, if you want to make a list of all voters in  a city, you need to put the voters in a Set because nobody is allowed to vote more than once.

Pretty much like Collection interface, the Set is declared as follows –

The Set interface does not define any new methods of its own but has two sub-interfaces. Set interface does not guarantee order of elements but its sub-interfaces do. These interfaces are SortedSet and NavigableSet. A SortedSet is a Set that maintains the elements in the ascending order. A NavigableSet is a SortedSet that allows retrieval based on the closest match.
Note that Set interface does not provide random access to elements.

The List Interface

A List is an ordered collection that can contain duplicates and allows for random access to elements. Lists are quite similar in behavior to Arrays, the only behavioral difference is that Lists have no size constraints. Considering the fact that while solving a real world problem no programmer wants size constraints, Lists have all but made Java Arrays a museum artifact.

The List interface defines a few methods of its own –

Queue Interface

The Queue interface is a unique collection that is designed with processing of elements. If you want to process the elements of your collection according to certain criterion, Queue is Java’s answer. Queue orders its element according to the specified criteria. Immaterial of the criteria used for ordering elements of Queue , the front of the element is the first to be processed.

The most common usage of Queue is to simulate a FIFO or First in first out Queue . The FIFO queue puts the element that has been longest in the container at the front. You can also have priority queues that take a Comparator to define the order of processing. For example, when deciding the order of landing of aeroplanes at a runway on an airport you would want to order the container of elements according to their fuel status.

The Queue interface defines the following additional methods

Deque Interface

A Deque (pronounced ‘deck’) allows processing at both ends of the container. A Deque allows insertions, examinations and removals at both ends. Therefore, a Deque can be used as both Stack and Queue.

Continuing with our airport traffic control example above, if we want the ability to redirect a few aeroplanes to other airports in extreme congestion we can store the aeroplanes in a Deque. We can process the aeroplanes from the front for landing and process from rear for notifying them to land at alternative destinations.

The Deque has following methods –

Map Interface

A Map is a data structure that maps keys to the values. Maps are Hashtables and have the constraint that keys must be unique. This is more of the defining feature of the data structure rather than a limitation because it guarantees a unique value for a key.

Consider the most common example of hashtable or Map – a Dictionary. A dictionary stores the elaboration of a word. The words become the key and the meaning of the word becomes the value. Using Map ensures that every word has a unique meaning.

SortedMap is a sub interface of Map. The defining feature of SortedMap is that it maintains the keys in ascending order.  Continuing with our Dictionary example, we would like to arrange all the words in our dictionary example alphabetically. A normal Map cannot guarantee the order, therefore we need to use SortedMap . Surprisingly, a very small number of real world problems require arranging keys in order. Therefore, Maps are way more popular and important than SortedMaps.

Having looked at the important interface we will now turn our attention to important implementations in the Java collections framework in the upcoming lessons.

Leave a comment

Your email address will not be published.