A Deep Dive into the Java Collections Framework |

This article offers a deep dive into the Java Collections Framework, packed with carefully selected questions, real code examples, and practical insights. It's designed to help you understand what really matters, from fundamentals to real-world scenarios. Let's get started.

In this article, we'll explore the Java Collections Framework. We will start with an overview, understanding its evolution and purpose. After that, we will look at the different interfaces and APIs present in the framework. We will explore the Collection, List, Set, Map, Queue, and the SequencedCollection interfaces. We will also understand how to pick the right collection, clarifying the differences between List, Set, and Queue and how to choose from the number of alternatives that each of these interfaces provides.

We'll also discover sorting strategies and thread-safe collection options. If you don't write thread-safe code, which collection options should you prefer? We'll also discuss concurrent collections, looking at different strategies like compare-and-swap (CAS) and copy-on-write, and we'll also compare fail-fast versus fail-safe iterators. Finally, we'll also look at recent additions to the collection framework and understand why sequenced collections were added.

The Evolution of the Collections Framework

In the first version of Java, there were early classes for grouping objects, including Dictionary, Vector, Stack, and Properties. These classes had an ad-hoc design with no consistent set of interfaces.

To address this, Java introduced the Collections Framework in Java 1.2. It had two main goals: 1. To unify collection handling through standard interfaces and implementations. 2. To improve the performance, flexibility, and ease of use of these collection interfaces and implementations.

The Collections Framework has evolved significantly over time: - Generics: The framework was updated to make use of generics. - Enhanced For Loop: You can use the enhanced for loop around all collections. - Java 5: Introduced concurrent collections like ConcurrentHashMap in addition to synchronized collections. - Java 8: Enhanced the framework to enable functional programming with features like Streams and Lambda expressions. - Java 9: Added factory methods (List.of(), Set.of(), Map.of()) to create immutable collections. - Java 21: Introduced SequencedCollection to ensure consistent ordering across different types.

The Need for Collections

Collections provide a flexible and efficient way to store, retrieve, and manipulate data. While an array can store a set of numbers, it has several limitations: - Fixed Size: Arrays cannot grow or shrink dynamically. - Manual Operations: You need to write manual logic for searching, adding, or removing elements, especially from the middle. - No Built-in Methods: There are no built-in methods for advanced operations like sorting or implementing complex data structures.

The Collections Framework solves these problems by offering: - Dynamic Resizing: Collections can grow or shrink as needed. - Predefined Methods: Support for adding, removing, sorting, and searching elements easily. - Rich Data Structures: A rich set of data structures like Lists, Sets, Maps, and Queues for different needs.

An Overview of Core Collection Interfaces

Here are the most important interfaces in the Collection Framework:

Collection: The root interface with methods for basic operations like adding and removing elements.
SequencedCollection: Extends Collection and adds a well-defined order, allowing operations at the beginning and end.
List: Stores ordered elements, allows duplicates, and supports index-based access.
Set: Represents a collection of unique elements, with no duplicates allowed.
- SortedSet: Maintains the unique elements in a sorted order.
- NavigableSet: Adds search and navigation methods (e.g., finding elements less than or greater than a specific value).
Queue: A collection for First-In, First-Out (FIFO) processing.
- Deque (Double-Ended Queue): Allows operations at both ends of the queue.
Map: Stores key-value pairs. Keys must be unique. Note: The Map interface does not inherit from the Collection interface.
- SortedMap: Stores key-value pairs sorted by key.
- NavigableMap: Adds search and navigation methods for keys.

Key Methods in the `Collection` Interface

The Collection interface is the root of the hierarchy and defines several key methods:

