Collections Overview

Collections Framework Hierarchy

The Java Collections Framework (JCF) is a unified architecture for representing and manipulating collections. It provides interfaces, implementations, and algorithms that make working with groups of objects efficient and consistent.

The top-level interfaces are:

• Collection — the root interface for List, Set, and Queue
• Map — separate interface for key-value pairs (not part of Collection)

The hierarchy:

Iterable
  └── Collection
        ├── List (ordered, allows duplicates)
        │     ├── ArrayList
        │     ├── LinkedList
        │     └── Vector
        ├── Set (no duplicates)
        │     ├── HashSet
        │     ├── LinkedHashSet
        │     └── TreeSet
        └── Queue (FIFO)
              ├── PriorityQueue
              └── ArrayDeque

Map (key-value pairs)
  ├── HashMap
  ├── LinkedHashMap
  ├── TreeMap
  └── Hashtable

import java.util.*;

public class CollectionsHierarchyDemo {
    public static void main(String[] args) {
        // Collection interface - can hold any number of elements
        Collection<String> collection = new ArrayList<>();
        collection.add("Hello");
        collection.add("World");
        collection.add("Hello");
        System.out.println("Collection: " + collection);
        System.out.println("Size: " + collection.size());

        // Iterable - can be used in for-each loop
        for (String s : collection) {
            System.out.println("Element: " + s);
        }

        // Map is NOT a Collection
        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);
        System.out.println("Map: " + map);

