Java Collections Framework Overview

List Interface Implementations

ArrayList

ArrayList is a dynamic array-based implementation of the List interface. It provides fast random access but slower insertions/deletions in the middle.

Characteristics:

• Resizable array implementation
• O(1) time complexity for get operations
• Amortized O(1) for append operations
• O(n) for insert/delete at arbitrary positions
• Allows null elements
• Not thread-safe

Example:

import java.util.ArrayList;
import java.util.List;

public class DynamicArrayDemo {
    public static void main(String[] args) {
        List<String> colors = new ArrayList<>();
        
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");
        
        colors.add(1, "Yellow");
        
        System.out.println("Second color: " + colors.get(1));
        
        colors.remove("Green");
        
        for (String color : colors) {
            System.out.println(color);
        }
    }
}

LinkedList

LinkedList implements both List and Deque interfaces using a doubly-linked list structure.

Characteristics:

• Doubly-linked list implementation
• O(1) for insert/delete at both ends
• O(n) for random access
• Implements Queue interface methods
• Allows null elements
• Not thread-safe

Example:

import java.util.LinkedList;
import java.util.Deque;

public class LinkedStructureDemo {
    public static void main(String[] args) {
        Deque<String> tasks = new LinkedList<>();
        
        tasks.addFirst("Task 1");
        tasks.addLast("Task 2");
        tasks.push("Task 3");
        
        while (!tasks.isEmpty()) {
            System.out.println("Processing: " + tasks.pop());
        }
    }
}

Set Interface Implementations

HashSet

HashSet uses a hash table for storage, offering constant-time performance for basic operations.

Characteristics:

• Hash table implementation
• No ordering guarantees
• O(1) average time for add/remove/contains
• Allows one null element
• Not thread-safe

Example:

import java.util.HashSet;
import java.util.Set;

public class UniqueElementsDemo {
    public static void main(String[] args) {
        Set<Integer> uniqueNumbers = new HashSet<>();
        
        uniqueNumbers.add(10);
        uniqueNumbers.add(20);
        uniqueNumbers.add(10); // Duplicate, won't be added
        
        System.out.println("Size: " + uniqueNumbers.size());
        uniqueNumbers.forEach(System.out::println);
    }
}

TreeSet

TreeSet implements SortedSet using a Red-Black tree, maintaining elements in sorted order.

Characteristics:

• Red-Black tree implementation
• Sorted order (natural or comparator)
• O(log n) for basic operations
• Doesn't allow null elements
• Not thread-safe

Example:

import java.util.TreeSet;
import java.util.Set;

public class SortedSetDemo {
    public static void main(String[] args) {
        Set<String> sortedWords = new TreeSet<>();
        
        sortedWords.add("Banana");
        sortedWords.add("Apple");
        sortedWords.add("Cherry");
        
        sortedWords.forEach(System.out::println);
    }
}

Map Interface Implementations

HashMap

HashMap is the most widely used Map implementation, based on a hash table.

Characteristics:

• Hash table implementation (array + linked list/red-black tree)
• No ordering guarantees
• O(1) average time for get/put
• Allows null key and multiple null values
• Not thread-safe

Example:

import java.util.HashMap;
import java.util.Map;

public class KeyValueStoreDemo {
    public static void main(String[] args) {
        Map<String, Integer> studentGrades = new HashMap<>();
        
        studentGrades.put("Alice", 85);
        studentGrades.put("Bob", 92);
        studentGrades.put("Charlie", 78);
        
        System.out.println("Bob's grade: " + studentGrades.get("Bob"));
        
        studentGrades.forEach((name, grade) -> 
            System.out.println(name + ": " + grade));
    }
}

TreeMap

TreeMap implements SortedMap using a Red-Black tree, maintaining keys in sorted order.

Characteristics:

• Red-Black tree implementation
• Sorted key order
• O(log n) for basic operations
• Doesn't allow null keys
• Not thread-safe

Example:

import java.util.TreeMap;
import java.util.Map;

public class OrderedMapDemo {
    public static void main(String[] args) {
        Map<String, Double> productPrices = new TreeMap<>();
        
        productPrices.put("Laptop", 999.99);
        productPrices.put("Mouse", 29.99);
        productPrices.put("Keyboard", 79.99);
        
        productPrices.forEach((product, price) -> 
            System.out.println(product + ": $" + price));
    }
}

Queue Implementations

PriorityQueue

PriorityQueue implements Queue interface based on a priority heap.

Characteristics:

• Heap implementation (min-heap by default)
• Ordered by natural order or comparator
• O(log n) for offer/poll
• Doesn't allow null elements
• Not thread-safe

Example:

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityTaskDemo {
    public static void main(String[] args) {
        Queue<Task> taskQueue = new PriorityQueue<>(Task::compareTo);
        
        taskQueue.offer(new Task("High", 3));
        taskQueue.offer(new Task("Low", 1));
        taskQueue.offer(new Task("Medium", 2));
        
        while (!taskQueue.isEmpty()) {
            System.out.println(taskQueue.poll());
        }
    }
    
    static class Task implements Comparable<Task> {
        String name;
        int priority;
        
        Task(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }
        
        @Override
        public int compareTo(Task other) {
            return Integer.compare(other.priority, this.priority);
        }
        
        @Override
        public String toString() {
            return name + " (Priority: " + priority + ")";
        }
    }
}

Concurrent Collections

ConcurrentHashMap

ConcurrentHashMap is a thread-safe HashMap replacement designed for high concurrency.

Characteristics:

• Lock striping (Java 8+ uses CAS + synchronized)
• Higher throughput than synchronized HashMap
• Weakly consistent iterators
• Doesn't allow null keys/values

Example:

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

public class ConcurrentMapDemo {
    public static void main(String[] args) {
        ConcurrentMap<String, Integer> cache = new ConcurrentHashMap<>();
        
        cache.putIfAbsent("counter", 0);
        cache.computeIfPresent("counter", (k, v) -> v + 1);
        
        System.out.println("Counter: " + cache.get("counter"));
    }
}

Collection Utilities

Collections Class

The Collections class provides utility methods for operating on collections.

Common Methods:

• sort(List<T>) - Sorts a list
• binarySearch(List<T>, T) - Binary search
• reverse(List<?>) - Reverses a list
• shuffle(List<?>) - Randomly shuffles
• synchronizedList(List<T>) - Creates synchronized view

Example:

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

public class CollectionUtilsDemo {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            numbers.add(i);
        }
        
        Collections.shuffle(numbers);
        System.out.println("Shuffled: " + numbers);
        
        Collections.sort(numbers);
        System.out.println("Sorted: " + numbers);
        
        int position = Collections.binarySearch(numbers, 7);
        System.out.println("Position of 7: " + position);
    }
}

Generics in Collections

Generics provide compile-time type safety for collections.

Benefits:

• Eliminates need for casting
• Enables type checking at compile time
• Allows creation of generic algorithms

Example:

public class GenericContainer<T> {
    private List<T> items = new ArrayList<>();
    
    public void add(T item) {
        items.add(item);
    }
    
    public T get(int index) {
        return items.get(index);
    }
    
    public static void main(String[] args) {
        GenericContainer<String> stringContainer = new GenericContainer<>();
        stringContainer.add("Hello");
        String text = stringContainer.get(0); // No casting needed
        
        GenericContainer<Integer> numberContainer = new GenericContainer<>();
        numberContainer.add(42);
        Integer number = numberContainer.get(0);
    }
}