Java Collections Framework¶

Overview¶

The Java Collections Framework provides a unified architecture for representing and manipulating collections of objects. It offers numerous interfaces, implementations, and algorithms to handle groups of objects efficiently. This guide covers the essential components of the framework, their usage patterns, performance characteristics, and best practices.

Prerequisites¶

Basic Java programming knowledge
Understanding of object-oriented programming concepts
Familiarity with Java generics

Learning Objectives¶

Understand the Java Collections Framework hierarchy and components
Learn to choose appropriate collection types for different scenarios
Master commonly used collection interfaces and implementations
Work with Lists, Sets, Queues, and Maps effectively
Understand collection utility classes and algorithms
Apply best practices for collection performance and usage
Learn about thread-safe collections

Collections Framework Overview¶

The Java Collections Framework is organized into interfaces, implementations, and utility classes:

Collection Hierarchy Diagram:
                               Iterable
                                  |
                              Collection
                /               |              \
              Set              List            Queue
             /   \              |               |
       HashSet  SortedSet    ArrayList        Deque
        /         |           LinkedList      /    \
  LinkedHashSet  NavigableSet              ArrayDeque PriorityQueue
                   |
                 TreeSet

Map Hierarchy:
             Map
           /     \
       HashMap   SortedMap
        /            |
LinkedHashMap    NavigableMap
                     |
                   TreeMap

Key Components:¶

Interfaces: Define the abstract data types (e.g., List, Set, Queue, Map)
Implementations: Concrete classes implementing the interfaces (e.g., ArrayList, HashSet)
Algorithms: Static methods that perform operations on collections (e.g., sorting, searching)

Collection Interfaces¶

Collection¶

The root interface in the collection hierarchy.

Collection<String> collection = new ArrayList<>();
collection.add("Apple");
collection.add("Banana");
collection.add("Cherry");

System.out.println(collection.size());       // 3
System.out.println(collection.contains("Apple"));  // true
collection.remove("Banana");
System.out.println(collection.size());       // 2

Key methods: - boolean add(E e): Adds element to collection - boolean remove(Object o): Removes element from collection - boolean contains(Object o): Checks if collection contains element - int size(): Returns number of elements - boolean isEmpty(): Checks if collection is empty - void clear(): Removes all elements - Iterator<E> iterator(): Returns iterator over elements

List¶

An ordered collection that allows duplicate elements.

List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Apple");  // Duplicates allowed
list.add(1, "Orange");  // Insertion at specific position

System.out.println(list);  // [Apple, Orange, Banana, Apple]
System.out.println(list.get(1));  // Orange

Key methods (in addition to Collection methods): - E get(int index): Returns element at specified position - E set(int index, E element): Replaces element at specified position - void add(int index, E element): Inserts element at specified position - E remove(int index): Removes element at specified position - int indexOf(Object o): Returns first index of element - int lastIndexOf(Object o): Returns last index of element - List<E> subList(int fromIndex, int toIndex): Returns a view of a portion of the list

Set¶

A collection that cannot contain duplicate elements.

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple");  // Duplicate not added

System.out.println(set.size());  // 2
System.out.println(set);  // [Apple, Banana] (order not guaranteed)

Queue¶

A collection designed for holding elements before processing, typically in FIFO order.

Queue<String> queue = new LinkedList<>();
queue.offer("First");
queue.offer("Second");
queue.offer("Third");

System.out.println(queue.peek());  // First (view head of queue)
System.out.println(queue.poll());  // First (remove head of queue)
System.out.println(queue.poll());  // Second

Key methods: - boolean offer(E e): Adds element to queue (preferred over add()) - E poll(): Retrieves and removes head of queue (returns null if empty) - E peek(): Retrieves but does not remove head (returns null if empty)

Deque¶

A double-ended queue that supports element insertion and removal at both ends.

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("First");
deque.addLast("Last");
deque.offerFirst("New First");
deque.offerLast("New Last");

System.out.println(deque);  // [New First, First, Last, New Last]
System.out.println(deque.pollFirst());  // New First
System.out.println(deque.pollLast());   // New Last

Key methods: - void addFirst(E e) / boolean offerFirst(E e): Add to front - void addLast(E e) / boolean offerLast(E e): Add to end - E removeFirst() / E pollFirst(): Remove from front - E removeLast() / E pollLast(): Remove from end - E getFirst() / E peekFirst(): Examine front - E getLast() / E peekLast(): Examine end