        // You cannot do: collection.add(map) - Map is not a Collection
        // But you can: map.entrySet() returns a Set<Map.Entry<K,V>>
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

Key design principles:

• Programming to interfaces: declare variables as List<String> not ArrayList<String>
• Implementations can be swapped without changing client code
• Generics provide type safety
• Common methods across all collections: size(), isEmpty(), contains(), iterator(), add(), remove()

The framework follows the principle of least surprise: all collections support iteration, have consistent equals() and hashCode() contracts, and implement Serializable where appropriate.

List Interface

The List interface represents an ordered collection (also called a sequence). Lists allow duplicate elements and provide positional access via index. Lists are zero-indexed.

Key characteristics:

• Ordered (maintains insertion order)
• Allows duplicates
• Indexed access via get(int index)
• Search via indexOf(Object o)

Common implementations:

• ArrayList — backed by a dynamic array, fast random access
• LinkedList — doubly linked list, fast insert/delete
• Vector — synchronized ArrayList (legacy, avoid)

import java.util.*;

public class ListInterfaceDemo {
    public static void main(String[] args) {
        // ArrayList - most common List implementation
        List<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");
        fruits.add("Banana"); // duplicates allowed

        System.out.println("List: " + fruits);
        System.out.println("Element at 0: " + fruits.get(0));
        System.out.println("Index of Banana: " + fruits.indexOf("Banana"));
        System.out.println("Size: " + fruits.size());

        // Modifying elements
        fruits.set(1, "Blueberry");
        fruits.add(2, "Elderberry");
        System.out.println("After modifications: " + fruits);

        // Removing elements
        fruits.remove("Cherry");
        fruits.remove(0);
        System.out.println("After removals: " + fruits);

        // Sublist
        List<String> sub = fruits.subList(0, 1);
        System.out.println("Sublist: " + sub);

        // LinkedList - implements both List and Deque
        List<String> linked = new LinkedList<>();
        linked.add("First");
        linked.add("Second");
        linked.add("Third");
        System.out.println("LinkedList: " + linked);

        // Iterating
        System.out.println("Using for-each:");
        for (String fruit : fruits) {
            System.out.println("  " + fruit);
        }

        // Using Iterator
        Iterator<String> it = fruits.iterator();
        System.out.println("Using Iterator:");
        while (it.hasNext()) {
            System.out.println("  " + it.next());
        }

        // Using ListIterator for bidirectional traversal
        ListIterator<String> lit = fruits.listIterator();
        System.out.println("Forward:");
        while (lit.hasNext()) {
            System.out.println("  " + lit.next());
        }
        System.out.println("Backward:");
        while (lit.hasPrevious()) {
            System.out.println("  " + lit.previous());
        }

        // Sorting
        Collections.sort(fruits);
        System.out.println("Sorted: " + fruits);
    }
}

When to use List:

• You need to maintain insertion order
• You need positional/index access
• You may have duplicate elements
• You frequently iterate over the collection

Set Interface

The Set interface represents a collection that contains no duplicate elements. It models the mathematical set abstraction. Sets do not guarantee any particular ordering.

Key characteristics:

• No duplicate elements
• Models mathematical set
• At most one null element (for most implementations)
• No positional access

Common implementations:

• HashSet — backed by HashMap, fastest, no ordering guarantees
• LinkedHashSet — maintains insertion order
• TreeSet — sorted (navigable) set, backed by TreeMap

import java.util.*;

public class SetInterfaceDemo {
    public static void main(String[] args) {
        // HashSet - no ordering guarantees, fastest
        Set<String> colors = new HashSet<>();
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");
        colors.add("Red"); // duplicate - ignored
        colors.add(null); // one null allowed

        System.out.println("HashSet: " + colors);
        System.out.println("Size: " + colors.size()); // 4, not 5
        System.out.println("Contains Red: " + colors.contains("Red"));

        // Set operations
        Set<Integer> setA = new HashSet<>(Arrays.asList(1, 2, 3, 4));
        Set<Integer> setB = new HashSet<>(Arrays.asList(3, 4, 5, 6));

        // Union
        Set<Integer> union = new HashSet<>(setA);
        union.addAll(setB);
        System.out.println("Union: " + union); // [1, 2, 3, 4, 5, 6]

        // Intersection
        Set<Integer> intersection = new HashSet<>(setA);
        intersection.retainAll(setB);
        System.out.println("Intersection: " + intersection); // [3, 4]

        // Difference
        Set<Integer> difference = new HashSet<>(setA);
        difference.removeAll(setB);
        System.out.println("Difference (A-B): " + difference); // [1, 2]

        // LinkedHashSet - maintains insertion order
        Set<String> ordered = new LinkedHashSet<>();
        ordered.add("Banana");
        ordered.add("Apple");
        ordered.add("Cherry");
        System.out.println("LinkedHashSet: " + ordered); // [Banana, Apple, Cherry]

        // TreeSet - sorted set
        Set<String> sorted = new TreeSet<>();
        sorted.add("Banana");
        sorted.add("Apple");
        sorted.add("Cherry");
        System.out.println("TreeSet: " + sorted); // [Apple, Banana, Cherry]

        // TreeSet navigation
        TreeSet<Integer> navSet = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));
        System.out.println("First: " + navSet.first()); // 10
        System.out.println("Last: " + navSet.last()); // 50
        System.out.println("Lower(25): " + navSet.lower(25)); // 20
        System.out.println("Higher(25): " + navSet.higher(25)); // 30
    }
}

When to use Set:

• You need to ensure uniqueness
• You don't need positional access
• You want fast membership testing
• You need mathematical set operations (union, intersection, difference)

Map Interface

The Map interface represents a key-value pair collection. Each key maps to at most one value. Maps do not extend the Collection interface — they are a separate hierarchy.

Key characteristics:

• Key-value pairs
• No duplicate keys
• Each key maps to one value
• At most one null key (for HashMap)
• Values can be duplicated

Common implementations:

• HashMap — no ordering, fastest
• LinkedHashMap — maintains insertion or access order
• TreeMap — sorted by key
• Hashtable — synchronized (legacy, avoid)

import java.util.*;

public class MapInterfaceDemo {
    public static void main(String[] args) {
        // HashMap - most common Map implementation
        Map<String, Integer> scores = new HashMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);
        scores.put("Alice", 98); // overwrite previous value

        System.out.println("Map: " + scores);
        System.out.println("Alice's score: " + scores.get("Alice"));
        System.out.println("Contains Bob: " + scores.containsKey("Bob"));
        System.out.println("Contains score 95: " + scores.containsValue(95));
        System.out.println("Size: " + scores.size());

        // Safe access with getOrDefault
        int score = scores.getOrDefault("David", 0);
        System.out.println("David's score: " + score); // 0

        // putIfAbsent - only put if key doesn't exist
        scores.putIfAbsent("David", 75);
        scores.putIfAbsent("Alice", 100); // Alice already exists, no change

