Java Collections

Java Collections Framework

Before Java 2, classes like Vector, Stack, and Hashtable were used to manage groups of objects. However, they lacked a consistent design and were not easily interoperable.

The Java Collections Framework (JCF), introduced in Java 1.2, provides a unified architecture for representing and manipulating collections (groups of objects). Key goals include:

• High Performance: Efficient implementations for common data structures.
• Interoperability: Allows different collection types to work together seamlessly.
• Extensibility: Easy to extend or adapt existing collections or implement new ones.
• Reduced Programming Effort: Provides standard data structures and algorithms, saving developers time.

The framework is built upon:

• Interfaces: Define the abstract data types (ADTs) for different kinds of collections (like List, Set, Map). They specify the contract (methods) without detailing the implementation. Code should generally be written against interfaces (e.g., List<String> list = new ArrayList<>();).
• Implementations (Classes): Concrete classes that provide specific data structures implementing the collection interfaces (e.g., ArrayList, LinkedList, HashSet, HashMap).
• Algorithms: Utility methods (often static, primarily in the Collections class) that perform operations like sorting, searching, shuffling, etc., on collections polymorphically.

Maps (Map interface and implementations like HashMap) are also part of the framework. While not strictly Collections (they store key-value pairs, not single elements), they are closely integrated.

Core Collection Interfaces

The main interfaces form a hierarchy:

Interface	Description
Collection<E>	The root interface for most collections (excluding Maps). Represents a group of objects (elements). Defines basic methods like add(), remove(), size(), iterator(), contains().
List<E>	Extends Collection. Represents an ordered sequence of elements (a sequence). Allows duplicate elements and positional access (by index). Common implementations: ArrayList, LinkedList.
Set<E>	Extends Collection. Represents a collection that contains no duplicate elements. Order is generally not guaranteed (except in LinkedHashSet, SortedSet). Common implementations: HashSet, LinkedHashSet, TreeSet.
SortedSet<E>	Extends Set. Represents a Set whose elements are maintained in sorted order (either natural ordering or by a Comparator). Implemented by TreeSet.
NavigableSet<E>	Extends SortedSet. Adds navigation methods (e.g., finding closest matches) and ability to iterate in descending order. Implemented by TreeSet.
Queue<E>	Extends Collection. Represents a collection typically used for holding elements prior to processing (e.g., FIFO - First-In, First-Out). Implementations: LinkedList, PriorityQueue, ArrayDeque.
Deque<E>	Extends Queue. Represents a double-ended queue, supporting element insertion and removal at both ends. Implementations: ArrayDeque, LinkedList.

Core Map Interfaces

Interface	Description
Map<K, V>	Represents a mapping from unique keys (K) to values (V). Each key can map to at most one value. Not part of the Collection hierarchy. Common implementations: HashMap, LinkedHashMap, TreeMap.
SortedMap<K, V>	Extends Map. Represents a Map whose entries are maintained in ascending key order (natural ordering or by Comparator). Implemented by TreeMap.
NavigableMap<K, V>	Extends SortedMap. Adds navigation methods for keys (e.g., finding closest matches). Implemented by TreeMap.
Map.Entry<K, V>	An inner interface of Map. Represents a single key-value pair within a Map.

Common Implementation Classes

Java provides several standard implementation classes:

Class	Interface(s) Implemented	Description & Use Case
ArrayList<E>	List<E>	Resizable array implementation. Fast random access (by index), relatively slower insertions/deletions in the middle. Good general-purpose list.
LinkedList<E>	List<E>, Deque<E>	Doubly-linked list implementation. Fast insertions/deletions at ends and middle (if iterator is positioned), slower random access. Good for frequent insertions/deletions, use as Queue/Stack.
HashSet<E>	Set<E>	Uses a hash table. Offers fast add, remove, contains (average O(1)). Does not guarantee order. Use when uniqueness is needed and order doesn’t matter.
LinkedHashSet<E>	Set<E>	Hash table + linked list implementation. Like HashSet but maintains insertion order of elements. Slightly slower than HashSet due to list maintenance.
TreeSet<E>	NavigableSet<E>, SortedSet<E>	Uses a tree structure (Red-Black tree). Stores elements in sorted order (natural or via Comparator). Slower add/remove/contains (O(log n)) than HashSet, but provides ordered traversal.
HashMap<K, V>	Map<K, V>	Hash table based implementation. Fast put, get, containsKey (average O(1)). Does not guarantee order. The standard, general-purpose Map implementation.
LinkedHashMap<K, V>	Map<K, V>	Hash table + linked list implementation. Like HashMap but maintains insertion order or access order of entries. Useful for caches (LRU).
TreeMap<K, V>	NavigableMap<K, V>, SortedMap<K, V>	Uses a tree structure (Red-Black tree). Stores entries sorted by key (natural or via Comparator). Slower put/get/containsKey (O(log n)) than HashMap, but provides ordered iteration by key.
ArrayDeque<E>	Deque<E>	Resizable array implementation of Deque. Efficient add/remove at both ends. Good choice for stacks and queues.