Map¶

A mapping from keys to values, where each key can map to at most one value.

Map<String, Integer> map = new HashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Cherry", 30);

System.out.println(map.get("Banana"));  // 20
map.put("Banana", 25);  // Replace value
System.out.println(map.get("Banana"));  // 25

Key methods: - V put(K key, V value): Associates value with key - V get(Object key): Returns value for key (or null) - V remove(Object key): Removes mapping for key - boolean containsKey(Object key): Checks if key exists - boolean containsValue(Object value): Checks if value exists - Set<K> keySet(): Returns set of all keys - Collection<V> values(): Returns collection of all values - Set<Map.Entry<K,V>> entrySet(): Returns set of key-value mappings

List Implementations¶

ArrayList¶

A resizable array implementation of the List interface.

List<String> arrayList = new ArrayList<>();
arrayList.add("Apple");
arrayList.add("Banana");
arrayList.add("Cherry");

// Random access (constant time)
System.out.println(arrayList.get(1));  // Banana

// Efficient iteration
for (String fruit : arrayList) {
    System.out.println(fruit);
}

Characteristics: - Dynamic resizing: Initial capacity is 10, grows by 50% when full - Fast random access: O(1) time - Fast iteration: Efficient for large lists - Slow insertion/deletion in middle: O(n) time (elements must be shifted) - Not synchronized (not thread-safe)

When to use: - Random access is common - List size changes infrequently - Iteration is the primary operation

LinkedList¶

A doubly-linked list implementation of the List and Deque interfaces.

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("Apple");
linkedList.add("Banana");
linkedList.addFirst("Kiwi");
linkedList.addLast("Orange");

System.out.println(linkedList);  // [Kiwi, Apple, Banana, Orange]

// Using as a deque
System.out.println(linkedList.pollFirst());  // Kiwi
System.out.println(linkedList.pollLast());   // Orange

Characteristics: - Node-based structure: Each element references previous and next elements - Slow random access: O(n) time (must traverse from beginning or end) - Fast insertion/deletion: O(1) time once position is found - More memory overhead due to node references - Not synchronized (not thread-safe)

When to use: - Frequent insertions/deletions in the middle - Implementation of stacks or queues - No need for random access

Set Implementations¶

HashSet¶

An implementation of the Set interface backed by a HashMap.

Set<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Apple");  // Duplicate not added

System.out.println(hashSet.size());  // 2
System.out.println(hashSet.contains("Banana"));  // true

Characteristics: - No guaranteed iteration order - O(1) time complexity for basic operations (add, remove, contains) - Allows one null element - Not synchronized (not thread-safe) - Based on hash table; elements should override hashCode() and equals()

When to use: - Fast lookup, insertion, and deletion - Don't need ordered iteration - Need to eliminate duplicates

LinkedHashSet¶

A HashSet with predictable iteration order.

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Cherry");
linkedHashSet.add("Apple");
linkedHashSet.add("Banana");

// Maintains insertion order
for (String fruit : linkedHashSet) {
    System.out.println(fruit);  // Cherry, Apple, Banana in that order
}

Characteristics: - Maintains insertion order using a doubly-linked list - O(1) time complexity for basic operations - Slightly slower than HashSet due to linked list maintenance - Not synchronized (not thread-safe)

When to use: - Need HashSet performance - Need predictable (insertion-order) iteration

TreeSet¶

A NavigableSet implementation based on a TreeMap.

TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("Cherry");
treeSet.add("Apple");
treeSet.add("Banana");

// Navigable operations
System.out.println(treeSet.first());  // Apple
System.out.println(treeSet.last());   // Cherry
System.out.println(treeSet.lower("Banana"));  // Apple
System.out.println(treeSet.higher("Banana")); // Cherry

// Sorted iteration
for (String fruit : treeSet) {
    System.out.println(fruit);  // Apple, Banana, Cherry (sorted order)
}

Characteristics: - Elements sorted by natural order or Comparator - O(log n) time complexity for basic operations - NavigableSet operations: first(), last(), lower(), higher(), etc. - Not synchronized (not thread-safe) - Elements must be comparable

When to use: - Need sorted iteration - Need to find closest matches or ranges of elements - Need to access first or last elements quickly

Queue and Deque Implementations¶

