Gyan Code

Collections Framework

List, Set, Map and more

1. Introduction to Collections

The Java Collections Framework is a unified architecture for representing and manipulating collections of objects. It provides interfaces, implementations, and algorithms for efficient data handling.

What are Collections?

A collection is an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data.

Core Interfaces Overview

InterfaceDescriptionKey FeaturesMain Implementations
CollectionRoot interfaceBasic operations: add, remove, containsAbstract base for all collections
ListOrdered collectionAllows duplicates, indexed accessArrayList, LinkedList, Vector
SetNo duplicatesMathematical set operationsHashSet, LinkedHashSet, TreeSet
MapKey-value pairsUnique keys, value mappingHashMap, LinkedHashMap, TreeMap
QueueProcessing orderFIFO operationsLinkedList, PriorityQueue, ArrayDeque

Basic Example

Collections Overview Example

import java.util.*;

public class CollectionsIntro {
    public static void main(String[] args) {
        // List - ordered collection with duplicates
        List<String> fruits = new ArrayList<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Apple"); // Duplicate allowed

        // Set - no duplicates
        Set<Integer> numbers = new HashSet<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(1); // Duplicate ignored

        // Map - key-value pairs
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 25);
        ages.put("Bob", 30);

        // Queue - FIFO operations
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("Task 1");
        tasks.offer("Task 2");

        // Display results
        System.out.println("Fruits: " + fruits);    // [Apple, Banana, Apple]
        System.out.println("Numbers: " + numbers);  // [1, 2]
        System.out.println("Ages: " + ages);        // {Alice=25, Bob=30}
        System.out.println("Tasks: " + tasks);      // [Task 1, Task 2]
    }
}

2. Collection Hierarchy

Understanding the collection hierarchy is crucial for choosing the right collection type for your specific use case.

The Collection Hierarchy

Iterable<T>
    |
Collection<E>
    |-- List<E>
    |      |-- ArrayList
    |      |-- LinkedList
    |      |-- Vector
    |
    |-- Set<E>
    |      |-- HashSet
    |      |-- LinkedHashSet
    |      |-- TreeSet
    |
    |-- Queue<E>
           |-- PriorityQueue
           |-- ArrayDeque
           |-- LinkedList

Map<K,V> (separate hierarchy)
    |-- HashMap
    |-- LinkedHashMap
    |-- TreeMap

Collection Interface Methods

Core Collection Methods

public interface Collection<E> extends Iterable<E> {
    // Basic Operations
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    boolean add(E e);
    boolean remove(Object o);
    Iterator<E> iterator();

    // Bulk Operations
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();

    // Array Operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

Common Collection Operations

Collection Operations Example

import java.util.*;

public class CollectionOperations {
    public static void main(String[] args) {
        List<String> languages = new ArrayList<>();

        // Adding elements
        languages.add("Java");
        languages.add("Python");
        languages.add("JavaScript");

        // Size and emptiness check
        System.out.println("Size: " + languages.size());
        System.out.println("Is Empty: " + languages.isEmpty());

        // Contains check
        System.out.println("Contains Java: " + languages.contains("Java"));

        // Iteration with for-each
        System.out.println("Languages:");
        for (String lang : languages) {
            System.out.println("- " + lang);
        }

        // Safe iteration with Iterator
        Iterator<String> it = languages.iterator();
        while (it.hasNext()) {
            String lang = it.next();
            if ("Python".equals(lang)) {
                it.remove(); // Safe removal during iteration
            }
        }

        // Bulk operations
        List<String> moreLanguages = Arrays.asList("C++", "Go", "Rust");
        languages.addAll(moreLanguages);

        System.out.println("After operations: " + languages);
    }
}

3. List Interface and Implementations

The List interface extends Collection and represents an ordered collection that can contain duplicate elements with indexed access.

Key Characteristics