add(element): Adds an element.
remove(element): Removes an element.
size(): Returns the number of elements.
isEmpty(): Checks if the collection is empty.
clear(): Removes all elements.
contains(element): Checks if an element exists.
containsAll(collection): Checks if all elements from another collection exist.
addAll(collection): Adds all elements from another collection.
removeAll(collection): Removes all matching elements.
retainAll(collection): Keeps only the elements present in another collection.
iterator(): Returns an iterator to traverse the elements.
stream(): Returns a sequential stream for functional-style operations.
parallelStream(): Returns a parallel stream, which can improve performance for large datasets by processing elements concurrently.

Key Methods in the `SequencedCollection` Interface

Introduced in JDK 21, SequencedCollection extends Collection and represents a collection with a well-defined encounter order.

Key methods include: - addFirst(element): Adds an element at the beginning. - addLast(element): Adds an element at the end. - getFirst(): Gets the first element. - getLast(): Gets the last element. - removeFirst(): Removes the first element. - removeLast(): Removes the last element. - reversed(): Returns a reverse-ordered view of the collection.

The `List` Interface

The List interface extends SequencedCollection and provides methods for position-based access. Lists maintain insertion order and allow duplicate elements.

Here is a simple example using ArrayList:

List<String> numbers = new ArrayList<>();
numbers.add("10"); // index 0
numbers.add("20"); // index 1
numbers.add("30"); // index 2
// numbers contains [10, 20, 30]

// Add element at a specific index
numbers.add(1, "15"); // at index 1
// numbers is now [10, 15, 20, 30]

// Lists allow duplicates
numbers.add("20");
// numbers is now [10, 15, 20, 30, 20]

// Fast lookup by index
String element = numbers.get(2); // returns "20"

The List interface provides additional methods such as: - addAll(index, collection): Adds all elements from another collection at a specific index. - get(index): Gets an element at a specific index. - set(index, element): Replaces an element at a specific index. - remove(index): Removes an element at a specific index. - indexOf(element): Finds the first index of an element. - lastIndexOf(element): Finds the last index of an element. - subList(fromIndex, toIndex): Creates a view of a portion of the list. - List.of(...): A static factory method (since JDK 9) to create an unmodifiable list.

Choosing a `List` Implementation

ArrayList: Best for fast random access. It uses a dynamic array internally. Use it when you need fast element access via get(index) and most insertions/removals are at the end. Avoid it for frequent insertions/deletions in the middle, as this requires shifting elements.
LinkedList: Best for frequent insertions and deletions. It uses a doubly-linked list. Use it when you have frequent modifications in the middle of the list. Avoid it when you need fast random access, as it requires traversing the list from the beginning. It also has higher memory overhead due to storing pointers.
Vector: A legacy class that is thread-safe because its methods are synchronized. It's generally slower than ArrayList due to synchronization overhead. Consider using it for legacy code or when simple thread safety is required for a list shared between multiple threads.
CopyOnWriteArrayList: A thread-safe variant of ArrayList. It creates a new copy of the array on each write operation (add, remove). This makes it safe for concurrent read-heavy scenarios. Avoid it if you have frequent writes or a very large list, as copying the array can be expensive.

How to Sort a List

There are several approaches to sort a list:

Collections.sort(): Best for simple sorting of strings or numbers using their natural ordering (alphabetical or ascending). This method modifies the original list in place.

List<String> names = new ArrayList<>(List.of("Four", "One", "Three", "Two"));
Collections.sort(names);
// names is now ["Four", "One", "Three", "Two"] -> sorted alphabetically

Comparable Interface: Implement this interface in your class to define a default or "natural" sorting order. The class itself controls the sorting logic by implementing the compareTo method.

class Cricketer implements Comparable<Cricketer> {
    private int runs;
    // constructor, getters...

    @Override
    public int compareTo(Cricketer that) {
        return Integer.compare(this.runs, that.runs);
    }
}
// Now you can use Collections.sort(listOfCricketers);

Comparator Interface: Implement this interface in a separate class to define custom sorting criteria. This is useful when you need multiple sorting orders or cannot modify the original class.