        // computeIfAbsent - compute value only if key missing
        scores.computeIfAbsent("Eve", k -> k.length() * 10);
        System.out.println("Eve's score: " + scores.get("Eve")); // 30

        // Iterating
        System.out.println("\nEntry set:");
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println("  " + entry.getKey() + " = " + entry.getValue());
        }

        System.out.println("\nKey set:");
        for (String key : scores.keySet()) {
            System.out.println("  " + key);
        }

        System.out.println("\nValues:");
        for (int val : scores.values()) {
            System.out.println("  " + val);
        }

        // remove and replace
        scores.remove("Bob");
        scores.replace("Charlie", 95);

        // Merge - combine values
        Map<String, Integer> map1 = new HashMap<>(Map.of("a", 1, "b", 2));
        Map<String, Integer> map2 = new HashMap<>(Map.of("b", 3, "c", 4));
        map2.forEach((key, value) -> map1.merge(key, value, Integer::sum));
        System.out.println("Merged: " + map1); // {a=1, b=5, c=4}
    }
}

When to use Map:

• You need to associate keys with values
• You need fast lookup by key (O(1) average)
• You want to count occurrences, cache results, or build associations

Queue Interface and Decision Guide

The Queue interface represents a collection designed for holding elements prior to processing. It typically follows FIFO (First-In-First-Out) ordering, though some implementations (like PriorityQueue) use different orderings.

Key Queue operations:

• offer(e) — insert element, returns false if full
• poll() — remove and return head, returns null if empty
• peek() — return head without removing, returns null if empty

import java.util.*;

public class QueueInterfaceDemo {
    public static void main(String[] args) {
        // PriorityQueue - min-heap by default
        Queue<Integer> pq = new PriorityQueue<>();
        pq.offer(30);
        pq.offer(10);
        pq.offer(20);
        pq.offer(5);

        System.out.println("PriorityQueue (min-heap):");
        while (!pq.isEmpty()) {
            System.out.println("  " + pq.poll()); // 5, 10, 20, 30
        }

        // Max-heap with reverse comparator
        Queue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());
        maxPq.offer(30);
        maxPq.offer(10);
        maxPq.offer(20);

        System.out.println("Max-heap:");
        while (!maxPq.isEmpty()) {
            System.out.println("  " + maxPq.poll()); // 30, 20, 10
        }

        // ArrayDeque as Queue
        Queue<String> queue = new ArrayDeque<>();
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        System.out.println("Queue head: " + queue.peek()); // First
        System.out.println("Queue: " + queue);
    }
}

Decision Guide

Choosing the right collection depends on your requirements:

import java.util.*;

public class CollectionDecisionGuide {
    // Pattern: Count occurrences
    public static Map<String, Integer> countWords(String[] words) {
        Map<String, Integer> counts = new HashMap<>();
        for (String word : words) {
            counts.merge(word, 1, Integer::sum);
        }
        return counts;
    }

    // Pattern: Remove duplicates preserving order
    public static <T> List<T> removeDuplicates(List<T> list) {
        return new ArrayList<>(new LinkedHashSet<>(list));
    }

    // Pattern: Top K elements
    public static List<Integer> topK(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : arr) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        List<Integer> result = new ArrayList<>(minHeap);
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }

    // Pattern: Check if two collections have common elements
    public static boolean hasCommonElement(List<Integer> a, List<Integer> b) {
        Set<Integer> setB = new HashSet<>(b);
        for (int num : a) {
            if (setB.contains(num)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String[] words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
        System.out.println("Word counts: " + countWords(words));

        List<String> list = Arrays.asList("a", "b", "a", "c", "b");
        System.out.println("No duplicates: " + removeDuplicates(list));

        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
        System.out.println("Top 3: " + topK(arr, 3));

        List<Integer> a = Arrays.asList(1, 2, 3);
        List<Integer> b = Arrays.asList(3, 4, 5);
        System.out.println("Has common: " + hasCommonElement(a, b));
    }
}

Key takeaway: The choice of collection is one of the most impactful design decisions in Java. Matching the right collection to your access pattern can mean the difference between O(1) and O(n) performance.