ArrayDeque¶

A resizable array implementation of the Deque interface.

Deque<String> arrayDeque = new ArrayDeque<>();
arrayDeque.addFirst("First");
arrayDeque.addLast("Last");
arrayDeque.offerFirst("New First");
arrayDeque.offerLast("New Last");

System.out.println(arrayDeque);  // [New First, First, Last, New Last]

// Stack operations (LIFO)
arrayDeque.push("Top");          // Add to front
System.out.println(arrayDeque.pop());  // Top (remove from front)

// Queue operations (FIFO)
arrayDeque.offer("End");         // Add to end
System.out.println(arrayDeque.poll()); // New First (remove from front)

Characteristics: - Faster than Stack when used as a stack - Faster than LinkedList when used as a queue - No capacity restrictions, grows as needed - Not thread-safe - Null elements prohibited

When to use: - Versatile double-ended queue (both stack and queue) - Better performance than LinkedList for most operations - Need to add or remove from both ends

PriorityQueue¶

A queue that orders elements according to their natural ordering or a provided Comparator.

// Natural ordering
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);
minHeap.offer(1);

// Elements come out in priority order (smallest first by default)
while (!minHeap.isEmpty()) {
    System.out.print(minHeap.poll() + " ");  // 1 2 5 8
}

// Custom comparator (max heap)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.addAll(Arrays.asList(5, 2, 8, 1));

while (!maxHeap.isEmpty()) {
    System.out.print(maxHeap.poll() + " ");  // 8 5 2 1
}

Characteristics: - Always removes the highest-priority element first - O(log n) time for offer, poll, and remove operations - O(1) time for peek operations - Not synchronized (not thread-safe) - Not necessarily FIFO for equal-priority elements

When to use: - Task scheduling by priority - Algorithms like Dijkstra's or Prim's - Heap implementation - Process elements in priority order

Map Implementations¶

HashMap¶

A hash table-based implementation of the Map interface.

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Apple", 10);
hashMap.put("Banana", 20);
hashMap.put("Cherry", 30);

System.out.println(hashMap.get("Banana"));  // 20

// Iterating over a HashMap
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Characteristics: - O(1) time complexity for basic operations - No guaranteed iteration order - Allows one null key and multiple null values - Not synchronized (not thread-safe) - Initial capacity and load factor affect performance

When to use: - Fast lookup by key - Don't need ordered iteration - Common general-purpose map implementation

LinkedHashMap¶

A HashMap with predictable iteration order.

Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("Cherry", 30);
linkedHashMap.put("Apple", 10);
linkedHashMap.put("Banana", 20);

// Maintains insertion order
for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
    // Prints: Cherry: 30, Apple: 10, Banana: 20
}

// LRU cache with access-order (rather than insertion-order)
Map<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true);
lruCache.put("A", 1);
lruCache.put("B", 2);
lruCache.put("C", 3);
lruCache.get("A");  // Access A
// Now the order is: B, C, A (A moved to end due to access)

Characteristics: - Maintains insertion order or access order - O(1) time complexity for basic operations - Slightly slower than HashMap due to linked list maintenance - Not synchronized (not thread-safe)

When to use: - Need HashMap performance - Need predictable iteration order - Implementing LRU caches (with access-order constructor)

TreeMap¶

A NavigableMap implementation based on a red-black tree.

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("Cherry", 30);
treeMap.put("Apple", 10);
treeMap.put("Banana", 20);

// Sorted by keys
for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
    // Prints: Apple: 10, Banana: 20, Cherry: 30
}

// NavigableMap operations
System.out.println(treeMap.firstKey());  // Apple
System.out.println(treeMap.lastKey());   // Cherry
System.out.println(treeMap.lowerKey("Banana"));  // Apple
System.out.println(treeMap.higherKey("Banana")); // Cherry
System.out.println(treeMap.subMap("Apple", "Cherry")); // {Apple=10, Banana=20}

Characteristics: - Keys sorted by natural order or Comparator - O(log n) time complexity for basic operations - NavigableMap operations: firstKey(), lastKey(), etc. - Not synchronized (not thread-safe) - Keys must be comparable

When to use: - Need keys in sorted order - Need to find closest matches or ranges of keys - Need to access first or last entries quickly

Utility Classes¶

Collections¶

A utility class with static methods that operate on or return collections.

