Collections Framework

Collections Framework Overview

Before Java 2, the language had only arrays, the Vector class, and the Hashtable class for grouping objects. These were inconsistent, not always interchangeable, and lacked a common API. Java 2 shipped the Collections Framework to fix all of that: a unified architecture of interfaces, implementations, and algorithms for storing and manipulating groups of objects.

The framework gives you three things. First, a set of interfaces that define what a collection can do: add elements, remove them, iterate over them, check membership, and so on. Second, a set of concrete classes that implement those interfaces with different performance characteristics suited to different use cases. Third, a utility class called Collections that provides static algorithms such as sorting, shuffling, and searching.

Because everything programmes against the interface (not the implementation), you can swap one implementation for another with a single line change. Code written against List works the same whether you hand it an ArrayList or a LinkedList. This is the power of the framework.

Collection Interface Hierarchy

At the very top sits java.lang.Iterable, which requires only one method: iterator(). Any class that implements Iterable can be used in an enhanced for-each loop. Below it sits java.util.Collection, which adds the core contract: size, isEmpty, contains, add, remove, and so on. From there the hierarchy branches into three main sub-interfaces.

Iterable and Iterator Interface

Iterable<T> is the contract that says: "you can get a cursor to walk over my elements." It declares a single method, Iterator<T> iterator(), which returns a fresh cursor positioned before the first element.

The Iterator<T> interface itself has three methods. hasNext() returns true if there are more elements to visit. next() advances the cursor and returns the element it just passed. remove() deletes the element most recently returned by next() from the underlying collection. Using remove() through the iterator is the only safe way to delete elements while iterating. Calling the collection's own remove() during a for-each loop will trigger a ConcurrentModificationException.

The enhanced for-each loop is syntactic sugar over an iterator. When you write for (String s : list), the compiler rewrites it as a call to list.iterator() followed by a while loop using hasNext() and next().

List Interface: ArrayList, LinkedList, Vector, Stack

The List interface extends Collection with positional access methods: get(int index), set(int index, E element), add(int index, E element), and indexOf(Object). Lists preserve insertion order and allow duplicates.

Set Interface: HashSet, LinkedHashSet, TreeSet

The Set interface guarantees that no duplicate elements can be stored. When you call add() and the element already exists, the set is unchanged and add() returns false. What counts as a duplicate is determined by the element's equals() and hashCode() methods (for hash-based sets) or its compareTo() method (for tree-based sets). Getting this contract wrong is the most common source of subtle bugs when using sets with custom objects.

Queue Interface: PriorityQueue, ArrayDeque, LinkedList as Queue

The Queue interface models a waiting line. Elements enter at the tail and leave from the head, which is the FIFO (first-in, first-out) pattern used in task scheduling, message passing, and breadth-first search. The interface provides two sets of methods for each operation: ones that throw exceptions on failure (add, remove, element) and ones that return null or false instead (offer, poll, peek). In most application code the null-returning versions are preferred because they avoid exception overhead in normal flow.

Deque Interface: ArrayDeque and LinkedList as Deque

Deque (double-ended queue) extends Queue and allows insertion and removal at both ends. This makes it useful as a stack (LIFO) as well as a queue (FIFO), and for any algorithm that needs to work from both ends of a sequence, such as sliding-window problems or palindrome checking.

ArrayDeque is the recommended general-purpose deque. It is faster than LinkedList for both stack and queue operations because it uses a circular array with no per-element object allocation. It is also the preferred replacement for the legacy Stack class.

Map Interface: HashMap, LinkedHashMap, TreeMap, Hashtable, ConcurrentHashMap

The Map interface is not part of the Collection hierarchy, but it is just as central to everyday Java programming. A Map stores key-value pairs where each key is unique. Given a key, retrieving its associated value is extremely efficient in hash-based implementations. Core operations are put(K key, V value), get(Object key), remove(Object key), containsKey(), keySet(), values(), and entrySet().

