Skip to main content

An overview of Java's container classes

Posted by hellofadude on February 12, 2014 at 10:41 AM PST

In the normal course of solving a general programming problem, it is almost certain that you will become compelled to create, and identify useful ways by which to hold any number of objects within your program. In Java, you are normally inclined toward the array as the natural choice for holding a group of primitives, but this has the obvious limitation of being of a fixed size, whereas, under normal circumstances, you are unlikely to know before hand, the number of objects, or indeed anything about their type before run-time.

The java.util package provides a collection of type safe containers with which you can very quickly and easily begin to solve a number of well documented programming problems. These containers are expressed as basic interfaces of two libraries - 1) Collection interface:- which describe a sequence of individual elements to which certain rules may be applied. Containers within this category include List, Set and Queue and 2) Map interface:- a group of key-value pairs that allow you to look up a value using a key. A Map is also known as an associative array.

Type safety within this context refers to the ability to ensure that only objects of the specified type can be inserted into a particular container. Java makes this possible through the use of generics, which provides a way for classes and interfaces to become parameters within other classes, interfaces and methods. For instance, one of the most commonly used container in Java is the ArrayList which represents a type of Collection. We could create a type safe ArrayList container to hold Fruit objects in the following way:-

ArrayList<Fruit> fruits = new ArrayList<Fruit>();

The angle brackets surrounding the type parameter is used to denote the actual type (class or interface) for which purpose the container was created. Java's containers are very simple to learn and use once you are able to get your head around the concept of generics. The following examples are designed to further elucidate the matter. First a non-parameterised container is used to hold a number of unrelated objects:-
package kingsley.java

import java.util.ArrayList;
  
class Fruit {
     private static long counter;
     private final long id = counter++;
     public long getId() { return id; }
}
class Furniture { }
public class UsingNonParameterisedContainer {
     @SuppressWarnings("unchecked")
     public static void main(String[] args) {
         ArrayList fruits = new ArrayList();
         for(int i = 0; i < 2; i++)
             fruits.add(new Fruit());
         fruits.add(new Furniture());
         for(int i = 0; i < fruits.size(); i++)
             System.out.println((Fruit)fruits.get(i));                 //! Class cast Exception
    }
}

In this example a non-parameterised ArrayList class is used to hold Fruit and Furniture objects, both of which are of dissimilar types. Because the container is not parameterised, the compiler is unable to undertake any form of type checking and elements are upcast to Object making it possible to include different types into the container absent warning.
The problem arises when we go to retrieve elements from the container and we have to make a cast back to the original types. In this particular example, the compiler reports a class cast exception because it is unable to cast a Furniture object to Fruit

In contrast to the previous example, this next example uses a type safe container (generics) to achieve much the same thing with the proviso that these containers are much more intuitive and produce better result:-

package kingsley.java

import java.util.ArrayList;

class Mango extends Fruit {}
class Orange extends Fruit {}
class Funiture {}
class Table extends Furniture {}
public class UsingParameterisedContainer {
     public static void main(String[] args) {
         ArrayList<Fruit> fruits = new ArrayList<Fruit>();
         for(int i = 0; i < 3; i++)
             fruits.add(new Mango());
         fruits.add(new Orange());
         //fruits.add(new Table()); Compiler error!
         for(int j = 0; j < fruits.size(); j++)
             System.out.println(fruits.get(j).getId());
         //using foreach syntax to iterate through list
         for(Fruit f : fruits)
             System.out.println(f.getClass().getSimpleName());
     }
}
/*Output
0
1
2
3
Mango
Mango
Mango
Orange
*//

In this version of a previous code, the parameterised container ArrayList is configured to hold Fruit objects with the addition of angle brackets that denote the use of generics. In this example, a number of Fruit subtypes are added to the container with little fuss, but the attempt to add a Table object induces a compiler error. The compiler protects Java's containers from abuse by undertaking type checking to guarantee that the container holds only the specified type. As a result of this guarantee, note that there is now no need to make a cast when retrieving elements from the container. In the previous example, a wrong type was only flagged at runtime, with Java's post SE 5 containers you get to find out about these sorts of bugs much sooner.

