Collections

Optional Reading

Read Introduction, Interfaces, Implementations and Algorithms of The Java Tutorial on Collections. I don't expect you to be experts on collections. Instead, I want you to be familiar with some of the basics and remember they exist for later projects.

Why Collections?

If you need to store some information in some type of data structure, the Java Collections provide you with proven implementations so you don't have to write your own. Collections are used to store, retrieve, manipulate, and communicate aggregate similar types of data. The point is that if you find yourself needing some kind of data structure to hold data, look a the Collections API first because you have a lot of options.

It turns out, Sun (Oracle) created a Collections Framework to act as a standard library of Containers. From the Java Tutorial:

A collections framework is a unified architecture for representing and manipulating collections. All collections frameworks contain the following:

• Interfaces: These are abstract data types that represent collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages, interfaces generally form a hierarchy.
• Implementations: These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.
• Algorithms: These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces. The algorithms are said to be polymorphic: that is, the same method can be used on many different implementations of the appropriate collection interface. In essence, algorithms are reusable functionality.

Note that what we have here is a set of Containers, with similar methods, and proven algorithms to manipulate your date. Typically, if you have need for a Container for data, the Java Collections Framework probably has something already designed, implemented, tested and published. There is no reason to "re-invent the wheel".

Collection Interfaces

It is mentioned above that the Collection Framework uses Interfaces to abstract data handling. Let us look at java.util.List and see what a sample Collections Framework Interface looks like

First, you'll notice the Interface definition uses Generics, which we will cover in the next module. Generics are a way to put type safety into Collections (they used to be just "Objects").

Interface List<E>

So, we see that the List Interface requires us to specify a type of List as part of its declaration, then if you notice, there are a lot of known implementations listed for the List Interface

AbstractList, AbstractSequentialList, ArrayList, AttributeList, CopyOnWriteArrayList, LinkedList, RoleList, RoleUnresolvedList, Stack, Vector

What is important here is that if you choose to have a list, you can choose "how" you want to implement that list, but it is still a List. You could start with a Vector implementation, then two months later switch to an ArrayList and your code would still work for the List interface methods

Some of the main methods in a Collection

