Lesson 2 - Java Collections Framework

In the previous lesson, Introduction to collections and genericity in Java, we learned to use genericity. In today's lesson, we're going to talk about how collections are implemented in the Java language. We're going to introduce the basic part of the Java Collections Framework.

Java Collections Framework

Every solid programming language offers collections in its standard library. In Java, the entire framework called Java Collections Framework serves for this purpose. It's a relatively complex interface and class hierarchy that is available to all programmers. The basic visualization of this framework is shown in the UML diagram below:

The basic interface which is the foundation for all Java collections is the Collection interface. This interface describes the basic methods for working with every collection. The most important methods are shown in the image below:

Let's describe these methods now:

• size() - returns the current number of elements in the collection
• isEmpty() - returns true if there's no element in the collection, otherwise false
• contains() - returns true if the collection contains an element passed as a parameter
• add() - adds a new element to the collection; returns true if the collection changed (element was added), otherwise false
• remove() - removes element from the collection; returns true if collection changed (the element existed and has been removed), otherwise false
• clear() - clears the collection contents

The Collection interface extends the Iterable interface. This interface defines methods for iterating not only collections but all objects that can be iterated. The interface has the iterator() method, which all collections must implement. It returns an iterator, which we're going to explain right away. Next, the interface contains two default methods with the implementation: forEach() and spliterator(), which we'll discuss in the further lessons.

Iterator

Iterators are objects that are used to iterate through collections. In fact, we've already used an iterator without knowing it, with the ArrayList collection.

Iterating by indexes

When we iterated through an array which isn't a fully-featured collection, we had two constructs to choose from: to iterate by indexes using the for loop:

String[] names = new String[] {"Kyle", "Peter", "Michael", "John"};

for (int i = 0; i < names.length; i++) {
    System.out.println(names[i]);
}

And using foreach:

String[] names = new String[] {"Kyle", "Peter", "Michael", "John"};

for (String name: names) {
    System.out.println(name);
}

When we use foreach over a simple array, Java internally uses the index access anyway. Foreach is just a syntactic sugar, a nicer syntax for the programmer, which is automatically replaced with another, typically more complex code, before compilation.

Iterating collections using iterators

We can use this syntactic sugar in the same way when iterating over real collections, which are the more complex structures than arrays, such as ArrayList. Java will just use an iterator under the hood and our code will be internally translated into something like this:

List<String> lastName = new ArrayList<>();
for (Iterator<String> iterator = lastName.iterator(); iterator.hasNext(); ) {
    String next = iterator.next();
    System.out.println(next);
    iterator.remove(); // If the collection supports it, the current element is deleted
}

In practice, knowledge of iterators pays off if we want to delete items from a collection while iterating through it at the same time. Then we have to use them explicitly for iteration, see below. Another use of iterators is for our own collections, which we want to work with the foreach loop.

The Iterator Interface

Let's look at the Iterator interface in detail. Its implementation is returned by the method of the same name. This interface contains two important methods: next() and hasNext(). Let's describe these methods:

• next() - returns the next item
• hasNext() - returns true if the next item exists

Using these 2 methods, Java is then able to iterate through a collection from the beginning to the end.

Since Java version 8, this interface contains also these methods:

• remove() - removes an item from the collection if it's supported by the collection, otherwise the UnsupportedOperationException is thrown; this is the only right way to remove an element from a collection while iterating through it
• forEachRemaining() - goes through each collection item and applies a given action to it

Custom iterator

Let's try to implement a custom iterator. That's an object, that allows a collection to be iterated. Let's assume that we've created our own SimpleList collection, which just wraps an ordinary array passed through the constructor. We're not going to add any methods to the class, we'll just implement the Iterable interface in it and the iterator() method, which will return an anonymous implementation of the iterator:

public class SimpleList<Type> implements Iterable <Type> {

 private Type[] arrayList;
 private int currentSize;

 public SimpleList(Type[] newArray) {
  this.arrayList = newArray;
  this.currentSize = arrayList.length;
 }

 @Override
 public Iterator <Type> iterator() {
  Iterator <Type> it = new Iterator<Type> () {

   private int currentIndex = 0;

   @Override
   public boolean hasNext() {
    return currentIndex < currentSize && arrayList[currentIndex] != null;
   }

   @Override
   public Type next() {
    return arrayList[currentIndex++];
   }
  };
  return it;
 }
}

The SimpleList class accepts an array in the constructor. An iterator is created for the array. It's important that the iterator() method always returns a new Iterator instance. An iterator can only be used to iterate through a collection from the beginning to the end. If you wanted to iterate backwards, first, you'd have to create an inverted collection and create a new iterator for it. In the hasNext() method, we find out whether the iterator can return the next item, or it has already reached the end. The next() method returns the current item and increases the array index.

Note that we've implemented the Iterator interface as an anonymous class. Of course, we could also declare a regular class, such as SimpleIterator, and return its instance in the iterator() method.

Collection descendants

The Collection interface is extended of other methods by the List, Set, and Queue interfaces based on the usage. The Map interface, which contains methods for working with the key-value type collections, is completely separate. The basic methods of these interfaces are implemented in abstract classes, according to the interface type: AbstractList, AbstractSet, AbstractQueue, and AbstractMap. Abstract classes are used because some concrete interface implementations can share the implementation of the basic methods (size(), isEmpty()), but will also have different methods such as add(), remove(). Furthermore, these abstract classes are useful in the case, when we want to implement our own collection but want to have the foundation already implemented.

To be completely accurate, all the abstract classes listed above, except for AbstractMap, also inherit from the common AbstractCollection abstract class. All the classes can be found in the java.util package. These classes have one common feature: they're not thread-safe. That means it's not safe to modify their items from multiple threads. In Java, this problem is solved using classes that are in the java.util.concurrent package. There are also classes of the same name with the support for multi-thread safety. For example, for ArrayList, there's a thread-safe version named CopyOnWriteArrayList.

In the following lessons, we'll gradually discuss the most important interfaces: List, Set, Queue, and Map along with their implementations, namely: ArrayList, LinkedList, HashSet, and HashMap. Next time we'll have Lists with arrays in Java.