List<String> list = new ArrayList<>(Arrays.asList("Banana", "Apple", "Cherry"));

// Sorting
Collections.sort(list);  // [Apple, Banana, Cherry]

// Binary search (on sorted list)
int index = Collections.binarySearch(list, "Banana");  // 1

// Finding min/max
String min = Collections.min(list);  // Apple
String max = Collections.max(list);  // Cherry

// Shuffling
Collections.shuffle(list);  // Random order

// Frequency and disjoint
List<String> fruits = Arrays.asList("Apple", "Banana", "Apple");
int freq = Collections.frequency(fruits, "Apple");  // 2
boolean disjoint = Collections.disjoint(
    Arrays.asList("Apple", "Banana"),
    Arrays.asList("Cherry", "Date")
);  // true (no common elements)

// Unmodifiable views
List<String> unmodifiableList = Collections.unmodifiableList(list);
// unmodifiableList.add("Date");  // UnsupportedOperationException

// Synchronized views
List<String> synchronizedList = Collections.synchronizedList(list);

Arrays¶

A utility class with static methods for manipulating arrays.

// Creating Lists from arrays
String[] array = {"Apple", "Banana", "Cherry"};
List<String> list = Arrays.asList(array);
// Note: The list is fixed-size and backed by the array

// Converting to array
List<String> fruitList = new ArrayList<>(Arrays.asList("Apple", "Banana"));
String[] fruitArray = fruitList.toArray(new String[0]);

// Sorting
Arrays.sort(array);

// Binary search
int index = Arrays.binarySearch(array, "Banana");

// Filling
Arrays.fill(array, "Unknown");

// Comparing
int[] arr1 = {1, 2, 3};
int[] arr2 = {1, 2, 3};
boolean equal = Arrays.equals(arr1, arr2);  // true

// Deep operations for multi-dimensional arrays
int[][] matrix1 = {{1, 2}, {3, 4}};
int[][] matrix2 = {{1, 2}, {3, 4}};
boolean deepEqual = Arrays.deepEquals(matrix1, matrix2);  // true

Iterating Collections¶

Traditional for-loop¶

List<String> list = Arrays.asList("Apple", "Banana", "Cherry");

// For lists with random access
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

Enhanced for-loop (for-each)¶

// Simpler, preferred for most cases
for (String item : list) {
    System.out.println(item);
}

Iterator¶

// Using Iterator
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    System.out.println(item);

    // Safe removal during iteration
    if (item.equals("Banana")) {
        iterator.remove();
    }
}

ListIterator (for Lists)¶

// ListIterator allows bidirectional traversal
ListIterator<String> listIterator = list.listIterator();

// Forward
while (listIterator.hasNext()) {
    System.out.println(listIterator.next());
}

// Backward
while (listIterator.hasPrevious()) {
    System.out.println(listIterator.previous());
}

Streams (Java 8+)¶

// Declarative approach
list.stream()
    .filter(s -> s.startsWith("A"))
    .map(String::toUpperCase)
    .forEach(System.out::println);

Map Iteration¶

Map<String, Integer> map = Map.of("Apple", 10, "Banana", 20, "Cherry", 30);

// Iterating over entries
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Iterating over keys
for (String key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}

// Iterating over values
for (Integer value : map.values()) {
    System.out.println(value);
}

// Using forEach (Java 8+)
map.forEach((key, value) -> System.out.println(key + ": " + value));

Comparators and Comparable Interface¶

Comparable¶

The Comparable interface allows classes to define their natural ordering.

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    // Constructor, getters, setters

    @Override
    public int compareTo(Person other) {
        // Natural ordering by age
        return Integer.compare(this.age, other.age);
    }
}

// Usage
List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
people.add(new Person("Charlie", 35));

Collections.sort(people);  // Sorts by age using compareTo

Comparator¶

The Comparator interface allows for comparison logic external to the class being compared.

// Comparator for name-based sorting
Comparator<Person> byName = Comparator.comparing(Person::getName);

// Comparator for age-based sorting (alternative to implementing Comparable)
Comparator<Person> byAge = Comparator.comparing(Person::getAge);

// Reversed comparator
Comparator<Person> byAgeDescending = byAge.reversed();

// Chained comparators
Comparator<Person> byAgeAndName = byAge.thenComparing(byName);

// Usage
Collections.sort(people, byName);  // Sort by name
Collections.sort(people, byAgeAndName);  // Sort by age, then by name

