The Java Collections Framework

The Java Collections Framework has been around for a long time, but with the advent of generics in Java 5, and now (in Java 8) with streams, functional programming and other features, some serious retrofitting has taken place, and all containers in the Java Collections Framework (even the legacy ones) are now generic. All serious Java programmers need to become familiar with these changes. It's an ongoing and probably never-ending process.

This information on this page is very concise, but can serve as a quick reference for some things that students, with luck, will find useful. That is, it is not complete in any way, but will at least show the interfaces that are most likely to be needed, along with the methods in those interfaces that are likely to be found most useful.

Students have to be prepared to keep referring back to the official Java documentation and may also find it helpful to search the Internet for examples that show the relationships among these various concepts. It must be admitted that, although the Java folks have done amazing things, many of those things had to be done "after the fact", and the overall result is, unfortunately, a bit of a dog's breakfast. Like the rest of us, if the "Java folks" could start over, they might do a few things somewhat differently.

An Overview of the Java Collections Framework and Some Advice for Choosing an Appropriate Collection

First you need to get a good sense of what's available, that is, what containers (collection types) Java provides, and for what kind of usage each might be appropriate.

This class and interface diagram (png) shows a brief overview of the Java Collections Framework, which is divided into four groups: List, Set, and Queue, as well as Map (which is sometimes regarded as conceptually separate from the "Collections" group). Only the principal, commonly-used interfaces and classes are shown. [One of the UML arrows in the diagram appears to be wrong ... can you spot it?]

And here are two more diagrams that provide more detail: JavaCollectionsAPI and JavaMapAPI
[As we said above, the Map hierarchy is often regarded as not being "officially" part of the Collections hierarchy.]

And this brief overview of Java containers (pdf) should also be helpful in giving you a sense of the more useful and commonly used containers and what considerations arise when you need to choose which container to use for a given application. The kind of question-and-answer scenario described in this document is something one has to go through whenever such decisions have to be made, and it is further illustrated in this "Q & A" diagram.

You will want to keep referring back to the discussion and diagrams here, and perhaps seek alternate presentations out there on the Internet.

Selected Interfaces and Some of Their Methods (from the Java Collections Framework API)

Note that sometimes when one interface inherits from another and thus necessarily contains a method from the "parent interface", the method is listed again in the "child interface" if something else needs to be said about it. For example, add(E e) appears in the Deque interface even though this method also appears in the Collection interface and Deque extends Collection. On the other hand, clear() appears in Collection but is not repeated in Deque.

Iterable: Allows an object to be a target of a "for-each" loop.
java.lang.Iterable<T>

- default void forEach(Consumer<? super T> action)
- Iterator<T> iterator()

Collection: A group of objects which may or may not allow duplicates and may or may not be ordered.
java.util.Collection<E> extends java.lang.Iterable<E>

- boolean add(E e) [optional] returns false if e already present and duplicates not allowed.
- boolean addAll(Collection<? extends E> c) [optional]
- void clear() [optional]
- boolean contains(Object obj)
- boolean containsAll(Collection<?> c)
- boolean equals(Object obj) where obj is a collection.
- int hashCode()
- boolean isEmpty()
- Iterator<E> iterator()
- boolean remove(Object obj) [optional] removes one instance of obj.
- boolean removeAll(Collection<?> c) [optional]
- default boolean removeIf(Predicate<? super E> filter)
- boolean retainAll(Collection<?> c) [optional] removes all but c's elements; returns true if collection changed.
- int size()
- default Stream<E> stream()
- Object[] toArray() returns array elements that are copies of the collection elements.
- <T> T[] toArray(T[] a) returns array containing all elements in this collection; runtime type of returned array is that of specified array.

List: A group of objects which may or may not contain duplicates and also guarantees order.
java.util.List<E> extends java.util.Collection<E>, java.lang.Iterable<E>