  • Maintains insertion order
  • Allows duplicate elements
  • Provides positional access (indexed)
  • Supports list-specific operations

ArrayList Implementation

Dynamic array implementation providing fast random access and efficient iteration.

ArrayList Examples

import java.util.*;

public class ArrayListExample {
    public static void main(String[] args) {
        // Creation with initial capacity
        List<String> fruits = new ArrayList<>(10);

        // Adding elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");
        fruits.add(1, "Mango"); // Insert at index 1

        System.out.println("Fruits: " + fruits);

        // Accessing elements
        String first = fruits.get(0);
        System.out.println("First fruit: " + first);

        // Modifying elements
        fruits.set(2, "Grapes");

        // Finding elements
        int index = fruits.indexOf("Mango");
        System.out.println("Mango index: " + index);

        // Removing elements
        fruits.remove(0); // Remove by index
        fruits.remove("Orange"); // Remove by value

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

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

LinkedList Implementation

Doubly-linked list implementation providing efficient insertion and deletion operations.

LinkedList Examples

import java.util.*;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> numbers = new LinkedList<>();

        // Adding elements
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);

        // LinkedList specific methods
        numbers.addFirst(5);  // Add to beginning
        numbers.addLast(40);   // Add to end

        System.out.println("Numbers: " + numbers);

        // Accessing first and last elements
        System.out.println("First: " + numbers.getFirst());
        System.out.println("Last: " + numbers.getLast());

        // Using as Stack (LIFO)
        LinkedList<String> stack = new LinkedList<>();
        stack.push("First");
        stack.push("Second");
        stack.push("Third");

        System.out.println("Stack: " + stack);
        System.out.println("Pop: " + stack.pop());

        // Using as Queue (FIFO)
        LinkedList<String> queue = new LinkedList<>();
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");

        System.out.println("Queue: " + queue);
        System.out.println("Poll: " + queue.poll());
    }
}

Performance Comparison

ArrayList

  • Random Access: O(1)
  • Insert at End: O(1)*
  • Insert at Beginning: O(n)
  • Memory Overhead: Low

LinkedList

  • Random Access: O(n)
  • Insert at End: O(1)
  • Insert at Beginning: O(1)
  • Memory Overhead: High

Choosing Between ArrayList and LinkedList

Use ArrayList when: You need frequent random access, have more reads than writes, or memory is a concern.

Use LinkedList when: You frequently insert/delete at the beginning/end, use it as a stack/queue, or have unpredictable insertion patterns.

4. Set Interface and Implementations

The Set interface models the mathematical set abstraction - a collection containing no duplicate elements.

Key Characteristics

  • No duplicate elements allowed
  • At most one null element
  • Mathematical set operations
  • Various ordering guarantees depending on implementation

HashSet Implementation

HashSet Examples

import java.util.*;

public class HashSetExample {
    public static void main(String[] args) {
        Set<String> colors = new HashSet<>();

        // Adding elements
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");
        colors.add("Red"); // Duplicate - ignored

        System.out.println("Colors: " + colors);
        System.out.println("Size: " + colors.size());

        // Set operations
        Set<String> moreColors = new HashSet<>(Arrays.asList("Blue", "Yellow", "Purple"));

        // Union
        Set<String> union = new HashSet<>(colors);
        union.addAll(moreColors);
        System.out.println("Union: " + union);

        // Intersection
        Set<String> intersection = new HashSet<>(colors);
        intersection.retainAll(moreColors);
        System.out.println("Intersection: " + intersection);

        // Difference
        Set<String> difference = new HashSet<>(colors);
        difference.removeAll(moreColors);
        System.out.println("Difference: " + difference);
    }
}

TreeSet Implementation

TreeSet Examples

import java.util.*;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();

        // Adding elements
        numbers.add(5);
        numbers.add(2);
        numbers.add(8);
        numbers.add(1);
        numbers.add(9);

        System.out.println("TreeSet: " + numbers); // Automatically sorted

        // NavigableSet operations
        System.out.println("First: " + numbers.first());
        System.out.println("Last: " + numbers.last());
        System.out.println("Lower than 5: " + numbers.lower(5));
        System.out.println("Higher than 5: " + numbers.higher(5));

        // Range operations
        SortedSet<Integer> subset = numbers.subSet(2, 8);
        System.out.println("Subset [2, 8): " + subset);

        // Custom comparator
        TreeSet<String> words = new TreeSet<>(Comparator.comparing(String::length));
        words.add("elephant");
        words.add("cat");
        words.add("dog");
        words.add("butterfly");

        System.out.println("Words by length: " + words);
    }
}
FeatureHashSetLinkedHashSetTreeSet
OrderingNo guaranteeInsertion orderNatural/Comparator
PerformanceO(1)O(1)O(log n)
MemoryLowestMediumHighest
Null valuesOne allowedOne allowedNot allowed
Range operationsNoNoYes