Thread-Safe Collections¶

Synchronized Collections¶

Wrappers for existing collections, providing synchronized access.

List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(new HashMap<>());
Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>());

// Important: Iteration must be manually synchronized
synchronized (synchronizedList) {
    Iterator<String> iterator = synchronizedList.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

Concurrent Collections¶

Designed for concurrent access, generally offering better performance than synchronized collections.

ConcurrentHashMap¶

Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put("Apple", 10);
concurrentMap.put("Banana", 20);

// No need to synchronize for most operations
for (Map.Entry<String, Integer> entry : concurrentMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Atomic operations
concurrentMap.computeIfAbsent("Cherry", k -> 30);
concurrentMap.computeIfPresent("Apple", (k, v) -> v + 5);

CopyOnWriteArrayList¶

List<String> copyOnWriteList = new CopyOnWriteArrayList<>();
copyOnWriteList.add("Apple");
copyOnWriteList.add("Banana");

// Safe iteration without synchronization
for (String item : copyOnWriteList) {
    System.out.println(item);
    // Modifications create a new copy of the underlying array
    copyOnWriteList.add("Cherry");  // Will not affect this iteration
}

BlockingQueue¶

BlockingQueue<String> blockingQueue = new LinkedBlockingQueue<>(10);  // Capacity 10

// Producer thread
new Thread(() -> {
    try {
        blockingQueue.put("Task 1");  // Blocks if queue is full
        blockingQueue.put("Task 2");
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

// Consumer thread
new Thread(() -> {
    try {
        String task = blockingQueue.take();  // Blocks if queue is empty
        System.out.println("Processing: " + task);
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

Best Practices¶

Choose the right collection:
Use ArrayList for random access and frequent iteration
Use LinkedList for frequent insertions/removals in the middle
Use HashSet for fast lookup without duplicates
Use LinkedHashSet for ordered iteration without duplicates
Use TreeSet for sorted elements
Use HashMap for key-value mapping with fast lookups
Use TreeMap for key-value mapping with sorted keys

Specify initial capacity when you know the approximate size to avoid resizing:

List<String> list = new ArrayList<>(1000);
Map<String, Integer> map = new HashMap<>(1000, 0.75f);

Use the interface type as variable type, not the implementation:

// Good
List<String> list = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();

// Avoid
ArrayList<String> list = new ArrayList<>();
HashMap<String, Integer> map = new HashMap<>();

Use enhanced for-loop for simple iteration:

for (String item : list) {
    System.out.println(item);
}

Use Iterator for safe removal during iteration:

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (condition(item)) {
        iterator.remove();  // Safe removal
    }
}

Use concurrent collections for multithreaded scenarios:

Map<String, Integer> map = new ConcurrentHashMap<>();
List<String> list = new CopyOnWriteArrayList<>();

Consider immutable collections when contents don't change:

// Java 9+
List<String> immutableList = List.of("Apple", "Banana", "Cherry");
Map<String, Integer> immutableMap = Map.of("Apple", 10, "Banana", 20);

Optimize Map key classes by implementing hashCode() and equals() properly.
Use disjoint collections when appropriate to minimize dependencies.
Leverage the Collections utility class for common operations.

Common Pitfalls and How to Avoid Them¶

ConcurrentModificationException:

// Incorrect - Modifying while iterating
for (String item : list) {
    if (item.equals("Banana")) {
        list.remove(item);  // Throws ConcurrentModificationException
    }
}

// Correct - Use Iterator's remove method
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.equals("Banana")) {
        iterator.remove();  // Safe removal
    }
}

// Alternative - Create a copy or use removeIf (Java 8+)
list.removeIf(item -> item.equals("Banana"));

Nulls in collections:

// Some collections don't allow null
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put(null, 10);  // NullPointerException

ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put(null, 10);  // NullPointerException

Performance issues with large collections:
LinkedList: O(n) access time vs ArrayList's O(1)
ArrayList: O(n) insertion/deletion in the middle vs LinkedList's O(1)
Frequent resizing: Set initial capacity for known sizes

Unintended list modifications when using Arrays.asList():

// asList returns a fixed-size list backed by the array
List<String> list = Arrays.asList("Apple", "Banana");
list.add("Cherry");  // UnsupportedOperationException

// Instead, create a new ArrayList
List<String> modifiableList = new ArrayList<>(Arrays.asList("Apple", "Banana"));
modifiableList.add("Cherry");  // Works fine

Thread-safety issues:

// Non-thread-safe
Map<String, Integer> map = new HashMap<>();

// Thread-safe but with performance overhead
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(map);

// Better for concurrent access
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();

Inefficient list-to-array conversion:

// Inefficient - requires two arrays
String[] array = list.toArray(new String[list.size()]);

// Better (Java 11+) - zero length array as template
String[] betterArray = list.toArray(new String[0]);

Forgetting to implement equals() and hashCode() for custom classes used as keys:

class Product {
    private String name;
    private double price;

    // Without proper equals() and hashCode(),
    // two Products with same values will be treated as different keys

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Product product = (Product) o;
        return Double.compare(product.price, price) == 0 &&
                Objects.equals(name, product.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, price);
    }
}

Resources for Further Learning¶

Official Documentation:
Java Collections Framework Overview
Java API: Collection
Books:
"Java Generics and Collections" by Maurice Naftalin and Philip Wadler
"Effective Java" by Joshua Bloch (Chapter on Collections)
Online Resources:
Baeldung Java Collections Tutorials
Oracle Java Tutorials: Collections
Practice Platforms:
LeetCode - Array and String problems
HackerRank - Java Collections challenges

Practice Exercises¶

Frequency Counter: Create a program that counts the frequency of words in a text file, sorting them from most to least frequent.
Custom Sorting: Implement a program that sorts a list of students by multiple criteria (GPA, name, then ID).
Playlist Manager: Create a music playlist manager that allows adding, removing, and shuffling songs, with proper ordering.
Graph Implementation: Implement a graph data structure using collections (adjacency list or matrix) and basic traversal algorithms.
LRU Cache: Implement a Least Recently Used (LRU) cache using LinkedHashMap.
Set Operations: Create methods to perform set operations (union, intersection, difference) using Java collections.
Multimap: Implement a multimap (a map where each key can have multiple values) using Java collections.
Priority Task Manager: Create a task management system that processes tasks based on their priority and deadline.
Directory Tree: Build a program that represents a file system's directory structure using appropriate collections.
Concurrent Data Processing: Implement a producer-consumer pattern using BlockingQueue for safe concurrent data processing.

Internal Implementations and Interview Topics¶

Collection Internal Implementations¶

ArrayList Internal Implementation¶

Backed by a dynamic array that grows as needed
Initial capacity is 10 elements
When capacity is reached, the array resizes by creating a new array with size: newCapacity = oldCapacity + (oldCapacity >> 1) (roughly 1.5x growth)
Uses System.arraycopy() for shifting elements during add/remove operations
Random access is O(1) using index-based access
Adding to the end is amortized O(1), but can be O(n) when resizing occurs
Insertion/deletion in the middle is O(n) due to element shifting

// ArrayList internal resizing pseudocode
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // grow by 50%
    if (newCapacity < minCapacity) newCapacity = minCapacity;
    // Copy old array to new larger array
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList Internal Implementation¶

Implemented as a doubly-linked list (not a singly-linked list)
Contains a Node inner class with references to previous, next, and the element
Maintains references to the first and last nodes for fast access to ends
Adding/removing from ends is O(1)
Adding/removing from middle is O(1) after finding the position (which is O(n))
Random access is O(n) as it must traverse from either end

// LinkedList Node structure pseudocode
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

HashSet Internal Implementation¶

Uses HashMap internally where the HashSet elements are stored as keys in the map
The HashMap values are all a shared dummy object
The same hashing mechanism from HashMap applies to HashSet
Load factor and initial capacity affect performance similar to HashMap

// Simplified HashSet implementation pseudocode
public boolean add(E e) {
    return map.put(e, PRESENT) == null; // PRESENT is a dummy shared object
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

LinkedHashSet Internal Implementation¶

Extends HashSet but uses LinkedHashMap internally
Maintains a doubly-linked list of entries in insertion order
The iteration order is predictable, unlike HashSet

TreeSet Internal Implementation¶

Uses TreeMap internally, with elements as keys and a dummy value
The ordering follows the same rules as TreeMap (natural ordering or comparator)
Self-balancing red-black tree structure ensures O(log n) operations

HashMap Internal Implementation¶

Uses an array of buckets (called table), each holding a linked list or tree of entries
Calculates bucket index using hash(key) & (table.length - 1)
When a bucket exceeds a threshold (8 entries), it converts from linked list to a balanced tree structure (Java 8+)
Converts back to linked list when fewer than 6 entries
Default initial capacity is 16 buckets, default load factor is 0.75
Resizes when size > capacity * loadFactor, doubling capacity each time
Java 8+ maintains consistent iteration order within each bucket

// Simplified HashMap node structure pseudocode
static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

// After exceeding TREEIFY_THRESHOLD (8), converts to:
static class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // For doubly-linked list
    boolean red;           // For red-black tree balancing
}

LinkedHashMap Internal Implementation¶

Extends HashMap but maintains a doubly-linked list of entries
Order can be insertion order (default) or access order (for LRU caches)
Slightly higher memory overhead than HashMap due to extra pointers

TreeMap Internal Implementation¶

Implemented as a Red-Black tree (self-balancing binary search tree)
Entries are sorted according to natural ordering or a provided comparator
All basic operations are O(log n)
Tree rotation operations maintain balance during insertions and deletions

Collection Comparison and Selection Guide¶

ArrayList vs LinkedList¶

Feature	ArrayList	LinkedList
Internal structure	Dynamic array	Doubly-linked list
Memory overhead	Lower	Higher (additional node pointers)
Random access	O(1)	O(n)
Insertion/deletion at beginning/middle	O(n)	O(1) after finding position
Insertion/deletion at end	Amortized O(1)	O(1)
Iteration performance	Better (cache locality)	Worse (pointer chasing)
Use case	Frequent random access, rare modifications	Frequent modifications, rare random access

HashSet vs LinkedHashSet vs TreeSet¶

Feature	HashSet	LinkedHashSet	TreeSet
Internal structure	HashMap	LinkedHashMap	TreeMap
Add/remove/contains	O(1)	O(1)	O(log n)
Iteration order	Unpredictable	Insertion order	Sorted order
Null elements	One null allowed	One null allowed	No null allowed (Java 7+)
Memory overhead	Lowest	Medium	Highest
Use case	Fast lookup, no order needed	Fast lookup with predictable order	Sorted elements and range operations

HashMap vs LinkedHashMap vs TreeMap¶

Feature	HashMap	LinkedHashMap	TreeMap
Internal structure	Hash table with buckets	HashMap + doubly-linked list	Red-black tree
Put/get/remove	O(1)	O(1)	O(log n)
Iteration order	Unpredictable	Insertion/access order	Sorted by keys
Null keys	One null key allowed	One null key allowed	No null keys
Memory overhead	Lowest	Medium	Highest
Use case	Fast key lookup	Predictable iteration, LRU caches	Sorted keys and range operations

Common Interview Questions and Tricky Scenarios¶

1. Modifying Collections During Iteration¶

// INCORRECT: Will throw ConcurrentModificationException
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
for (String item : list) {
    if (item.equals("B")) {
        list.remove(item); // Concurrent modification!
    }
}

// CORRECT: Using Iterator's remove method
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String item = iterator.next();
    if (item.equals("B")) {
        iterator.remove(); // Safe removal
    }
}

// CORRECT: Using removeIf (Java 8+)
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
list.removeIf(item -> item.equals("B"));

2. HashMap Key Design Pitfalls¶

// INCORRECT: Mutable key with changing hashCode
Map<MutableKey, String> map = new HashMap<>();
MutableKey key = new MutableKey(1);
map.put(key, "Original");
System.out.println(map.get(key)); // Original

key.setValue(2); // Changes the hashCode
System.out.println(map.get(key)); // null (can't find it anymore)

// CORRECT: Use immutable keys or make copies
class MutableKey {
    private int value;

    public MutableKey(int value) { this.value = value; }

    public void setValue(int value) { this.value = value; }

    @Override
    public int hashCode() { return value; }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof MutableKey)) return false;
        return ((MutableKey)obj).value == this.value;
    }
}

