Master Java Collections Framework
Java Collections Framework
The Java Collections Framework is a unified architecture for representing and manipulating collections of objects. It provides a set of interfaces, implementations, and algorithms that enable efficient storage, retrieval, and manipulation of groups of objects.
Overview
The Collections Framework consists of:
- Interfaces: Abstract data types representing collections
- Implementations: Concrete implementations of collection interfaces
- Algorithms: Static methods for searching, sorting, and manipulating collections
import java.util.*;
public class CollectionsOverview {
public static void main(String[] args) {
// List - ordered collection, allows duplicates
List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Apple"); // Duplicates allowed
// Set - no duplicates
Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple"); // Duplicate ignored
// Map - key-value pairs
Map<String, Integer> map = new HashMap<>();
map.put("Apple", 5);
map.put("Banana", 3);
// Queue - FIFO structure
Queue<String> queue = new LinkedList<>();
queue.offer("First");
queue.offer("Second");
System.out.println("List: " + list); // [Apple, Banana, Apple]
System.out.println("Set: " + set); // [Apple, Banana]
System.out.println("Map: " + map); // {Apple=5, Banana=3}
System.out.println("Queue: " + queue); // [First, Second]
}
}
Collection Hierarchy
Collection<E>
|
+---------------+---------------+
| | |
List<E> Set<E> Queue<E>
| | |
ArrayList HashSet LinkedList
LinkedList TreeSet PriorityQueue
Vector LinkedHashSet ArrayDeque
Stack
Map<K,V> (separate hierarchy)
|
+-------+-------+
| |
HashMap TreeMap
LinkedHashMap ConcurrentHashMap
Hashtable
List Interface
Ordered collections that allow duplicates:
ArrayList
Dynamic array implementation:
import java.util.*;
public class ArrayListExample {
public static void main(String[] args) {
List<String> fruits = new ArrayList<>();
// Adding elements
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");
fruits.add(1, "Grape"); // Insert at index 1
// Accessing elements
System.out.println("First fruit: " + fruits.get(0));
System.out.println("Size: " + fruits.size());
// Updating elements
fruits.set(2, "Mango"); // Replace element at index 2
// Removing elements
fruits.remove("Banana");
fruits.remove(0); // Remove by index
// Iterating
for (String fruit : fruits) {
System.out.println(fruit);
}
// Using Iterator
Iterator<String> iterator = fruits.iterator();
while (iterator.hasNext()) {
String fruit = iterator.next();
if (fruit.equals("Mango")) {
iterator.remove(); // Safe removal during iteration
}
}
// Bulk operations
List<String> moreFruits = Arrays.asList("Pineapple", "Strawberry");
fruits.addAll(moreFruits);
// Searching
boolean hasApple = fruits.contains("Apple");
int index = fruits.indexOf("Grape");
System.out.println("Final list: " + fruits);
}
}
LinkedList
Doubly-linked list implementation:
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.addFirst(5); // Add to beginning
numbers.addLast(30); // Add to end
// LinkedList as Deque
numbers.offerFirst(1);
numbers.offerLast(40);
// Accessing head and tail
System.out.println("First: " + numbers.peekFirst());
System.out.println("Last: " + numbers.peekLast());
// Removing from ends
int first = numbers.pollFirst();
int last = numbers.pollLast();
System.out.println("Removed first: " + first + ", last: " + last);
System.out.println("Remaining: " + numbers);
// Performance consideration: ArrayList vs LinkedList
performanceComparison();
}
public static void performanceComparison() {
int size = 100000;
// ArrayList - better for random access
List<Integer> arrayList = new ArrayList<>();
long start = System.nanoTime();
for (int i = 0; i < size; i++) {
arrayList.add(i);
}
// Random access
for (int i = 0; i < 1000; i++) {
arrayList.get(i * 10);
}
long arrayTime = System.nanoTime() - start;
// LinkedList - better for frequent insertions/deletions
List<Integer> linkedList = new LinkedList<>();
start = System.nanoTime();
for (int i = 0; i < size; i++) {
linkedList.add(0, i); // Insert at beginning
}
long linkedTime = System.nanoTime() - start;
System.out.println("ArrayList time: " + arrayTime / 1_000_000 + " ms");
System.out.println("LinkedList time: " + linkedTime / 1_000_000 + " ms");
}
}
Set Interface
Collections that don't allow duplicates:
HashSet
Hash table implementation:
import java.util.*;
public class HashSetExample {
public static void main(String[] args) {
Set<String> uniqueWords = new HashSet<>();
// Adding elements
uniqueWords.add("apple");
uniqueWords.add("banana");
uniqueWords.add("apple"); // Duplicate ignored
uniqueWords.add("orange");
System.out.println("Unique words: " + uniqueWords);
// Set operations
Set<String> fruits = new HashSet<>(Arrays.asList("apple", "banana", "grape"));
Set<String> citrus = new HashSet<>(Arrays.asList("orange", "lemon", "grape"));
// Union
Set<String> union = new HashSet<>(fruits);
union.addAll(citrus);
System.out.println("Union: " + union);
// Intersection
Set<String> intersection = new HashSet<>(fruits);
intersection.retainAll(citrus);
System.out.println("Intersection: " + intersection);
// Difference
Set<String> difference = new HashSet<>(fruits);
difference.removeAll(citrus);
System.out.println("Difference: " + difference);
// Custom objects in Set
customObjectsInSet();
}
public static void customObjectsInSet() {
Set<Person> people = new HashSet<>();
people.add(new Person("John", 25));
people.add(new Person("Jane", 30));
people.add(new Person("John", 25)); // Should be considered duplicate
System.out.println("People set size: " + people.size());
}
static class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Person person = (Person) obj;
return age == person.age && Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public String toString() {
return name + "(" + age + ")";
}
}
}
TreeSet
Sorted set implementation:
import java.util.*;
public class TreeSetExample {
public static void main(String[] args) {
// Natural ordering
TreeSet<Integer> numbers = new TreeSet<>();
numbers.addAll(Arrays.asList(5, 2, 8, 1, 9, 3));
System.out.println("Sorted numbers: " + numbers); // [1, 2, 3, 5, 8, 9]
// Navigation methods
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));
System.out.println("Floor of 4: " + numbers.floor(4));
System.out.println("Ceiling of 4: " + numbers.ceiling(4));
// Range operations
System.out.println("Head set (< 5): " + numbers.headSet(5));
System.out.println("Tail set (>= 5): " + numbers.tailSet(5));
System.out.println("Sub set [3, 8): " + numbers.subSet(3, 8));
// Custom comparator
TreeSet<String> words = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
words.addAll(Arrays.asList("banana", "Apple", "cherry", "Date"));
System.out.println("Case-insensitive sorted: " + words);
// Custom objects with Comparable
customComparableObjects();
}
public static void customComparableObjects() {
TreeSet<Student> students = new TreeSet<>();
students.add(new Student("Alice", 85));
students.add(new Student("Bob", 92));
students.add(new Student("Charlie", 78));
students.add(new Student("David", 92));
System.out.println("Students sorted by grade (then name): " + students);
}
static class Student implements Comparable<Student> {
private String name;
private int grade;
public Student(String name, int grade) {
this.name = name;
this.grade = grade;
}
@Override
public int compareTo(Student other) {
int gradeComparison = Integer.compare(other.grade, this.grade); // Descending by grade
return gradeComparison != 0 ? gradeComparison : this.name.compareTo(other.name);
}
@Override
public String toString() {
return name + "(" + grade + ")";
}
}
}
Map Interface
Key-value pair collections:
HashMap
Hash table implementation:
import java.util.*;
public class HashMapExample {
public static void main(String[] args) {
Map<String, Integer> inventory = new HashMap<>();
// Adding key-value pairs
inventory.put("Apple", 50);
inventory.put("Banana", 30);
inventory.put("Orange", 25);
// Accessing values
int appleCount = inventory.get("Apple");
int pearCount = inventory.getOrDefault("Pear", 0); // Default if key not found
// Updating values
inventory.put("Apple", 45); // Replace existing value
inventory.merge("Banana", 10, Integer::sum); // Add to existing value
// Removing entries
inventory.remove("Orange");
inventory.remove("Apple", 45); // Remove only if value matches
// Checking existence
boolean hasGrapes = inventory.containsKey("Grapes");
boolean hasQuantity30 = inventory.containsValue(30);
// Iterating over map
System.out.println("=== Iterating over entries ===");
for (Map.Entry<String, Integer> entry : inventory.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
System.out.println("=== Iterating over keys ===");
for (String key : inventory.keySet()) {
System.out.println(key + ": " + inventory.get(key));
}
System.out.println("=== Iterating over values ===");
for (Integer value : inventory.values()) {
System.out.println("Quantity: " + value);
}
// Compute methods (Java 8+)
inventory.compute("Grapes", (key, value) -> (value == null) ? 15 : value + 5);
inventory.computeIfAbsent("Mango", key -> 20);
inventory.computeIfPresent("Banana", (key, value) -> value * 2);
System.out.println("Final inventory: " + inventory);
// Performance considerations
performanceDemo();
}
public static void performanceDemo() {
// Custom hash code implementation affects performance
Map<PersonKey, String> peopleMap = new HashMap<>();
PersonKey key1 = new PersonKey("John", "Doe");
PersonKey key2 = new PersonKey("Jane", "Smith");
peopleMap.put(key1, "Engineer");
peopleMap.put(key2, "Designer");
System.out.println("John's job: " + peopleMap.get(new PersonKey("John", "Doe")));
}
static class PersonKey {
private String firstName;
private String lastName;
public PersonKey(String firstName, String lastName) {
this.firstName = firstName;
this.lastName = lastName;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
PersonKey personKey = (PersonKey) obj;
return Objects.equals(firstName, personKey.firstName) &&
Objects.equals(lastName, personKey.lastName);
}
@Override
public int hashCode() {
return Objects.hash(firstName, lastName);
}
}
}
TreeMap
Sorted map implementation:
import java.util.*;
public class TreeMapExample {
public static void main(String[] args) {
// Natural ordering of keys
TreeMap<String, Integer> sortedGrades = new TreeMap<>();
sortedGrades.put("Charlie", 85);
sortedGrades.put("Alice", 92);
sortedGrades.put("Bob", 78);
sortedGrades.put("David", 88);
System.out.println("Sorted by name: " + sortedGrades);
// Navigation methods
System.out.println("First entry: " + sortedGrades.firstEntry());
System.out.println("Last entry: " + sortedGrades.lastEntry());
System.out.println("Lower key than 'Charlie': " + sortedGrades.lowerKey("Charlie"));
System.out.println("Higher key than 'Charlie': " + sortedGrades.higherKey("Charlie"));
// Range views
System.out.println("Head map (before 'Charlie'): " + sortedGrades.headMap("Charlie"));
System.out.println("Tail map (from 'Charlie'): " + sortedGrades.tailMap("Charlie"));
System.out.println("Sub map ['Bob', 'David'): " + sortedGrades.subMap("Bob", "David"));
// Custom comparator - sort by grade
TreeMap<String, Integer> gradesSorted = new TreeMap<>((name1, name2) -> {
int grade1 = sortedGrades.get(name1);
int grade2 = sortedGrades.get(name2);
int gradeComparison = Integer.compare(grade2, grade1); // Descending by grade
return gradeComparison != 0 ? gradeComparison : name1.compareTo(name2);
});
gradesSorted.putAll(sortedGrades);
System.out.println("Sorted by grade (desc): " + gradesSorted);
}
}
Queue Interface
FIFO (First-In-First-Out) collections:
LinkedList as Queue
import java.util.*;
public class QueueExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
// Adding elements (enqueue)
queue.offer("First");
queue.offer("Second");
queue.offer("Third");
System.out.println("Queue: " + queue);
// Examining head without removal
String head = queue.peek();
System.out.println("Head: " + head);
// Removing elements (dequeue)
while (!queue.isEmpty()) {
String element = queue.poll();
System.out.println("Removed: " + element);
}
// Safe operations vs throwing operations
System.out.println("Peek on empty queue: " + queue.peek()); // Returns null
System.out.println("Poll on empty queue: " + queue.poll()); // Returns null
try {
queue.element(); // Throws exception on empty queue
} catch (NoSuchElementException e) {
System.out.println("element() threw exception on empty queue");
}
}
}
PriorityQueue
Heap-based priority queue:
import java.util.*;
public class PriorityQueueExample {
public static void main(String[] args) {
// Natural ordering (min-heap for numbers)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.addAll(Arrays.asList(5, 2, 8, 1, 9, 3));
System.out.println("Min heap polling:");
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " "); // 1 2 3 5 8 9
}
System.out.println();
// Max heap using custom comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.addAll(Arrays.asList(5, 2, 8, 1, 9, 3));
System.out.println("Max heap polling:");
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " "); // 9 8 5 3 2 1
}
System.out.println();
// Custom objects with priority
taskSchedulingExample();
}
public static void taskSchedulingExample() {
PriorityQueue<Task> taskQueue = new PriorityQueue<>();
taskQueue.add(new Task("Low priority task", 3));
taskQueue.add(new Task("High priority task", 1));
taskQueue.add(new Task("Medium priority task", 2));
taskQueue.add(new Task("Critical task", 1));
System.out.println("Task execution order:");
while (!taskQueue.isEmpty()) {
Task task = taskQueue.poll();
System.out.println("Executing: " + task);
}
}
static class Task implements Comparable<Task> {
private String name;
private int priority;
public Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
@Override
public int compareTo(Task other) {
int priorityComparison = Integer.compare(this.priority, other.priority);
return priorityComparison != 0 ? priorityComparison : this.name.compareTo(other.name);
}
@Override
public String toString() {
return name + " (priority: " + priority + ")";
}
}
}
Collections Utilities
Static methods for common operations:
import java.util.*;
public class CollectionsUtilities {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3));
// Sorting
Collections.sort(numbers);
System.out.println("Sorted: " + numbers);
Collections.sort(numbers, Collections.reverseOrder());
System.out.println("Reverse sorted: " + numbers);
// Searching (binary search - requires sorted list)
Collections.sort(numbers);
int index = Collections.binarySearch(numbers, 5);
System.out.println("Index of 5: " + index);
// Shuffling
Collections.shuffle(numbers);
System.out.println("Shuffled: " + numbers);
// Min/Max
System.out.println("Min: " + Collections.min(numbers));
System.out.println("Max: " + Collections.max(numbers));
// Frequency
List<String> words = Arrays.asList("apple", "banana", "apple", "cherry", "apple");
System.out.println("Frequency of 'apple': " + Collections.frequency(words, "apple"));
// Replacing
Collections.replaceAll(words, "apple", "orange");
System.out.println("After replacement: " + words);
// Rotating
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C", "D", "E"));
Collections.rotate(list, 2);
System.out.println("Rotated by 2: " + list);
// Immutable collections
List<String> immutableList = Collections.unmodifiableList(list);
try {
immutableList.add("F"); // Throws UnsupportedOperationException
} catch (UnsupportedOperationException e) {
System.out.println("Cannot modify unmodifiable list");
}
// Synchronized collections
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
// Empty collections
List<String> emptyList = Collections.emptyList();
Set<String> emptySet = Collections.emptySet();
Map<String, String> emptyMap = Collections.emptyMap();
// Singleton collections
List<String> singletonList = Collections.singletonList("only");
Set<String> singletonSet = Collections.singleton("only");
Map<String, String> singletonMap = Collections.singletonMap("key", "value");
}
}
Performance Comparison
Understanding when to use which collection:
import java.util.*;
public class PerformanceComparison {
private static final int SIZE = 100000;
public static void main(String[] args) {
System.out.println("=== List Performance ===");
compareListPerformance();
System.out.println("\n=== Set Performance ===");
compareSetPerformance();
System.out.println("\n=== Map Performance ===");
compareMapPerformance();
}
public static void compareListPerformance() {
// ArrayList vs LinkedList for different operations
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// Add at end
long start = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
arrayList.add(i);
}
long arrayListAddTime = System.nanoTime() - start;
start = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
linkedList.add(i);
}
long linkedListAddTime = System.nanoTime() - start;
// Random access
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
arrayList.get(i * 10);
}
long arrayListAccessTime = System.nanoTime() - start;
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
linkedList.get(i * 10);
}
long linkedListAccessTime = System.nanoTime() - start;
System.out.println("ArrayList add: " + arrayListAddTime / 1_000_000 + " ms");
System.out.println("LinkedList add: " + linkedListAddTime / 1_000_000 + " ms");
System.out.println("ArrayList access: " + arrayListAccessTime / 1_000_000 + " ms");
System.out.println("LinkedList access: " + linkedListAccessTime / 1_000_000 + " ms");
}
public static void compareSetPerformance() {
Set<Integer> hashSet = new HashSet<>();
Set<Integer> treeSet = new TreeSet<>();
Set<Integer> linkedHashSet = new LinkedHashSet<>();
// Adding elements
Random random = new Random();
List<Integer> testData = new ArrayList<>();
for (int i = 0; i < SIZE; i++) {
testData.add(random.nextInt(SIZE));
}
long start = System.nanoTime();
hashSet.addAll(testData);
long hashSetTime = System.nanoTime() - start;
start = System.nanoTime();
treeSet.addAll(testData);
long treeSetTime = System.nanoTime() - start;
start = System.nanoTime();
linkedHashSet.addAll(testData);
long linkedHashSetTime = System.nanoTime() - start;
System.out.println("HashSet add: " + hashSetTime / 1_000_000 + " ms");
System.out.println("TreeSet add: " + treeSetTime / 1_000_000 + " ms");
System.out.println("LinkedHashSet add: " + linkedHashSetTime / 1_000_000 + " ms");
}
public static void compareMapPerformance() {
Map<String, Integer> hashMap = new HashMap<>();
Map<String, Integer> treeMap = new TreeMap<>();
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
List<String> keys = new ArrayList<>();
for (int i = 0; i < SIZE; i++) {
keys.add("key" + i);
}
// Put operations
long start = System.nanoTime();
for (String key : keys) {
hashMap.put(key, key.hashCode());
}
long hashMapTime = System.nanoTime() - start;
start = System.nanoTime();
for (String key : keys) {
treeMap.put(key, key.hashCode());
}
long treeMapTime = System.nanoTime() - start;
start = System.nanoTime();
for (String key : keys) {
linkedHashMap.put(key, key.hashCode());
}
long linkedHashMapTime = System.nanoTime() - start;
System.out.println("HashMap put: " + hashMapTime / 1_000_000 + " ms");
System.out.println("TreeMap put: " + treeMapTime / 1_000_000 + " ms");
System.out.println("LinkedHashMap put: " + linkedHashMapTime / 1_000_000 + " ms");
}
}
Best Practices
1. Choose the Right Collection
public class CollectionChoice {
public void demonstrateChoices() {
// Use ArrayList for:
// - Random access to elements
// - Infrequent insertions/deletions in middle
List<String> randomAccess = new ArrayList<>();
// Use LinkedList for:
// - Frequent insertions/deletions at beginning/end
// - Queue/Deque operations
LinkedList<String> frequentModifications = new LinkedList<>();
// Use HashSet for:
// - Fast lookups
// - No duplicates needed
// - Order doesn't matter
Set<String> fastLookup = new HashSet<>();
// Use TreeSet for:
// - Sorted order
// - Range operations
Set<String> sortedSet = new TreeSet<>();
// Use HashMap for:
// - Fast key-value lookups
// - Order doesn't matter
Map<String, String> fastMapping = new HashMap<>();
// Use TreeMap for:
// - Sorted key order
// - Range operations on keys
Map<String, String> sortedMapping = new TreeMap<>();
}
}
2. Implement equals() and hashCode() Properly
public class Person {
private String name;
private int age;
// Constructor, getters, setters...
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Person person = (Person) obj;
return age == person.age && Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
3. Use Appropriate Initial Capacity
public class CapacityOptimization {
public void optimizeCapacity() {
// When you know approximate size, set initial capacity
List<String> largeList = new ArrayList<>(1000);
Set<String> largeSet = new HashSet<>(1000);
Map<String, String> largeMap = new HashMap<>(1000);
// This prevents multiple resizing operations
}
}
4. Prefer Interfaces Over Implementations
public class InterfaceUsage {
// Good - programming to interface
public void processItems(List<String> items) {
// Can accept ArrayList, LinkedList, etc.
}
// Bad - tied to specific implementation
public void processItemsBad(ArrayList<String> items) {
// Only accepts ArrayList
}
}
Summary
The Java Collections Framework provides:
- Flexible Data Structures: Lists, Sets, Maps, Queues for different use cases
- Performance Options: Different implementations optimized for specific operations
- Utility Methods: Sorting, searching, and manipulation algorithms
- Type Safety: Generics ensure compile-time type checking
Choosing Collections:
- ArrayList: Random access, infrequent modifications
- LinkedList: Frequent insertions/deletions, queue operations
- HashSet: Fast lookups, no order requirements
- TreeSet: Sorted elements, range operations
- HashMap: Fast key-value access, no order requirements
- TreeMap: Sorted keys, range operations
Master the Collections Framework to write efficient, maintainable Java applications with optimal data structure choices for your specific use cases.