Collections Utility Class

java.util.Collections (note the plural) is a class of static methods that operate on collections. It is distinct from the Collection interface itself. Think of it as a toolbox of algorithms that you can apply to any list, set, or other collection without being concerned about the underlying implementation.

The methods divide broadly into three groups: reordering methods that change the state of a list (sort, reverse, shuffle, rotate); searching and statistical methods that read from a collection without changing it (min, max, frequency, binarySearch, disjoint); and wrapping methods that return special-purpose views of collections (unmodifiableList, synchronizedList, singletonList, nCopies, emptyList).

Arrays.asList() vs List.of(), Set.of(), and Map.of() (Java 9+)

Java provides several shortcuts for creating collections from a known set of values. Choosing the wrong one leads to subtle bugs, so understanding the differences is important.

Arrays.asList() returns a fixed-size list backed directly by the provided array. You can call set() to replace elements, but you cannot add or remove elements because the size is tied to the array. Changes to the original array are reflected in the list and vice versa.

Java 9 introduced List.of(), Set.of(), and Map.of() as truly immutable factory methods. None of these allow nulls, and any attempt to call add, remove, set, or put on them throws UnsupportedOperationException. They are compact, easy to read, and safe to share across threads without synchronisation. If you need a mutable starting point from an immutable literal, wrap it: new ArrayList<>(List.of(...)).

Comparable vs Comparator

Sorting requires some way to compare two objects and decide which comes first. Java provides two mechanisms for this: Comparable and Comparator. They solve the same problem but from different perspectives.

Comparable<T> is implemented by the class itself. Its single method, int compareTo(T other), defines the natural ordering of the class. Return a negative number if this object should come before other, zero if they are equal, and a positive number if this object should come after other. Classes like Integer, String, and LocalDate already implement Comparable.

Comparator<T> is an external strategy object. You create one when you want an ordering that is different from the natural ordering, or when you cannot modify the class (it belongs to a library). Since Java 8, Comparator is a functional interface, so you can express it as a lambda or use the convenient factory methods like Comparator.comparing(), thenComparing(), and reversed().

Iterator and ListIterator

You have already seen Iterator earlier in this tutorial, but it is worth comparing it directly with its more powerful sibling, ListIterator.

A ListIterator is obtained from any List by calling listIterator(). It extends Iterator and adds the ability to traverse backwards using hasPrevious() and previous(), to retrieve the current index using nextIndex() and previousIndex(), to replace the last element visited using set(), and to insert a new element at the current position using add(). This makes it the right tool when you need to transform a list in-place during a single pass.

Fail-fast vs Fail-safe Iterators

When you iterate over a collection and another piece of code modifies it concurrently (or even in the same thread, directly through the collection's own methods during a loop), the safety of the operation depends entirely on which type of iterator you are using.

Fail-fast iterators are used by the standard single-threaded collections: ArrayList, LinkedList, HashMap, HashSet, and their relatives. They maintain an internal modification count. Every structural change to the collection (adding, removing, or clearing elements) increments this count. Each time the iterator calls next() it checks whether the count has changed since the iterator was created. If it has, it immediately throws a ConcurrentModificationException. The name "fail-fast" is accurate: rather than producing silently wrong results, the iterator fails loudly as soon as it detects the problem.

Fail-safe iterators (found in the concurrent collections in java.util.concurrent, such as CopyOnWriteArrayList and ConcurrentHashMap) operate on a snapshot of the collection's state taken at the time the iterator was created. Modifications to the original collection after that point are not seen by the iterator, and no exception is thrown. The trade-off is memory: maintaining a snapshot is more expensive, and the iterator may see stale data.

Quiz - Test Your Knowledge

Ten questions covering the interface hierarchy, List and Set implementations, Queue and Map choices, the Collections utility class, immutable factory methods, Comparable versus Comparator, ListIterator capabilities, and fail-fast versus fail-safe behaviour. Read each option carefully before selecting your answer.