3. The Infamous equals and hashCode Contract¶

// INCORRECT: Breaking the equals/hashCode contract
class IncorrectPerson {
    private String name;
    private int age;

    // Constructor, getters, setters...

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof IncorrectPerson)) return false;
        IncorrectPerson other = (IncorrectPerson) obj;
        return name.equals(other.name) && age == other.age;
    }

    // No hashCode override! This breaks the contract
}

// CORRECT: Maintaining the equals/hashCode contract
class Person {
    private String name;
    private int age;

    // Constructor, getters, setters...

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Person)) return false;
        Person other = (Person) obj;
        return Objects.equals(name, other.name) && age == other.age;
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

4. TreeSet/TreeMap with Custom Class¶

// INCORRECT: No natural ordering or comparator
class Product {
    private String name;
    private double price;

    // Constructor, getters, setters...
}

TreeSet<Product> products = new TreeSet<>();
products.add(new Product("Laptop", 999.99)); // ClassCastException!

// CORRECT: Implementing Comparable
class Product implements Comparable<Product> {
    private String name;
    private double price;

    // Constructor, getters, setters...

    @Override
    public int compareTo(Product other) {
        return Double.compare(this.price, other.price);
    }
}

// ALTERNATIVE: Using a custom Comparator
TreeSet<Product> productsByName = new TreeSet<>((p1, p2) -> 
    p1.getName().compareTo(p2.getName()));