The example further demonstrates how to select each element from within the container using both the for loop and foreach syntax, both of which are ideally suited to a number of different scenarios. The use of the foreach syntax with any Collection object is made possible because of the presence of the Iterable interface whose iterator() method produces an Iterator.

Collection<E> Interface

In Java, collections is a term used to describe a single unit or group comprising of multiple elements. It is synonymous with the concept of a container and both are often used interchangeably.

Java provides a collections framework that comprise more than a dozen interfaces that make it possible for containers to be manipulated independent from the details of their implementation.
At the root of this framework is the Collection interface which represents a generalisation of the concept of a collection implemented by all containers of this type in a way that allows for a greater level of flexibility and variety in the range of it's application and implementation. An ArrayList is an oft used type of Collection which we might have chosen to implement in the following way:-

Collection<Fruit> fruits = new ArrayList<Fruit>();

By upcasting an ArrayList object to a Collection reference, we are in effect programming to the interface. This is a preferred method of programming that encourages loose coupling and high cohesion. Of course, such an arrangement would restrict our access to the methods in the ArrayList class, however this technique provides us with much flexibility that means we could easily switch implementation to any other subtype of the Collection interface with very little effort.

The Collection interface provides several methods that can be used to manipulate elements within containers including for instance some of the more frequently used ones like size() method, which returns the number of elements in the specified collection, the iterator() method, returns an iterator over all elements in the collection, the remove() method which removes an instance of the specified element from the collection, the toArray() method which returns an array containing all of the elements in this collection and a number of others. One may wish to consult the Java API for the full list of methods available to subtypes of the Collection interface.

List<E> Interface

List is a basic type of Collection that maintains elements in a particular sequence and may contain duplicate elements. In addition to the methods inherited from the Collection interface, List provides additional methods including for instance methods that allow indexed access to elements within the list and unlike arrays, are automatically resizeable to accommodate additional elements.

The most commonly used List implementation include those referred to previously i.e. ArrayList - a type of List that particularly excels at randomly accessing elements but is less efficient at insertion and removal operations and LinkedList - a type of List that performs insertion and removal operations more efficiently than does an ArrayList but is known to be less efficient at random access operations. In addition to Implementing the basic List interface, a LinkedList includes methods that make it useable as a Queue or double-ended queue (Deque). A Deque is a linear collection of elements that allows the addition and removal of elements at both end points. The following example demonstrates some of the more common operations associated with objects of a List subtype:-

import java.util.*;

