1. Overview
Let’s now take a step back and have a high-level look at the Java Collections Framework.
We’ve already seen why collections are essential, and now we’ll go one step further by exploring their high-level structure. We’ll discuss the core interfaces and go over some of the most common implementations to understand how everything fits together. By the end of this lesson, we’ll have a clear map of the framework’s primary components and their relationships.
There is no code we need to check out to follow along with this lesson.
2. The Core Interfaces
The Java Collections Framework is built around a set of core interfaces. These interfaces define the general behaviors expected from different types of collections, providing a consistent way to perform common operations such as adding, removing, or searching for elements. This abstraction allows us to work with collections in a uniform way, regardless of their specific implementation.
Let’s review the primary interfaces and their most commonly used implementations.
2.1. High-Level Interface Hierarchy
At the top of the hierarchy is the Collection interface, which gathers fundamental behaviors for working with groups of elements:
┌───────────────────┐
│ Collection<T> │
└────────┬──────────┘
┌────────────────────┼─────────────────────┐
│ │ │
┌────────▼───────┐ ┌────────▼────────┐ ┌────────▼─────────┐
│ List<T> │ │ Set<T> │ │ Queue<T> │
└────────────────┘ └─────────────────┘ └──────────────────┘
Note: Map is not a subtype of Collection
┌────────────────────┐
│ Map<K, V> │
└────────────────────┘As we can see, under the top Collection interface, we have specialized interfaces like List, Set, and Queue. Each of these builds upon Collection but adapts it to a specific use case. For instance, List focuses on ordered sequences, while Set emphasizes the uniqueness of its elements.
Apart from basic Collection operations, Queue provides additional insertion, extraction, and inspection operations. Typically, but not necessarily, Queue represents a First-In-First-Out (FIFO) data structure.
Next to those lies the Map interface, which isn’t a subtype of Collection but still belongs to the overall framework. Instead of handling single elements, Map organizes data as key-value pairs, allowing fast lookups and updates based on unique keys.
Of note is that the Collection interface extends the Iterable interface. We omitted Iterable in the above diagram, as it isn’t part of the collections framework, but a foundational interface that the Collection type and its subtypes extend. It allows us to iterate over a Collection one by one, for example, through enhanced for loops.
It’s worth noting that all collections define the type of data they handle using generics, specified between angle brackets (<>).
2.2. Interrelations Between Key Interfaces
All these interfaces work together to provide a consistent development experience. For example, we can iterate over a List or a Set using similar approaches. That means that once we know how to iterate over one type of collection, we can apply the same principle to others.
Because Map is conceptually different, it has its own methods for working with keys and values. Still, the framework offers ways to retrieve Collection views of a Map, so we can reuse concepts like iteration.
3. Common Implementations
Behind each interface, Java provides ready-made classes that we can use directly.
Next, we’ll look closer at List, Set, Queue, and Map implementations. However, we won’t dive into every method yet, as each will be covered in more detail in future lessons. The goal here is to understand these implementations’ key characteristics.
It’s important to note that none of these standard implementations are thread-safe by default, and some thread-safe collections are separately provided.
3.1. List Implementations
Lists store elements in a specific order. List allows duplicates. Also, inserting and removing elements are easy tasks for List:
┌───────────────────┐
│ List<T> │
└────────┬──────────┘
┌───────────────┴───────────────┐
│ │
┌────────▼────────┐ ┌──────────▼─────────┐
│ ArrayList<T> │ │ LinkedList<T> │
└─────────────────┘ └────────────────────┘ArrayList is great for quick random access, while LinkedList is more suited to frequent insertions and deletions in the middle or at the beginning of the list.
3.2. Set Implementations
Sets avoid duplicate elements:
┌───────────────────┐
│ Set<T> │
└────────┬──────────┘
┌───────────────┼────────────────┐
│ │ │
┌────────▼──────┐ ┌──────▼──────────┐ ┌───▼──────────┐
│ HashSet<T> │ │ LinkedHashSet<T>│ │ TreeSet<T> │
└───────────────┘ └─────────────────┘ └──────────────┘HashSet offers efficient lookups through hashing, while LinkedHashSet preserves the insertion order. TreeSet sorts elements based on their natural order or a custom comparator.
3.3. Queue Implementations
We’ve mentioned that Queue typically represents a FIFO data structure. Next, let’s look at some standard Queue implementations:
┌───────────────────┐
│ Queue<T> │
└────────┬──────────┘
┌───────────────┴───────────────┐
│ │
┌────────▼──────────┐ ┌─────────▼──────────┐
│ Deque<T> │ │ PriorityQueue<T> │
└───────────┬───────┘ └────────────────────┘
│
┌─────────┴─────────┐
│ │
┌──────▼────────┐ ┌─────▼────────┐
│ ArrayDeque<T> │ │LinkedList<T> │
└───────────────┘ └──────────────┘PriorityQueue is a Queue implementation. It presents a priority-based, not a FIFO structure. In PriorityQueue, “priority” determines the order in which elements are removed (dequeued), not the order in which they were added. In other words, higher-priority elements are removed before others, regardless of insertion time.
We’ve learned that LinkedList is a List implementation, but it also implements the Deque interface. A Deque (Double-Ended Queue) is a subtype of Queue. It’s a linear data structure that allows insertion and removal of elements from both the front and the rear. Therefore, it supports both queue (FIFO) and stack (LIFO) operations, making it highly versatile. ArrayDeque is another commonly used class that implements Deque.
3.4. Map Implementations
Map works with key-value pairs, helping us organize data by unique keys. Further, Map doesn’t allow duplicate keys, but values can be duplicated:
┌──────────────────────┐
│ Map<K, V> │
└───────────┬──────────┘
│
┌──────────────────────┼───────────────────────┐
│ │ │
┌────▼───────────┐ ┌──────▼─────────────┐ ┌─────▼───────────┐
│ HashMap<K, V> │ │LinkedHashMap<K, V> │ │ TreeMap<K, V> │
└────────────────┘ └────────────────────┘ └─────────────────┘HashMap is typically the default choice for key-value storage thanks to its speed.
Apart from HashMap, there are two commonly used Map implementations: LinkedHashMap and TreeMap.
Like LinkedHashSet and TreeSet, respectively, LinkedHashMap also preserves insertion order, and TreeMap keeps keys sorted.
3.5. Why There is no Sorted List Implementation
We’ve seen that there are sorted collections such as TreeSet and TreeMap, which keep their elements sorted automatically.
Some may wonder why there are no automatically sorted List implementations. This is because the List interface is designed around ordered, positional access, allowing duplicates and supporting efficient random access in some implementations. Continuously maintaining sort order would conflict with these characteristics, so lists are typically sorted on demand rather than automatically.
A side note for the bigger picture: sorted collections in the framework rely on the Comparable and Comparator interfaces to determine element order.
3.6. How These Classes Fit Together
We’ve talked about several standard classes in the Java Collections Framework. Now, let’s summarize them in a table:
| Type | Class/Interface | Ordered? | Duplicates Allowed? | Key Features / Use Cases |
|---|---|---|---|---|
| List | List | Yes | Yes | Ordered collection, allows random access and duplicates |
| ArrayList | Yes (by index) | Yes | Fast random access, good for read-heavy operations | |
| LinkedList | Yes (by index) | Yes | Fast insertions/removals, also implements Deque | |
| Set | Set | Depending on implementations | No | Unique elements, no duplicates allowed |
| HashSet | No (unordered) | No | Fast lookup, no order guarantee | |
| LinkedHashSet | Yes (insertion) | No | Maintains insertion order | |
| TreeSet | Yes (sorted) | No | Sorted elements using natural/comparator order | |
| Queue | Queue | Yes | Yes | Holds elements before processing, typically FIFO |
| Deque | Yes (double-ended) | Yes | Add/remove elements at both ends, for FIFO and LIFO | |
| ArrayDeque | Yes (insertion) | Yes | Resizable array-based, faster than LinkedList in most cases | |
| PriorityQueue | No | Yes | Elements can be obtained by priority, not FIFO | |
| Map | Map | Depending on implementations | No duplicate keys | Key-value pairs, keys must be unique |
| HashMap | No | No duplicate keys | Fast lookup, no ordering | |
| LinkedHashMap | Yes (insertion) | No duplicate keys | Maintains insertion order | |
| TreeMap | Yes (sorted by key) | No duplicate keys | Keep keys sorted |
All these classes share some common ground: they inherit from the core interfaces and follow similar naming patterns. Switching between different implementations is usually straightforward if we understand the basics of List, Set, and Map. We just need to pick the class with the desired behavior or performance characteristics.
4. Additional Utilities in the Framework
Besides these core classes, Java Collections also provides utility methods and classes in java.util.Collections, plus a few more collection-related features in java.util.Arrays. We won’t explore them as part of this lesson, but just as a quick preview examples, Collections.sort() lets us quickly sort a list, while Collections.emptyList() helps us return an immutable list with zero elements. These utilities extend the framework’s power, making it more straightforward to handle everyday tasks.