5. Map Interface and Implementations

The Map interface represents a mapping between keys and values. Each key can map to at most one value.

HashMap Implementation

HashMap Examples

import java.util.*;

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, Integer> grades = new HashMap<>();

        // Adding key-value pairs
        grades.put("Alice", 95);
        grades.put("Bob", 87);
        grades.put("Charlie", 92);

        // Accessing values
        Integer aliceGrade = grades.get("Alice");
        System.out.println("Alice's grade: " + aliceGrade);

        // Safe operations
        Integer defaultGrade = grades.getOrDefault("Eve", 0);
        grades.putIfAbsent("Diana", 88);

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

        // Using streams for advanced operations
        double average = grades.values().stream()
            .mapToInt(Integer::intValue)
            .average()
            .orElse(0.0);
        System.out.println("Average grade: " + average);

        // Find top student
        Optional<Map.Entry<String, Integer>> topStudent =
            grades.entrySet().stream()
                .max(Map.Entry.comparingByValue());

        topStudent.ifPresent(entry ->
            System.out.println("Top student: " + entry.getKey()));
    }
}

TreeMap Implementation

TreeMap Examples

import java.util.*;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Double> prices = new TreeMap<>();

        // Adding entries
        prices.put("AAPL", 150.25);
        prices.put("GOOGL", 2800.50);
        prices.put("MSFT", 300.75);
        prices.put("AMZN", 3200.00);

        System.out.println("Sorted prices: " + prices);

        // NavigableMap operations
        System.out.println("First entry: " + prices.firstEntry());
        System.out.println("Last entry: " + prices.lastEntry());

        // Range queries
        System.out.println("Stocks A-M: " + prices.subMap("A", "M"));
        System.out.println("Stocks from M: " + prices.tailMap("M"));

        // Finding highest priced stock
        Map.Entry<String, Double> highest = prices.entrySet().stream()
            .max(Map.Entry.comparingByValue())
            .orElse(null);

        System.out.println("Highest priced: " + highest);
    }
}

6. Queue and Deque Interfaces

The Queue interface represents a collection designed for holding elements prior to processing, typically in FIFO order.

Queue Operations

Operation TypeThrows ExceptionReturns Special Value
Insertadd(e)offer(e)
Removeremove()poll()
Examineelement()peek()

PriorityQueue Implementation

PriorityQueue Examples

import java.util.*;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Min-heap (natural ordering)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);

        System.out.println("Polling from min-heap:");
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // 1, 2, 5, 8
        }

        // Max-heap using reverse comparator
        PriorityQueue<Integer> maxHeap =
            new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(Arrays.asList(5, 2, 8, 1));

        System.out.println("Polling from max-heap:");
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 8, 5, 2, 1
        }

        // Custom objects with priority
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(
            Comparator.comparing(Task::getPriority).reversed()
        );

        taskQueue.offer(new Task("Low priority", 1));
        taskQueue.offer(new Task("High priority", 10));
        taskQueue.offer(new Task("Medium priority", 5));

        System.out.println("Task execution order:");
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();
            System.out.println(task.getName() + " (Priority: " + task.getPriority() + ")");
        }
    }

    static class Task {
        private String name;
        private int priority;

        public Task(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }

        public String getName() { return name; }
        public int getPriority() { return priority; }
    }
}

ArrayDeque Implementation

ArrayDeque Examples

import java.util.*;

public class ArrayDequeExample {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();

        // Adding elements to both ends
        deque.addFirst("Second");
        deque.addFirst("First");
        deque.addLast("Third");
        deque.addLast("Fourth");

        System.out.println("Deque: " + deque);

        // Using as Stack (LIFO)
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("Stack operations:");
        while (!stack.isEmpty()) {
            System.out.println("Pop: " + stack.pop());
        }