public class ListsOperations {
      public static void main(String[] args) {
         ArrayList<Integer> arrayList = new ArrayList<Integer>(10);
         LinkedList<Integer> linkList = new LinkedList<Integer>();
         Random rand = new Random(10);
         for(int i = 0; i < 10; i++) {
             arrayList.add(i*rand.nextInt(100));
             linkList.add(arrayList.size()*rand.nextInt(100));
         }
         System.out.println("1: arrayList = " + arrayList);
         arrayList.add(new Integer(500));// appends to end of list
         System.out.println("2: arrayList.add(new Integer(500)) = " +  arrayList);
         System.out.println("3: arrayList.contains(new Integer(500)) = " + arrayList.contains(new Integer(500)));
         System.out.println("4: arrayList.remove(new Integer(92)) = " + arrayList.remove(new Integer(92)));
         System.out.println("5: arrayList.indexOf(291) = " + arrayList.indexOf(291));
         System.out.println("6: linkList = " + linkList);
         System.out.println("7: linkList.getFirst() = " + linkList.getFirst());
         linkList.addFirst(new Integer(1000));// insert element at beginning of list
         System.out.println("8: linkList.addFirst(new Integer(1000)) = " + linkList);
         linkList.offer(new Integer(1000)); // adds as tail element
         System.out.println("9: linkList.offer(new Integer(1000)) = " + linkList);
         arrayList.addAll(linkList);// add to arraylist
         System.out.println("10: arrayList.addAll(linkList) = " + arrayList);
         List<Integer> subList = arrayList.subList(5, 11);// new list from arraylist
         System.out.println("11: arrayList.containsAll(subList) = " + arrayList.containsAll(subList));
         System.out.println("12: subList = " + subList);
         Collections.sort(subList); //sort in ascending order
         System.out.println("13: Collections.sort(subList) = " + subList);
         Collections.shuffle(subList); // random permutations
         System.out.println("14: Collections.shuffle(subList) = " + subList);

     }

}
/* Output
1: arrayList = [0, 93, 92, 291, 324, 115, 546, 665, 688, 657]
2: arrayList.add(new Integer(500)) = [0, 93, 92, 291, 324, 115, 546,
665, 688, 657, 500]
3: arrayList.contains(new Integer(500)) = true
4: arrayList.remove(new Integer(92)) = true
5: arrayList.indexOf(291) = 2
6: linkList = [80, 180, 168, 352, 70, 594, 56, 640, 477, 380]
7: linkList.getFirst() = 80
8: linkList.addFirst(new Integer(1000)) = [1000, 80, 180, 168, 352, 70,
594, 56, 640, 477, 380]
9: linkList.offer(new Integer(1000)) = [1000, 80, 180, 168, 352, 70,
594, 56, 640, 477, 380, 1000]
10: arrayList.addAll(linkList) = [0, 93, 291, 324, 115, 546, 665, 688,
657, 500, 1000, 80, 180, 168, 352, 70, 594, 56, 640, 477, 380, 1000]
11: arrayList.containsAll(subList) = true
12: subList = [546, 665, 688, 657, 500, 1000]
13: Collections.sort(subList) = [500, 546, 657, 665, 688, 1000]
14: Collections.shuffle(subList) = [1000, 657, 665, 546, 500, 688]
*//

Note that both types of lists store elements in the order in which they are inserted and both constitute a modifiable sequence i.e the quality of being automatically resizable. Line 2 adds an element to the list, line 3 checks if the list contains a particular element, line 4 removes an element from the list and line 5 returns the index of a referenced element. Note that these operations use the equals() method inherited from the root Object to decide if any two objects are equal and as a consequence may behave differently depending on the behaviour of the equals() method. This example uses Integer wrapper classes that define equality as values being of an equivalent primitive type.

LinkedList has methods that provide very similar behaviour but have different names to reflect the context of particular usage. For instance, the getFirst(), element() and peek() methods all return the head or first element in the list, while getFirst() and element() throw a NoSuchElementException if the list is empty, the peek() method returns null.

The same applies to the remove() and removeFirst() methods both of which remove and return the head of the list and will throw a NoSuchElementException if a list is found to be empty, while the poll() method provides a similar functionality but will return null in the event of an empty list. Only a few of these methods are demonstrated in the above example.

Set<E> Interface

A Set has only a slightly different interface as a Collection, but produces a different behaviour which does not allow for duplicate elements from among the set. One of the more common uses of a Set is for membership lookup i.e. to test for the existence of an object within the set. A Set determines membership based on the value of an object. Set implementations include HashSet, TreeSet and LinkedHashSet, all of which differ in how they store and process elements.
For example, HashSet uses a hashing function to add speed to it's processing of elements and makes no guarantees as to the iteration order of the set, while TreeSet keeps elements sorted in a red black tree structure and is based on a TreeMap. Finally, a LinkedHashSet maintains elements in the order of insertion using a LinkedList but also uses hashing for lookup.

Here is an example of some operations available to objects that implement the Set interface:-

import java.util.*;