- void add(int index, Object obj) shifts up any pre-existing elements at or beyond index.
- boolean addAll(int index, Collection c) shifts up any pre-existing elements at or beyond index.
- Object get(int index)
- int indexOf(Object obj) returns index of first instance of obj, or -1.
- int lastIndexOf(Object obj) returns index of last instance of obj, or -1.
- ListIterator listIterator()
- ListIterator listIterator(int index)
- Object remove(int index) removes and returns element at index, compacting resulting list.
- default void replaceAll(UnaryOperator<E> operator) applies operator to each element.
- Object set(int index, Object obj)
- default void sort(Comparator<? super E> c)
- List<E> subList(int start, int end) in which returned list references elements of orginal list.

Queue: A group of objects held (usually but not always) in FIFO (First-In-First-Out), but other orders include LIFO (Last-In-First-Out or "stack-order" and an order determined by a supplied Comparator. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation).
java.util.Queue<E> extends java.util.Collection<E>, java.lang.Iterable<E>

- void add(E e) inserts e into queue if possible and throws one of several possible exceptions on failure.
- boolean offer(E e) inserts e into queue if possible and returns true, or returns false on failure.
- E element() retrieves but does not remove head or throws a NoSuchElementException if the queue is empty.
- E peek() retrieves but does not remove the head, or returns null if the queue is empty.
- E poll() retrieves and removes the head or returns null if the queue is empty.
- E remove() retrieves and removes the head or throws a NoSuchElement exception if the queue is empty.

Deque (pronounced "deck"): A group (double-ended queue) of objects which represent a linear collection that supports element insertion and deletion at both ends. Each of the methods to insert, remove and examine an element has two versions: one that throws an exception if the operation fails and one that returns a special value if the operation fails (null or false, depending on the operation).
java.util.Deque<E> extends java.util.Queue<E>, java.util.Collection<E>, java.lang.Iterable<E>

- boolean add(E e) adds e to (tail of) queue represented by this deque.
- void addFirst(E e) adds e to front of deque (throws one of several possible exceptions on failure).
- void addLast(E e) adds e to end of deque (throws one of several possible exceptions on failure).
- boolean contains(Object o)
- Iterator<E> descendingIterator()
- E element() retrieves head (first element) of queue represented by this deque.
- E getFirst() throws NoSuchElementException if deque is empty.
- E getLast() throws NoSuchElementException if deque is empty.
- Iterator<E> iterator()
- boolean offer(E e) inserts e into (tail of) queue represented by this deque.
- boolean offerFirst(E e) inserts e at front of deque (throws one of several possible exceptions on failure).
- boolean offerLast(E e) inserts e at end of deque (throws one of several possible exceptions on failure).
- E peek() retrieves head of queue represented by this deque and returns it (or null if deque empty).
- E peekFirst() retrieves first element and returns it (or null if deque empty).
- E peekLast() retrieves last element and returns it (or null if deque empty).
- E poll() retrieves and removes head of queue represented by this deque (or null if deque empty).
- E pollFirst() retrieves and removes first element and returns it (or null if deque empty).
- E pollLast() retrieves and removes last element and returns it (or null if deque empty).
- E pop() pops element from stack represented by this deque.
- void push(E e) pushes element onto stack represented by this deque.
- E remove() removes first element.
- boolean remove(Object o)
- E removeFirst() throws NoSuchElementException if deque is empty.
- boolean removeFirstOccurrence(Object o)
- E removeLast() throws NoSuchElementException if deque is empty.
- boolean removeLastOccurrence(Object o)
- int size()

Set: A group of objects which does not allow duplicates and has no guaranteed order.
java.util.Set<T> extends java.util.Collection<T>, java.lang.Iterable<T>

- boolean add(Object obj) [optional]
- boolean addAll(Collection c) [optional]
- void clear() [optional]
- boolean contains(Object obj)
- boolean containsAll(Collection c)
- boolean equals(Object obj)
- int hashCode()
- boolean isEmpty()
- Iterator<E> iterator()
- boolean remove(Object obj) [optional]
- boolean removeAll(Collection c) [optional]
- boolean retainAll(Collection c) [optional]
- int size()
- Object[] toArray()
- <T> T[] toArray(T[] a)