class DescendingSorter implements Comparator<Cricketer> {
    @Override
    public int compare(Cricketer c1, Cricketer c2) {
        return Integer.compare(c2.getRuns(), c1.getRuns()); // descending
    }
}
// Usage:
Collections.sort(players, new DescendingSorter());

Set Interfaces

Set: Extends Collection and guarantees no duplicate elements.
SequencedSet: A Set with a well-defined encounter order.
SortedSet: Extends SequencedSet and maintains elements in a sorted order.
NavigableSet: Extends SortedSet and adds navigation methods.

Here are some examples:

// HashSet (basic Set)
Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple"); // This is ignored
// set contains ["Apple", "Banana"]

// LinkedHashSet (SequencedSet)
SequencedSet<Integer> sequencedSet = new LinkedHashSet<>();
sequencedSet.add(1);
sequencedSet.add(2);
sequencedSet.add(3);
sequencedSet.addFirst(0);
sequencedSet.addLast(4);
// sequencedSet contains [0, 1, 2, 3, 4] in insertion order

// TreeSet (SortedSet & NavigableSet)
NavigableSet<Integer> navSet = new TreeSet<>(Set.of(10, 20, 30));
// navSet contains [10, 20, 30] in sorted order
System.out.println(navSet.lower(20)); // prints 10
System.out.println(navSet.ceiling(20)); // prints 20

Choosing a `Set` Implementation

HashSet: For fast lookups when order is not important. It's unordered and not thread-safe.
LinkedHashSet: Maintains insertion order. Use it when you need a predictable iteration order. It's slightly slower than HashSet and not thread-safe.
TreeSet: For sorted elements. It implements NavigableSet and is backed by a red-black tree. Use it when you need elements to be sorted or require range-based queries. It's not thread-safe.
CopyOnWriteArraySet: A thread-safe Set implementation. Good for read-heavy concurrent scenarios. Avoid with frequent writes.
ConcurrentSkipListSet: A thread-safe version of TreeSet. Use it in multi-threaded applications that need a sorted set.

Queue Interfaces

Queue: Holds elements for processing in FIFO (First-In, First-Out) order.
Deque: A double-ended queue that allows insertion and removal from both ends.
BlockingQueue: A thread-safe queue for producer-consumer scenarios. It blocks when trying to add to a full queue or take from an empty queue.

Example of a Queue: ```java Queue queue = new LinkedList<>(); queue.offer("A"); queue.offer("B");

System.out.println(queue.peek()); // "A" (retrieves but doesn't remove) System.out.println(queue.poll()); // "A" (retrieves and removes) System.out.println(queue.peek()); // "B" ```

Important `Queue` Implementations

PriorityQueue: A queue where elements are ordered by priority (natural order or a custom comparator).
ArrayDeque: An array-based implementation of Deque.
ArrayBlockingQueue: An array-backed, fixed-size BlockingQueue.
LinkedBlockingQueue: A BlockingQueue implemented with a linked list.
ConcurrentLinkedQueue: A thread-safe Queue.
ConcurrentLinkedDeque: A thread-safe Deque.

Map Interfaces

Map: Stores key-value pairs. Keys are unique. Does not extend Collection.
SequencedMap: A Map that maintains a well-defined sequence of entries.
SortedMap: A Map that maintains keys in a sorted order.
NavigableMap: Extends SortedMap with navigation methods.

Example of a Map: ```java Map map = new HashMap<>(); map.put("Alice", 25); map.put("Bob", 30);

Integer age = map.get("Alice"); // returns 25 ```

Choosing a `Map` Implementation

HashMap: The most common implementation. It's unordered and not thread-safe.
LinkedHashMap: Maintains insertion order. It's not thread-safe.
TreeMap: A sorted key-value store that implements NavigableMap. Keys are sorted. It's not thread-safe.
ConcurrentHashMap: A thread-safe map with high concurrency. A concurrent version of HashMap.
ConcurrentSkipListMap: A thread-safe sorted map. A concurrent version of TreeMap.