public class SetOperations {
     public static void main(String[] args) {
         Set<String> hashset = new HashSet<String>();
         HashSet<String> linkhashset = new LinkedHashSet<String>();
         Collections.addAll(linkhashset, "A E I O U".split(" "));
         Collections.addAll(hashset, "A B C D E F".split(" "));
         System.out.println("1: linkhashset = " + linkhashset);
         System.out.println("2: hashset = " + hashset);
         System.out.println("3: linkhashset.contains("X") = " + linkhashset.contains("X"));// membership lookup
         System.out.println("4: linkhashset.containsAll(hashSet2) = " + linkhashset.containsAll(hashset));
         Collections.addAll(linkhashset, hashset.toArray(new String[0]));
         System.out.println("5: Collections.addAll(linkhashset, hashset) = " + linkhashset);
         System.out.println("6: linkhashset.containsAll(hashSet2) = " + linkhashset.containsAll(hashset));
         System.out.println("7: hashset.remove("E") = " + hashset.remove("E"));
         System.out.println("8: hashset" + hashset);
         System.out.println("9: hashset.removeAll(linkhashset) - " + hashset.removeAll(linkhashset));
         System.out.println("10: hashset" + hashset);
         Collections.addAll(linkhashset, hashset.toArray(new String[0])); // No duplicates
         System.out.println("11: linkhashset" + linkhashset);
         String v = new String("V");
         linkhashset.add(v);
         System.out.println("12: linkhashset.add(v) = " + linkhashset);
         System.out.println("13: linkhashset.contains(v) = " + linkhashset.contains(v));
     }
}
/* Output
1: linkhashset = [A, E, I, O, U]
2: hashset = [A, B, C, D, E, F]
3: linkhashset.contains("X") = false
4: linkhashset.containsAll(hashSet2) = false
5: Collections.addAll(linkhashset, hashset) = [A, E, I, O, U, B, C, D, F]
6: linkhashset.containsAll(hashSet2) = true
7: hashset.remove("E") = true
8: hashset[A, B, C, D, F]
9: hashset.removeAll(linkhashset) - true
10: hashset[]
11: linkhashset[A, E, I, O, U, B, C, D, F]
12: linkhashset.add(v) = [A, E, I, O, U, B, C, D, F, V]
13: linkhashset.contains(v) = true
*//

The example upcasts a HashSet object to a Set and a LinkedHashSet to a HashSet. Both containers are populated using the utility Collections.addAll(). The rest of the example demonstrates some of the methods available to subtypes of the Set interface.
Further if you are interested in an ordered set of results, you can make use of a SortedSet like so:-
SortedSet<Integer> treeSet = new TreeSet<Integer>();

Queue<E> Interface

A Queue is a type of Collection that typically takes a "first-in-first-out" (FIFO) approach to the processing of elements. This is to say elements are retrieved in the same order in which they are inserted with the exception of objects that implement the priority queue discipline - which is an alternative queuing technique that subscribes to highest priority or greatest need.

Queue objects can be used as a reliable means to comfortably transfer objects from one area of your program to another and they also possess the peculiar feature of including multiple forms for methods that provide a common functionality but behave differently in that whereby one form throws an exception in the event of an operation failure, the other returns some special value given similar circumstances:-
import java.util.*;