SortedSet: A Set which also has a total ordering on its elements, which may be the natural ordering of the elements if they have one, or an ordering imposed by a Comparator supplied when the sorted set is created. An iterator on such a set will traverse the set elements in increasing order. Some methods in addition to the Set methods are provided to take advantage of the ordering. This interface is the analogue of SortedMap.
java.util.SortedSet<E> extends java.util.Collection<E>, java.lang.Iterable<E>

- E first()
- E last()
- SortedSet<E> headSet(E toElement) does not include toElement.
- SortedSet<E> tailSet(E fromElement)) includes fromElement.
- SortedSet<E> subSet(E fromElement, E toElement) includes fromElement but not toElement.

NavigableSet: A SortedSet extended with "navigation methods" for reporting closest matches for given search targets and which may be accessed and traversed in either ascending or descending order.
java.util.NavigableSet<E> extends java.util.SortedSet<E>, java.util.Collection<E>, java.lang.Iterable<E>

- E ceiling() returns the least element >= the given element, or null if no such element exists.
- E higher() returns the least element > the given element, or null if no such element exists.
- E floor() returns the greatest element <= the given element, or null if no such element exists.
- E lower() returns the greatest element < the given element, or null if no such element exists.
- SortedSet<E> headSet(E toElement) does not include toElement.
- NavigableSet<E> headSet(E toElement, boolean inclusive) includes toElement if inclusive is true.
- SortedSet<E> tailSet(E fromElement)) includes fromElement.
- NavigableSet<E> tailSet(E fromElement)) includes fromElement if inclusive is true.
- SortedSet<E> subSet(E fromElement, E toElement) includes fromElement but not toElement.
- NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive).
- Iterator<E> descendingIterator() returns an iterator over the elements in this set, in descending order.
- Iterator<E> iterator() returns an iterator over the elements in this set, in ascending order.
- NavigableSet<E> descendingSet() returns a reverse order view of the elements contained in this set.
- E pollFirst() retrieves and removes first (lowest) element and returns it (or null if this set is empty).
- E pollLast() retrieves and removes last (highest) element and returns it (or null if this set is empty).

Notes on Classes That Implement the Above Interfaces

There are abstract classes that implement one or more of the above interfaces. You can safely ignore these abstract classes unless you intend to implement your own container based on one of them. Most programmers will instead simply use one or more of the provided concrete classes that implement one or more of the above interfaces.

Thus it is important to become familiar with the standard classes that implement one or more of the above interfaces and are provided by Java for use "off the shelf", so to speak. For each such class, you should know the name of the class, what constructors it has, and which interface(s) it implements. Being familiar with these interfaces and knowing which one(s) are implemented by a particular concrete class goes a long way toward knowing what an object of the class can do for you (in other words, what methods you can call on an object of the class). Of course, any particular class may also provide one or more methods in addition to those in the implemented interfaces and you need to be aware of these "extra" methods as well. For example, ArrayList has methods ensureCapacity() and trimToSize() that fall into this category. Note as well that since ArrayList implements the List interface, this implies that it also implements the Collection interface and the Iterable interface, since the List interface extends the Collection interface which, in turn, extends the Iterable interface. However, we list the relevant implemented interfaces explicitly with each implementing class. Other interfaces may also be implemented by a giaven class, but we are only concerned with the collections-related ones here. Observations imilar to the preceding apply to the other concrete classes as well.

As a word of advice, when you are reading the methods in the Java API for a particular class, always try to keep the "big picture" in mind. That is, try to identify which methods are there because of a particular interface being implemented by the class, and which are unique to the class itself.

Concrete classes with which you should become familiar (by studying Oracle's Java API):
ArrayList implements Iterable, Collection, List
LinkedList implements Iterable, Collection, List, Deque, Queue
ArrayDeque implements Iterable, Collection, Deque, Queue
PriorityQueue implements Iterable, Collection, Queue
HashSet implements Iterable, Collection, Set
TreeSet implements Iterable, Collection, Set, NavigableSet, SortedSet

Note that Vector and Stack are legacy containers whose use should now be deprecated in favor of one of the above classes (ArrayList in the case of Vector, and ArrayDeque in the case of Stack).