5. The Significance of Load Factor in HashMap¶

The load factor determines when a HashMap will resize, balancing space and time efficiency:

// Default: capacity=16, loadFactor=0.75 (reasonable balance)
Map<String, Integer> defaultMap = new HashMap<>();

// Space-efficient but slower: smaller capacity, higher load factor
Map<String, Integer> spaceEfficient = new HashMap<>(16, 0.9f);

// Time-efficient but memory-intensive: larger capacity, lower load factor
Map<String, Integer> timeEfficient = new HashMap<>(64, 0.5f);

6. Collection Memory Consumption¶

// Use EnumSet for enum values instead of HashSet
public enum Day { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY }

// GOOD: Memory efficient
Set<Day> weekdays = EnumSet.range(Day.MONDAY, Day.FRIDAY);

// BAD: Much more memory overhead
Set<Day> weekdays = new HashSet<>(Arrays.asList(
    Day.MONDAY, Day.TUESDAY, Day.WEDNESDAY, Day.THURSDAY, Day.FRIDAY));

7. Immutable Collections¶

// Java 9+ immutable collection factories
List<String> immutableList = List.of("A", "B", "C");
Set<String> immutableSet = Set.of("A", "B", "C");
Map<String, Integer> immutableMap = Map.of("A", 1, "B", 2, "C", 3);