Legacy Classes (Generally Avoid in New Code):

• Vector<E>: Synchronized version of ArrayList. Slower due to synchronization overhead. Prefer ArrayList and external synchronization if needed, or use concurrent collections.
• Stack<E>: Extends Vector. LIFO stack implementation. Prefer ArrayDeque for stack operations.
• Hashtable<K, V>: Synchronized version of HashMap. Does not permit null keys or values. Prefer HashMap or ConcurrentHashMap.
• Dictionary<K, V>: Abstract predecessor of Map. Obsolete.
• Properties: Subclass of Hashtable. Still commonly used for configuration files (key-value pairs are Strings).

Iterating Through Collections

Common ways to iterate:

• Enhanced For-Loop (Foreach): The simplest and often preferred way. Works for any class implementing Iterable (which includes all Collections).
• Iterator: Provides hasNext(), next(), and remove() methods. Required when you need to remove elements during iteration.
• Streams API (Java 8+): Offers a functional approach using methods like forEach(), map(), filter(), collect(). Very powerful for processing sequences of elements.

Example using Iterator:

List<String> names = new ArrayList<>(Arrays.asList("Alice", "Bob", "Charlie"));
Iterator<String> iterator = names.iterator();
while (iterator.hasNext()) {
    String name = iterator.next();
    System.out.println(name);
    if (name.equals("Bob")) {
        iterator.remove(); // Safely remove element during iteration
    }
}
System.out.println("After removal: " + names); // Output: [Alice, Charlie]

The Collections Utility Class

The java.util.Collections class provides static utility methods for operating on or returning collections. Examples:

• sort(List<T> list) / sort(List<T> list, Comparator<? super T> c): Sorts a list.
• binarySearch(List<? extends Comparable<? super T>> list, T key): Searches a sorted list.
• reverse(List<?> list): Reverses the order of elements in a list.
• shuffle(List<?> list): Randomly permutes elements in a list.
• max(Collection<? extends T> coll) / min(...): Finds the maximum/minimum element according to natural ordering.
• frequency(Collection<?> c, Object o): Counts occurrences of an element.
• synchronizedList(List<T> list) / synchronizedSet(...) / synchronizedMap(...): Returns thread-safe wrappers (though often less efficient than concurrent collections).
• unmodifiableList(List<? extends T> list) / unmodifiableSet(...) / unmodifiableMap(...): Returns unmodifiable views of collections.

The Comparator Interface

Used when you need custom sorting logic or want to sort objects of classes that don’t implement Comparable or whose natural ordering isn’t desired. The Comparator interface defines the int compare(T o1, T o2) method.

With Java 8+, Comparator can often be implemented concisely using lambda expressions or method references.

List<String> words = Arrays.asList("apple", "banana", "kiwi", "orange");
// Sort by length using a lambda expression
words.sort((s1, s2) -> Integer.compare(s1.length(), s2.length()));
// Or using Comparator.comparingInt method reference
// words.sort(Comparator.comparingInt(String::length));
System.out.println(words); // Output: [kiwi, apple, orange, banana]

Streams API for Collection Processing

Java 8 introduced the Streams API (java.util.stream), providing a powerful functional style for processing sequences of elements, including collections.

Example: Filtering and Collecting

List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "Anna");

// Get a list of names starting with 'A', converted to uppercase
List<String> aNamesUpper = names.stream() // Get a stream from the list
                                .filter(name -> name.startsWith("A")) // Keep names starting with A
                                .map(String::toUpperCase) // Convert remaining names to uppercase
                                .collect(Collectors.toList()); // Collect results into a new List

System.out.println(aNamesUpper); // Output: [ALICE, ANNA]

Summary

The Java Collections Framework is essential for any Java developer. It provides a robust set of interfaces, implementations, and algorithms for managing groups of objects efficiently and effectively. Prefer coding to interfaces, choose implementations based on performance needs (access speed, insertion/deletion speed, memory usage, ordering), and leverage the Streams API for complex processing tasks.