public class QueueOperations {
     public static void main(String[] args) {
         Queue<Character> qe = new LinkedList<Character>();
         for(char c : "Encyclopedia".toCharArray())
         qe.offer(c);
         System.out.println("Queue.offer() - "+ qe);
         qe.poll();
         System.out.println("Queue.poll() - "+ qe);
         System.out.println("queue.peek() " + qe.peek());
         qe.add(new Character('E'));
         System.out.println("queue.add() " + qe);
     }
/* Output
fer() - [E, n, c, y, c, l, o, p, e, d, i, a]
Queue.poll() - [n, c, y, c, l, o, p, e, d, i, a]
queue.peek() n
queue.add() [n, c, y, c, l, o, p, e, d, i, a, E]
*//

The offer() method inserts the specified element into the queue if possible and returns false in the event of a failure. The add() method inherited from the Collection interface performs the same operation which it can only fail by throwing an exception, as a result, the offer() method is the preferred option. The poll() method retrieves and removes the head of the queue, or returns null if the queue is empty. The remove() method performs the same operation but throws an exception if the queue is empty. The peek() and element() methods retrieve but do not remove the head of the queue. While the element() method will throw an exception if the queue is empty, the peek() method returns null giving the same set of circumstances.

Map<K,V> interface

A Map is quite unlike those subtypes of Collection with which we have by now become familiar, in fact it is a very distinct data structure. The Map interface describes methods that operate on key/value pairs, providing you with the ability to map objects to other objects by using a key to map to at most a single value, and for which duplicate keys are forbidden. Map implementation include HashMap, TreeMap and LinkedHashMap, all of which provide similar behaviour and performances to those described in the Set interface subheading.

Some of the methods available to Map objects include those for performing basic operations like put(), get(), remove(), size(), containsKey(), containsValue(), et cetera as well as other methods that perform bulk operations and provide collection views:-

import java.util.*;

public class MapOperations {
      public static void main(String[] args) {
         Map<String, String> myPets = new HashMap<String, String>();
         myPets.put("new Dog ", " woof woof");
         myPets.put("new Cat ", " meeow meeow");
         myPets.put("new bunnyRabbit ", " honk honk");
         System.out.println("myPets: " + myPets);
         System.out.println("myPets.containsKey("new cat") = " + myPets.containsKey("new Cat "));
         System.out.println("myPets.containsValue("honk honk") = " + myPets.containsValue(" honk honk"));
     }

}
/* Output
myPets: {new Cat = meeow meeow, new Dog = woof woof, new bunnyRabbit =
honk honk}
myPets.containsKey("new cat") = true
myPets.containsValue("honk honk") = true
*//

The above code is a simple example of how to look up objects and values in a Map using the containsKey() and containsValue() method. A Map provides a very powerful abstraction that simplify very many programming problems, for instance, here is a program that tracks the pseudo-random nature of Java's Random class, where the number produced by the Random is assigned as the key and the number of times that number is produced is taken to be the value. It would be necessary to generate very many random numbers restricted to a small subset of numbers:-

import java.util.*;

public class MapOperations2 {
      public static void main(String[] args) {
         Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
         Random rand = new Random(25);
         for (int i = 0; i < 2000; i++) {
             int x = rand.nextInt(10);
             Integer freq = map.get(x);
            map.put(x, freq == null ? 1 : freq + 1);
         }
         System.out.println(map);
      }
}
/* Output
{1=200, 8=218, 7=194, 5=195, 6=198, 4=188, 0=198, 9=191, 2=220, 3=198}
*//

In this example, a ternary if/else operator is used to test and increment the frequency a particular number has been randomly generated. Because Maps do not accept duplicate keys there is little chance of a particular key occurring more than once. Maps can also be expanded to include multiple dimensions by including other maps whose values also happen to be other containers or even further made up of other maps. A Map may return a Collection of its values, a Set of its keys or a Set of its pairs.

Iterator design pattern

An Iterator object provides a way to iterate over the elements in a sequence without exposing its underlying implementation. It comes under the category of a behavioural design pattern and any discourse on Java's containers is incomplete without affording it adequate attention, since you may have perceived before now that most containers within the Java's collection framework implement the Iterable interface, which is a prerequisite for accessing an Iterator. A Map on the other hand produces a Set view of it's elements with the entrySet() method which proves sufficient for iteration purposes.

An Iterator object provides you with a number of very useful methods that rest easily beside the concept of a container, like for instance the next() method which is a call to get the next element in the sequence, the hasNext() method which returns either of true or false according to whether the sequence remains empty or not, and the remove() method which removes the last element returned by the iterator:-

import java.util.*;

public class Iteration {
     public static void main(String[] args) {
         List<Integer> arraylist = new ArrayList<Integer>();
         Random rand = new Random(27);
         for(int i = 0; i < 8; i++)
             arraylist.add((Integer)rand.nextInt(20));
         System.out.println("arraylist: " + arraylist);
         Iterator sequence = arraylist.iterator();
         while(sequence.hasNext()) {
             Integer next = sequence.next();
             System.out.println("The double value for " + next + " is " + next.doubleValue());
         }
         sequence.remove();
         System.out.println("arraylist: " + arraylist);
     }
}
}
/* Output
arraylist: [10, 12, 17, 18, 11, 16, 10, 14]
The double value for 10 is 10.0
The double value for 12 is 12.0
The double value for 17 is 17.0
The double value for 18 is 18.0
The double value for 11 is 11.0
The double value for 16 is 16.0
The double value for 10 is 10.0
The double value for 14 is 14.0
arraylist: [10, 12, 17, 18, 11, 16, 10]
*//

