The Java Collections Framework

The Two Hierarchies

The Collections Framework is divided into two distinct interface trees:

1. Collection<E> — the root interface for most collections (groups of elements).
2. Map<K, V> — a separate, parallel hierarchy for key–value mappings. Map is not a Collection.

The Collection<E> Sub-Interfaces

List<E>

An ordered collection (sequence). Elements have a positional index. Duplicates are allowed. The user controls where each element is inserted.

List<String> names = new ArrayList<>();
names.add("Alice");            // index 0
names.add("Bob");              // index 1
names.add("Alice");            // index 2 — duplicate is fine
String second = names.get(1);  // "Bob"

Set<E>

A collection with no duplicates (as defined by equals()). May or may not be ordered depending on implementation.

Set<String> unique = new HashSet<>();
unique.add("Alice");
unique.add("Bob");
unique.add("Alice");           // ignored — already present

Queue<E>

A collection designed for holding elements prior to processing. Typically FIFO (first-in-first-out) but can also be priority-ordered. Provides insertion, extraction, and inspection operations, each in two forms: one that throws an exception on failure, and one that returns a special value.

Deque<E> (Double-Ended Queue)

Extends Queue<E>. Supports element insertion and removal at both ends. Can be used as a stack (LIFO) or a queue (FIFO).

The Map<K, V> Hierarchy

Maps keys to values. Each key can map to at most one value. No duplicate keys. Replacing a mapping for an existing key overwrites the old value.

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 85);
scores.put("Bob", 92);
int aliceScore = scores.get("Alice");  // 85

Common Implementations

Interface	Implementations	Characteristics
List	ArrayList	Resizable array, $O(1)$ random access, $O(n)$ mid-list insert
List	LinkedList	Doubly-linked, $O(1)$ insert/remove at known position, $O(n)$ random access
Set	HashSet	Hash table, $O(1)$ operations, no ordering
Set	TreeSet	Red-black tree, $O(\log n)$ operations, sorted order
Set	LinkedHashSet	Hash table + linked list, insertion order
Queue / Deque	ArrayDeque	Resizable array, faster than Stack and LinkedList for queue/stack use
Map	HashMap	Hash table, $O(1)$ operations, no ordering
Map	TreeMap	Red-black tree, $O(\log n)$ operations, sorted keys
Map	LinkedHashMap	Hash table + linked list, insertion or access order

Generic Usage and the Diamond Operator

List<String> strings = new ArrayList<>();          // diamond <> infers String
Set<Integer> numbers = new HashSet<>();
Map<String, List<Integer>> nested = new HashMap<>();

The diamond operator (<>) was introduced in Java 7. It avoids repeating type arguments and keeps declarations concise.

The Collections Utility Class

java.util.Collections provides static utility methods that operate on or return collections:

Collections.sort(list);                          // in-place sort (natural order)
Collections.sort(list, comparator);              // in-place sort (custom order)
Collections.binarySearch(list, key);             // binary search (list must be sorted)
Collections.shuffle(list);                       // random permutation
Collections.reverse(list);                       // reverse in-place
Collections.min(collection);                     // minimum element
Collections.max(collection);                     // maximum element
Collections.unmodifiableList(list);              // read-only wrapper
Collections.synchronizedList(list);              // thread-safe wrapper
Collections.frequency(collection, element);      // count occurrences

Programming to Interfaces

List<String> list = new ArrayList<>();
list = new LinkedList<>();  // change implementation, rest of code unchanged

By declaring variables and parameters using the most general interface type that meets your needs, you isolate the rest of the code from implementation details. If you later decide LinkedList is better than ArrayList for your access pattern, you change one line — the constructor call — and all other code continues to work.

This is a direct application of the Dependency Inversion Principle and enables both the Open/Closed Principle and testability with mock implementations.