// Pre-Java 9 immutable collections
List<String> immutableList = Collections.unmodifiableList(new ArrayList<>(Arrays.asList("A", "B", "C")));
Set<String> immutableSet = Collections.unmodifiableSet(new HashSet<>(Arrays.asList("A", "B", "C")));
Map<String, Integer> immutableMap = Collections.unmodifiableMap(new HashMap<String, Integer>() {{
    put("A", 1); put("B", 2); put("C", 3);
}});

8. Fail-Fast vs Fail-Safe Iterators¶

// Fail-Fast Iterator (throws ConcurrentModificationException)
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
Iterator<String> iterator = list.iterator();
list.add("D"); // Modification outside iterator
while (iterator.hasNext()) {
    System.out.println(iterator.next()); // Will throw exception
}

// Fail-Safe Iterator (uses a copy, doesn't throw exception)
List<String> list = new CopyOnWriteArrayList<>(Arrays.asList("A", "B", "C"));
Iterator<String> iterator = list.iterator();
list.add("D"); // Modification doesn't affect iterator's copy
while (iterator.hasNext()) {
    System.out.println(iterator.next()); // Prints A, B, C (no D)
}

9. Avoiding Autoboxing/Unboxing Overhead¶

// BAD: Significant autoboxing/unboxing overhead
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < 1000000; i++) {
    map.put(i, i * i);
}

// GOOD: Specialized primitive collections
// Using a library like Trove or Fastutil
TIntIntMap map = new TIntIntHashMap();
for (int i = 0; i < 1000000; i++) {
    map.put(i, i * i);
}

10. Collection View Modifications¶

// Map key set modifications affect the map
Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);

Set<String> keys = map.keySet();
keys.remove("A"); // Also removes from the map!

System.out.println(map); // {B=2}

// Sublist modifications affect the original list
List<String> original = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
List<String> sub = original.subList(1, 4); // B, C, D
sub.remove("C");
System.out.println(original); // [A, B, D, E]