In this example, the iterator object sequence steps through the container sequentially, so long as the test condition in the while clause evaluates to true, printing the each element to screen. The example also demonstrates the use of the remove() method which removes the last element returned by the iterator from the underlying collection.

Here is a method that uses an iterator to step through a sequence providing a view of the elements within a variety of containers:-

import java.util.*; 

public class Iteration2 {
     static void view(Iterator<Character> it) {
         while(it.hasNext()) {
             Character p = it.next();
             System.out.print("[ " + p + " " + " ]");
         }
         System.out.println();
     }
     public static void main(String[] args) {
         char[] cc = {'d', 'e', 'c', 'x', 'd'};
         Random rand = new Random();
         ArrayList<Character> list = new ArrayList<Character>();
         LinkedList<Character> list2 = new LinkedList<Character>();
         HashSet<Character> set = new HashSet<Character>();
         for(int i = 0; i < cc.length; i++) {
             list.add(cc[rand.nextInt(cc.length)]);
             list2.add(cc[rand.nextInt(cc.length)]);
             set.add(cc[rand.nextInt(cc.length)]);
         }
         view(list.iterator());
         view(list2.iterator());
         view(set.iterator());
     }

}
/* Output
[ d  ][ d  ][ c  ][ d  ][ c  ]
[ e  ][ c  ][ e  ][ e  ][ d  ]
[ d  ][ x  ]
*//

The view() method in this example has no knowledge of the underlying container or the type of sequence it is traversing, and therein lies the real value of the iterator design pattern - it provides you with the ability to separate the operation of traversing a sequence from the underlying implementation of the said sequence.

An Iterator is limited only by it's ability to move in one direction only - forward through a sequence. A ListIterator is a subtype of Iterator that can only be produced by List subtypes and that has the unique quality of not only being bidirectional, meaning it can move forward and backward through a list, but it can also replace the most recently visited element using it's set() method, in addition to being able to produce the indexes of the next and previous elements relative to it's current position in the list.

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

class Element {
     private static long counter = 0;
     private final long id = counter++;
     public String toString() {
         return this.getClass().getSimpleName() + " " + id;
     }
}

public class LisIteration {
     static void listIterator(List list) {
         ListIterator listIterator = list.listIterator(list.size());
         while(listIterator.hasPrevious())
             System.out.print("The " + (listIterator.previousIndex() == 1 ? "1st" :
                                         (listIterator.previousIndex() == 2 ? "2nd" :
                                           (listIterator.previousIndex() == 3 ? "3rd" :
                                             (listIterator.previousIndex() == 4 ? "4th" :
                                               (listIterator.previousIndex() == 5 ? "5th" : "0")))))
                                                  +  " element is " + listIterator.previous() + "\n");
         listIterator.set(new Element());
     }
     public static void main(String[] args) {
         List<Element> l1 = new ArrayList<Element>();
         for(int i = 0; i < 6; i++) {
             l1.add(new Element());
         }
         listIterator(l1);
         System.out.print(l1);
     }
}
/* Output
The 5th element is Element 5
The 4th element is Element 4
The 3rd element is Element 3
The 2nd element is Element 2
The 1st element is Element 1
The 0 element is Element 0
[Element 6, Element 1, Element 2, Element 3, Element 4, Element 5]
*//

The above example uses some rather elaborate code to print out the elements within a container while iterating backwards through the sequence and then replaces the most recently selected element using the set() method.

You may have noticed that unlike arrays, you can produce a printable representation of the elements within a container without the need for an additional API to parse the output like the Arrays.toString() method. Also unlike arrays, containers do not hold primitives, and must rely on wrapper classes to perform the necessary conversion using the autoboxing and autounboxing mechanism.