        // Using as Queue (FIFO)
        ArrayDeque<String> queue = new ArrayDeque<>();
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");

        System.out.println("Queue operations:");
        while (!queue.isEmpty()) {
            System.out.println("Poll: " + queue.poll());
        }

        // Palindrome checker
        System.out.println("Is 'racecar' palindrome? " + isPalindrome("racecar"));
        System.out.println("Is 'hello' palindrome? " + isPalindrome("hello"));
    }

    public static boolean isPalindrome(String str) {
        ArrayDeque<Character> deque = new ArrayDeque<>();

        for (char c : str.toLowerCase().toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                deque.offer(c);
            }
        }

        while (deque.size() > 1) {
            if (!deque.pollFirst().equals(deque.pollLast())) {
                return false;
            }
        }
        return true;
    }
}

7. Advanced Operations

This chapter covers advanced operations and utilities for working with Java Collections effectively.

Collections Utility Class

Collections Utilities

import java.util.*;

public class CollectionsUtilities {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));

        System.out.println("Original: " + numbers);

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

        // Reverse sorting
        Collections.sort(numbers, Collections.reverseOrder());
        System.out.println("Reverse sorted: " + numbers);

        // Shuffling
        Collections.shuffle(numbers);
        System.out.println("Shuffled: " + numbers);

        // Binary search (requires sorted list)
        Collections.sort(numbers);
        int index = Collections.binarySearch(numbers, 5);
        System.out.println("Index of 5: " + index);

        // Min and Max
        System.out.println("Min: " + Collections.min(numbers));
        System.out.println("Max: " + Collections.max(numbers));

        // Frequency
        List<String> words = Arrays.asList("hello", "world", "hello", "java");
        System.out.println("Frequency of 'hello': " + Collections.frequency(words, "hello"));

        // Rotate
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
        Collections.rotate(list, 2);
        System.out.println("Rotated by 2: " + list);

        // Unmodifiable collections
        List<String> immutable = Collections.unmodifiableList(list);
        System.out.println("Immutable list: " + immutable);
    }
}

Stream API with Collections

Stream Operations

import java.util.*;
import java.util.stream.*;

public class StreamOperations {
    public static void main(String[] args) {
        List<String> words = Arrays.asList(
            "hello", "world", "java", "stream", "api", "collection"
        );

        // Filter, map, and collect
        List<String> longWords = words.stream()
            .filter(word -> word.length() > 4)
            .map(String::toUpperCase)
            .sorted()
            .collect(Collectors.toList());

        System.out.println("Long words: " + longWords);

        // Grouping by length
        Map<Integer, List<String>> wordsByLength = words.stream()
            .collect(Collectors.groupingBy(String::length));

        System.out.println("Words by length: " + wordsByLength);

        // Partitioning
        Map<Boolean, List<String>> partitioned = words.stream()
            .collect(Collectors.partitioningBy(word -> word.length() > 4));

        System.out.println("Long words: " + partitioned.get(true));
        System.out.println("Short words: " + partitioned.get(false));

        // Joining strings
        String joined = words.stream()
            .collect(Collectors.joining(", ", "[", "]"));

        System.out.println("Joined: " + joined);

        // Statistical operations
        List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

        IntSummaryStatistics stats = numbers.stream()
            .mapToInt(Integer::intValue)
            .summaryStatistics();

        System.out.println("Statistics: " + stats);
    }
}

Custom Comparators

Advanced Comparators

import java.util.*;

public class CustomComparators {
    public static void main(String[] args) {
        List<Person> people = Arrays.asList(
            new Person("Alice", 30, 75000),
            new Person("Bob", 25, 65000),
            new Person("Charlie", 35, 80000),
            new Person("Diana", 28, 70000)
        );

        // Sort by age
        people.sort(Comparator.comparing(Person::getAge));
        System.out.println("By age: " + people);

        // Sort by salary descending, then age ascending
        people.sort(Comparator.comparing(Person::getSalary).reversed()
                   .thenComparing(Person::getAge));
        System.out.println("By salary desc, age asc: " + people);

        // Sort by name length, then alphabetically
        people.sort(Comparator.comparing((Person p) -> p.getName().length())
                   .thenComparing(Person::getName));
        System.out.println("By name length, then alphabetically: " + people);
    }

