Java Collections Framework

These pages are not part of the ECE 250 course, however, they are available to students who are interested in learning (either for personal interest or perhaps to prepare for an interview) about how some of the data structures covered in this course are implemented in the Java Collections Framework. The best introduction to this framework is Oracle's own

Java Collections Framework Tutorial

This tutorial will introduce some of the features of the Java Collections Framework and tie it into the course ECE 250, however, the above tutorial is an excellent source. This page is broken up into:

Java for C++ programmers

Students who are attending interviews where they may be required to know Java, the following page, by Richard G. Baldwin, highlighting the differences between Java and C++ may be useful. At some point, I may attempt to write a sequence of examples for each of these differences. A slightly longer presentation is shown here, by Cay Horstmann. Some of the most obvious differences are covered here:

  • Every object in java is a reference, and all objects are passed by reference. Consequently, the first transformation is to remove all * before variables declared to be pointers to objects, remove all & before any parameters passed by reference, and replace all -> with ..

  • Remove public:, private: and protected: labels and place the visibility keyword in front of all member variables and member functions.
  • Call member variables attributes and member functions methods.
  • All method definitions are inside the class definition.
  • Remove the ; at the end of the class, and get used to the CamelCase naming convention for class names and begin with a lower-case letter for attributes and method names.
  • The file ClassName.java contains only the class ClassName.
  • All functions must be methods. If this restriction doesn't make sense, make it static.
  • All classes are sub classes of the Object class.
  • Operator overloading is not allowed except in the special case of strings where + will concatenate two strings.
  • Arrays are instances of the array class. They look a lot like C++ arrays, except that the arrays have a public attribute length that stores the length of the array. The type is denoted by [] after the variable, and not a * before it. Arrays always check to ensure you are not accessing entries outside the bounds of the array. Like C and C++, arrays go from 0 to length - 1.
  • Only single inheritance is allowed—not that multiple inheritance is that useful.
  • An interface is just a collection of signatures of methods. If a class implements an interface, it must give definitions for each of the methods in the interface.
  • If you want to convert a class into an executable, you must give it a method with the signature public static void main( String[] args )
  • The equivalent of libraries are packages, and they are included with a statement import packagename;.

That's a start. Read the above tutorials for more information and you're also welcome to look at the Wikipeda page Comparison of Java and C++.

Collections in Java

Many of the common algorithms and data structures covered in introductory courses are implemented, in some way, in the Java Collections Framework. Thus, most Java programmers will usually be saved the burden of implementing these data structures with each new project. The individual data structures are implemented as classes in Java, however, to standardize the operations used in Java's Collections Framework, Java uses the idea of an interfaces. An interface is similar to class in that each interface is associated with a list of operations, however, these operations are not associated with any actual implementation. There are no attributes associated with an interface. A class which implements an interface must implement each of the operations listed in the interface.

Every class in the Java Collections Framework implement either the Collection interface or the Map interface.

The Java Collection Interface

A collection is a data structure which stores objects, possibly indexed by an integer.

The UML Class Diagrams for the Collection interface is shown in Figure 1. (Note that there is no attributes block for an interface.) This interface has operations for adding, checking membership of (contains), and removing both individual objects and all objects within some other collection. In addition, it is possible delete all elements which do not occur in another collection. Also, there are queries to check the number of elements (size) and whether or not the collection is empty. The collection can also be emptied (or cleared). There are two techniques for accessing all the elements in the collection: either return an array containing all the elements or return an iterator which allows the user to step through the elements one at a time.

Figure 1. The UML Class Diagram for the Java Collection Interface

Implementations of the Collection Interface

There are further sub-interfaces associated with many of the data structures covered in ECE 250 together with various implementations for each. These are summarized in Table 1. Very often, the some of implementations will have specialized features not available in the default implementations. Some of these additional properties will be discussed in ECE 354, including concurrency and synchronization.

Table 1. Interfaces and implementations of various data structures based on the Collection interface.

Data Structure Interface Class(es) (Implementations)
Array List
RandomAccess		 ArrayList
Vector
concurrent.CopyOnWriteArrayList
Linked List List LinkedList
Stack List RandomAccess Stack
Queue Queue concurrent.ArrayBlockingQueue
concurrent.ConcurrentLinkedQueue
concurrent.DelayQueue
concurrent.LinkedBlockingQueue
concurrent.SynchronousQueue
Deque Deque ArrayDeque
concurrent.LinkedBlockingDeque
LinkedList
Priority Queues Queue PriorityQueue
concurrent.PriorityBlockingQueue
Set Set
SortedSet
NavigableSet		 concurrent.ConcurrentSkipListSet
EnumSet
HashSet
LinkedHashSet
LinkedHashSet
TreeSet
concurrent.CopyOnWriteArraySet

The Java Map Interface

A map is a data structure which stores objects based on a key associated with each object. Each time an item is inserted, two arguments are passed: the key and the object to be associated with they key. The key must be unique: the same Map collection cannot contain two different objects for the same key. Retrieval is based strictly on the key.

The UML Class Diagram for the Map interface is shown in Figure 2. Note that there are two classes associated with any implementation of the Map interface: one for the keys, the other for the stored values.

Note that the values() function can return any class which implements the Collections<V> interface. Thus, for example, the author of a class which implements the Map interface could choose to return a Set, or perhaps a Queue, though wisdom would dictate that a Queue is, in many cases, sub-optimal.

Figure 2. The UML Class Diagram for the Java Map Interface

Implementations of the Map Interface

As with the Collection interface, the Map interface has sub-interfaces and there are numerous implementations of these interfaces in the default Java distribution (listed in Table 2). Like the Collections, some of these implementations deal with additional topics such as concurrency and synchronization.

Table 2. Interfaces and implementations of various data structures based on the Map interface.

Data Structure Interface Class(es) (Implementations)
Hash Table concurrent.ConcurrentMap concurrent.ConcurrentHashMap
HashMap
Hashtable
IdentityHashMap
EnumMap
WeakHashMap
LinkedHashMap
Skip List concurrent.ConcurrentMap
Navigable
SortedMap		 concurrent.ConcurrentSkipListMap
Red-Black Tree NavigableMap
SortedMap		 TreeMap

Example of an Interface

A common interface used in society is that of a telephone. A telephone has the following operations:

  1. Connecting,
  2. Disconnecting,
  3. Entering the digits 0 through 9

Each of the following implementations of the above interface is different in some respect:

  1. Rotary-dial phone
  2. Touch-tone phone
  3. Cellular phone
  4. Internet phone

The difference between a mechanical rotary-dial telephone and the others is significant while there is less difference between the other three. (What differentiates the connection process between a touch-tone phone and a cell phone?) A walkie-talkie is not a telephone not because it is not a communication device (it is) but rather because it does not have the interface associated with what we consider to be a telephone.

References

The following on-line references are available:

Acknowledgments