Collections have matured quite a bit since their initial introduction. You can take a look at the Collection API and then lets cover some of the interesting methods in a bit more detail (we'll look at most of the methods listed in the API below, but not all of them).

Interestingly, some of the methods in the Collection interface are listed as optional. If you look at the first method below...add()...this doesn't make sense for a read-only implementation of a Collection. In this case two things may happen if you call this "optional" method in a class that doesn't support the operation (1) a UnsupportedOperationException *may* be thrown by the implementing class if the calling of the method will have no effect on the collection. (2) the method may not do anything to the collections, but will return its stated value.

I've taken the summaries of the methods and added a few words to each, note that you can click on any method name to go to the full API documentation of that method.

You can pretty much count on anything in the Collection Framework implementing all of these methods, so they are good to remember!

Why Multiple Implementations for the same Interface?

There are already several implementations of some basid interfacest:

Take a look at the above table. Notice that for the List interface, there are four implementations, ArrayList, Vector, Stack and LinkedList. If they both implement the List interface, why have four?

You can determine which is better for your use by looking in the API. It all comes down to the implementation. ArrayList is implemented using an internal Array. Efficient for most simple list, but if you want to do a lot of dynamic manipulation of the list (adds, inserts, removes) the Array implementation is not the most efficient. LinkedList on the other hand is much better for dynamic lists. The API for LinkedList states that "In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue."

So, they are both lists, but how the list will be used helps determine which implementation of the List interface to use. The API will tell you how the interface is implemented (HashMap, Array, LinkedList, etc...) so that you can choose the correct implementation.

What about Vector?

Many of you may remember java.util.Vector which was an early Collection-like component from the early days of Java 2 platform v1.2. It was "retrofitted" to implement the List interface and is now a member of the Java Collections (note it wasn't in the table from the required reading). Many people use ArrayList instead of Vector because Vector has built in synchronization (Thread safety), which has a performance cost. Unless you need a "synchronized" ArrayList, you don't need to use Vector.

New since JDK 1.6

Several additions were made to the Collections API that are not talked about in the Optional Reading above. They are:

New Interfaces

• Deque: A double ended queue
• BlockingDeque: A Deque which will block on inserting input if it is full.
• NavigableSet: A SortedSet extended with navigation methods reporting closest matches for given search targets.
• NavigableMap: A SortedMap extended with navigation methods returning the closest matches for given search targets.

New Classes

• ArrayDeque: An implementation of Deque using Arrays. Not thread safe, but performs faster than a Stack when used as a stack and faster than a Linked List when used as a queue.
• LinkedBlockingDeque: Implementation of BlockingDeque
• ConcurrentSkipListSet: This implementation provides expected average log(n) time cost for the contains, add, and remove operations and their variants
• ConcurrentSkipListMap: A Map providing additional atomic put, remove, and replace methods. Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a ConcurrentMap as a key or value happen-before actions subsequent to the access or removal of that object from the ConcurrentMap in another thread
• AbstractMap.SimpleEntry: An Entry maintaining a key and a value. The value may be changed using the setValue method. This class facilitates the process of building custom map implementations
• AbstractMap.SimpleImmutableEntry: An Entry maintaining an immutable key and a value. The value may be changed using the setValue method. This class facilitates the process of building custom map implementations

Updated Classes in Java 6.0

• LinkedList: is modified to implement Deque.
• TreeSet: Now implements NavigableSet
• TreeMap: is modified to implement NavigableMap
• Collections: 2 new methods newSetFromMap and asLifoQueue are added

New in Java 8

One of the things that was added to the Collections Framework in Java 8 was the stream() and parallelStream() methods. While we don't tend to cover the advanced topics like Streams in this course, this supports things like lambdas and other more specialized methods to handle processing of large Collections in efficient and even parallel implementations.

Iterating through a Collection

There are actually at least three different ways to iterate through a Collection.

The first way is to use something that is new in JDK 8, and something we really won't cover in this class...but I'll quickly mention it here. As of JDK 8, the recommended way to iterate through a Collection is to use something called a Stream and Lambda Functions. For example, let's say you have our Employee class, and you want to print out people in the Security Department. You get a Stream from the Collection, and then filter and process each element.

employees.stream()
   .filter(e -> getDepartment().equals("Security")
   .forEach(e -> System.out.println(e.getName());

The above code, gets the stream, filters the elements for those where getDepartment() is equal to "Security", and then prints out each one. Again, trying to cover Streams and Lambdas at this point is out of scope, but if you are interested, you can dig into it more.

The second way is to use the for-each Construct

for (Employee emp : employees) {
   if (emp.getDepartment().equals("Security") {
       System.out.println(e.getName());
   }
}

The third way is to use an Iterator to travese the elements of the Collection. An Iterator is actually an Interface that provides the following methods:

public Intgerface Iterator<E> {
  boolean hasNext();
  E next();
  void remove();  // this is an optional method and may not be in every implementation
}

And as is often the case, this example uses Generics, which we will cover in the next section. Let's just say the

You use an Iterator by getting the Iterator from the Collection (it supplies the implementation), and then seeing if there is anything next "in line" in the Collection to process with the Iterator. This is the hasNext() method, and it returns true if there is another element in the Collection. If there is another element, you can call the next() method to access the next Element.

So, lets use an ArrayList as an example. We'll show the code for building the 3 element ArrayList, and then how to use the Iterator.

        ArrayList<Employee> employees = new ArrayList<Employee>();
        Employee e = new Employee();
        e.setFirstName("Bob");
        e.setLastName("Evans");
        e.setDepartment("Security");
        employees.add(e);
        e = new Employee();
        e.setFirstName("Robert");
        e.setLastName("Mitchell");
        e.setDepartment("Security");
        employees.add(e);
        e = new Employee();
        e.setFirstName("Dana");
        e.setLastName("Schlichting");
        e.setDepartment("Help Desk");
        employees.add(e);
        Iterator i = employees.iterator();
        while (i.hasNext()){
            Employee emp = (Employee)i.next();
            if (emp.getDepartment().equals("Security")) {
                System.out.println(emp.getName());
            }
        }

There is something else interesting about the use of the iterator

You then call the next()

Basic Collections Types (Interfaces)

The following list describes the different types, or Interfaces that exist in the Collections Framework

• Collection - This is that base Interface for all of the more specialized Interfaces. It contains a group of Objects, referred to as elements. This interface has some very general metyhods like size(), isEmpty(), add(), remove() and iterator(), that are independent of any of the more specialized interfaces.
• Set - A Set is a Collection that cannot contain duplicate elements. Sets will allow you to try to add a duplicate, but they will not modify the Collection if the element is already present.
• List - Unlike Sets, Lists may contain duplicate information. Lists imply a certain amount of ordering, and some methods are defined to access the list with an index and search the List. This interface adds a ListIterator that allows both forward and backward motion through the list. A List may be sorted by using the Collections.sort(l) method.
• Queue - a Queue is a List that is designed to hold items in sequence prior to processing them. Queues typically operate in a FIFO (First in, First out) scheme. Basically it is a List you load from one "end" and unload from the other.
• Deque - This is a double-ended queue. You can load and unload elements from either end.
• Map - This is a Collection that places elements in a Container, but indexes them with keys. A map cannot contain duplicate keys, but may contain duplicate values...the keys are the unique identifiers that allow you to pull out the appropriate element. Maps typically have methods like get(), put(), remove(), containsKey(), containsValue()
• SortedSet - This is a Set container that maintains its elements in ascending order, as prescribed by a default, or custom Comparator.
• SortedMap - This is a Map container that maintains its elements in ascending key order, as prescribed by a default, or custom Comparator.

Practice

Download the collections Eclipse project, unzip it and load it (or just view the source if you aren't using Eclipse).

In this example, I make some very simple collections using different implementations. Run the code and look at the output.

Try removing the equals and hashCode methods of Test and see what happens to the HashSet examples. Why do you think this is?

Also pay attention to the order of the elements vs. how they had been added. Why does the HashSet not come out in the order added?