    static class Person {
        private String name;
        private int age;
        private double salary;

        public Person(String name, int age, double salary) {
            this.name = name;
            this.age = age;
            this.salary = salary;
        }

        public String getName() { return name; }
        public int getAge() { return age; }
        public double getSalary() { return salary; }

        @Override
        public String toString() {
            return String.format("Person{name='%s', age=%d, salary=%.0f}", name, age, salary);
        }
    }
}

8. Performance and Best Practices

Understanding performance characteristics and following best practices is crucial for efficient collection usage.

Performance Characteristics

CollectionGet/AccessAddRemoveContainsMemory
ArrayListO(1)O(1) amortizedO(n)O(n)Low
LinkedListO(n)O(1)O(1) if node knownO(n)High
HashSetN/AO(1)O(1)O(1)Medium
TreeSetN/AO(log n)O(log n)O(log n)High
HashMapO(1)O(1)O(1)O(1)Medium
TreeMapO(log n)O(log n)O(log n)O(log n)High

Best Practices Example

Collections Best Practices

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class BestPractices {
    public static void main(String[] args) {
        // 1. Choose the right collection type
        demonstrateCollectionChoice();

        // 2. Initialize with appropriate capacity
        demonstrateCapacity();

        // 3. Use immutable collections when possible
        demonstrateImmutableCollections();

        // 4. Thread safety considerations
        demonstrateThreadSafety();
    }

    private static void demonstrateCollectionChoice() {
        System.out.println("1. Choosing the right collection:");

        // Use ArrayList for frequent random access
        List<String> frequentAccess = new ArrayList<>();

        // Use LinkedList for frequent insertions at beginning/end
        List<String> frequentModification = new LinkedList<>();

        // Use HashSet for fast membership testing
        Set<String> fastLookup = new HashSet<>();

        // Use ArrayDeque instead of Stack
        Deque<String> stack = new ArrayDeque<>();

        System.out.println("Choose collection based on usage patterns\n");
    }

    private static void demonstrateCapacity() {
        System.out.println("2. Capacity initialization:");

        // Initialize with expected size to avoid resizing
        List<Integer> list = new ArrayList<>(1000);

        // For maps, consider load factor
        int expectedSize = 1000;
        Map<String, String> map = new HashMap<>((int) (expectedSize / 0.75f) + 1);

        System.out.println("Initialize with appropriate capacity\n");
    }

    private static void demonstrateImmutableCollections() {
        System.out.println("3. Immutable collections:");

        // Java 9+ immutable collections
        List<String> immutableList = List.of("A", "B", "C");
        Set<String> immutableSet = Set.of("X", "Y", "Z");
        Map<String, Integer> immutableMap = Map.of("one", 1, "two", 2);

        System.out.println("Immutable list: " + immutableList);
        System.out.println("Use immutable collections when data won't change\n");
    }

    private static void demonstrateThreadSafety() {
        System.out.println("4. Thread safety:");

        // Thread-safe collections
        Map<String, String> concurrentMap = new ConcurrentHashMap<>();
        List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());

        System.out.println("Choose appropriate thread-safe collections\n");
    }
}

Key Performance Tips

  • Initialize collections with expected capacity
  • Use appropriate collection for access patterns
  • Implement equals() and hashCode() properly
  • Use enhanced for-loops when possible
  • Consider thread-safety requirements

Common Pitfalls

  • ConcurrentModificationException during iteration
  • Poor hashCode() implementation
  • Using wrong collection type
  • Memory leaks with unused references
  • Not using generics (raw types)

Collection Selection Guide

  • ArrayList: Random access, few modifications
  • LinkedList: Frequent insertions/deletions
  • HashSet: Fast lookups, no duplicates
  • TreeSet: Sorted unique elements
  • HashMap: Key-value mapping
  • ArrayDeque: Stack/Queue operations

Key Takeaways

  • Choose the right collection based on your specific use case
  • Understand time complexity for different operations
  • Use generics for type safety and better performance
  • Leverage Stream API for functional programming
  • Consider thread safety requirements in concurrent applications
  • Always implement equals() and hashCode() consistently