Java Programming - Collections Framework

Java Programming Language

Chapter 12: Collections Framework

Data Structures and Algorithms

Course: 4343203 - Java Programming

What We'll Cover

Collections Framework Overview
List Interface and Implementations
Set Interface and Implementations
Map Interface and Implementations
Queue and Deque Interfaces
Iterators and Enhanced For Loop
Collections Utility Class
Generics in Collections

Collections Framework Hierarchy

Collections Framework Overview

Collections Framework provides a unified architecture for storing and manipulating groups of objects

Core Interfaces

Main Collection Interfaces:

Collection: Root interface for most collections
List: Ordered collection (allows duplicates)
Set: Collection with no duplicates
Queue: Collection for holding elements before processing
Map: Key-value pairs (not part of Collection hierarchy)

Benefits of Collections:

Reduces programming effort
Increases performance
Provides interoperability
Reduces learning effort
Promotes software reuse

Collection vs Collections:

Collection: Interface representing a group of objects
Collections: Utility class with static methods
Collection methods: add(), remove(), size(), etc.
Collections methods: sort(), reverse(), max(), etc.

Basic Collection Operations


import java.util.*;

public class CollectionBasics {
    public static void main(String[] args) {
        // Creating different types of collections
        List list = new ArrayList<>();
        Set set = new HashSet<>();
        Map map = new HashMap<>();
        
        // Basic operations on List
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");
        list.add("Apple"); // Duplicates allowed
        
        System.out.println("List: " + list);
        System.out.println("List size: " + list.size());
        System.out.println("Contains Apple: " + list.contains("Apple"));
        
        // Basic operations on Set
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple"); // Duplicate ignored
        
        System.out.println("Set: " + set);
        System.out.println("Set size: " + set.size());
        
        // Basic operations on Map
        map.put("Apple", 5);
        map.put("Banana", 3);
        map.put("Cherry", 8);
        
        System.out.println("Map: " + map);
        System.out.println("Apple count: " + map.get("Apple"));
        
        // Common operations
        System.out.println("List is empty: " + list.isEmpty());
        System.out.println("Set contains Banana: " + set.contains("Banana"));
        System.out.println("Map keys: " + map.keySet());
        System.out.println("Map values: " + map.values());
    }
}

List Interface

List is an ordered collection that allows duplicates and indexed access

List Implementations

ArrayList

Resizable array implementation
Fast random access (O(1))
Slow insertion/deletion (O(n))
Not synchronized
Good for frequent access

LinkedList

Doubly-linked list implementation
Slow random access (O(n))
Fast insertion/deletion (O(1))
Implements List and Deque
Good for frequent modifications

Vector

Synchronized version of ArrayList
Thread-safe but slower
Legacy class (avoid in new code)
Use Collections.synchronizedList()
Or use CopyOnWriteArrayList

ArrayList Examples

Basic ArrayList Operations:


import java.util.*;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList numbers = new ArrayList<>();
        
        // Adding elements
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(1, 15); // Insert at index 1
        
        System.out.println("ArrayList: " + numbers);
        
        // Accessing elements
        System.out.println("Element at index 2: " + numbers.get(2));
        System.out.println("First element: " + numbers.get(0));
        System.out.println("Last element: " + numbers.get(numbers.size() - 1));
        
        // Modifying elements
        numbers.set(0, 5); // Replace element at index 0
        System.out.println("After modification: " + numbers);
        
        // Searching
        System.out.println("Index of 20: " + numbers.indexOf(20));
        System.out.println("Contains 30: " + numbers.contains(30));
        
        // Removing elements
        numbers.remove(2); // Remove by index
        numbers.remove(Integer.valueOf(20)); // Remove by value
        System.out.println("After removal: " + numbers);
        
        // Size and capacity
        System.out.println("Size: " + numbers.size());
        numbers.trimToSize(); // Trim capacity to current size
    }
}

ArrayList vs LinkedList Performance:


public class ListPerformanceComparison {
    public static void main(String[] args) {
        final int SIZE = 100000;
        
        // ArrayList performance test
        ArrayList arrayList = new ArrayList<>();
        long startTime = System.currentTimeMillis();
        
        // Add elements to end
        for (int i = 0; i < SIZE; i++) {
            arrayList.add(i);
        }
        long arrayListAddTime = System.currentTimeMillis() - startTime;
        
        // Access elements randomly
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            int index = (int) (Math.random() * SIZE);
            arrayList.get(index);
        }
        long arrayListAccessTime = System.currentTimeMillis() - startTime;
        
        // LinkedList performance test
        LinkedList linkedList = new LinkedList<>();
        startTime = System.currentTimeMillis();
        
        // Add elements to end
        for (int i = 0; i < SIZE; i++) {
            linkedList.add(i);
        }
        long linkedListAddTime = System.currentTimeMillis() - startTime;
        
        // Access elements randomly
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            int index = (int) (Math.random() * SIZE);
            linkedList.get(index);
        }
        long linkedListAccessTime = System.currentTimeMillis() - startTime;
        
        System.out.println("ArrayList add time: " + arrayListAddTime + "ms");
        System.out.println("LinkedList add time: " + linkedListAddTime + "ms");
        System.out.println("ArrayList access time: " + arrayListAccessTime + "ms");
        System.out.println("LinkedList access time: " + linkedListAccessTime + "ms");
    }
}

Set Interface

Set is a collection that contains no duplicate elements

Set Implementations

HashSet

Hash table implementation
No ordering guarantee
O(1) add, remove, contains
Allows one null element
Not synchronized

LinkedHashSet

Hash table + linked list
Maintains insertion order
Slightly slower than HashSet
Predictable iteration order
Good for ordered unique elements

TreeSet

Red-Black tree implementation
Sorted order (natural or custom)
O(log n) add, remove, contains
No null elements allowed
Implements NavigableSet

Set Examples

HashSet Operations:


import java.util.*;

public class SetExample {
    public static void main(String[] args) {
        // HashSet - no ordering
        Set fruits = new HashSet<>();
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");
        fruits.add("Apple"); // Duplicate ignored
        
        System.out.println("HashSet: " + fruits);
        
        // LinkedHashSet - maintains insertion order
        Set orderedFruits = new LinkedHashSet<>();
        orderedFruits.add("Apple");
        orderedFruits.add("Banana");
        orderedFruits.add("Cherry");
        orderedFruits.add("Apple"); // Duplicate ignored
        
        System.out.println("LinkedHashSet: " + orderedFruits);
        
        // TreeSet - sorted order
        Set sortedFruits = new TreeSet<>();
        sortedFruits.add("Banana");
        sortedFruits.add("Apple");
        sortedFruits.add("Cherry");
        
        System.out.println("TreeSet: " + sortedFruits);
        
        // Set operations
        Set set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        Set set2 = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));
        
        // Union
        Set union = new HashSet<>(set1);
        union.addAll(set2);
        System.out.println("Union: " + union);
        
        // Intersection
        Set intersection = new HashSet<>(set1);
        intersection.retainAll(set2);
        System.out.println("Intersection: " + intersection);
        
        // Difference
        Set difference = new HashSet<>(set1);
        difference.removeAll(set2);
        System.out.println("Difference: " + difference);
    }
}

TreeSet with Custom Ordering:


public class TreeSetExample {
    static class Student implements Comparable {
        String name;
        int age;
        double grade;
        
        public Student(String name, int age, double grade) {
            this.name = name;
            this.age = age;
            this.grade = grade;
        }
        
        @Override
        public int compareTo(Student other) {
            // Sort by grade (descending), then by name
            int gradeComparison = Double.compare(other.grade, this.grade);
            if (gradeComparison != 0) {
                return gradeComparison;
            }
            return this.name.compareTo(other.name);
        }
        
        @Override
        public String toString() {
            return name + "(" + grade + ")";
        }
    }
    
    public static void main(String[] args) {
        TreeSet students = new TreeSet<>();
        students.add(new Student("Alice", 20, 85.5));
        students.add(new Student("Bob", 19, 92.0));
        students.add(new Student("Charlie", 21, 78.5));
        students.add(new Student("Diana", 20, 92.0));
        
        System.out.println("Students sorted by grade:");
        for (Student student : students) {
            System.out.println(student);
        }
        
        // TreeSet with custom comparator
        TreeSet lengthSorted = new TreeSet<>((s1, s2) -> {
            int lengthComparison = Integer.compare(s1.length(), s2.length());
            return lengthComparison != 0 ? lengthComparison : s1.compareTo(s2);
        });
        
        lengthSorted.addAll(Arrays.asList("Java", "Python", "C", "JavaScript", "Go"));
        System.out.println("Strings sorted by length: " + lengthSorted);
    }
}

Map Interface

Map stores key-value pairs with unique keys

Map Implementations

HashMap

Hash table implementation
No ordering guarantee
O(1) get, put, remove
Allows one null key
Not synchronized

LinkedHashMap

Hash table + linked list
Maintains insertion order
Can maintain access order
Useful for LRU caches
Slightly slower than HashMap

TreeMap

Red-Black tree implementation
Sorted by key (natural or custom)
O(log n) get, put, remove
No null keys allowed
Implements NavigableMap

Map Examples

HashMap Operations:


import java.util.*;

public class MapExample {
    public static void main(String[] args) {
        Map studentGrades = new HashMap<>();
        
        // Adding key-value pairs
        studentGrades.put("Alice", 85);
        studentGrades.put("Bob", 92);
        studentGrades.put("Charlie", 78);
        studentGrades.put("Diana", 96);
        
        System.out.println("Student grades: " + studentGrades);
        
        // Accessing values
        System.out.println("Alice's grade: " + studentGrades.get("Alice"));
        System.out.println("Eve's grade: " + studentGrades.get("Eve")); // null
        System.out.println("Eve's grade (default): " + 
            studentGrades.getOrDefault("Eve", 0));
        
        // Checking existence
        System.out.println("Contains Alice: " + studentGrades.containsKey("Alice"));
        System.out.println("Contains grade 92: " + studentGrades.containsValue(92));
        
        // Updating values
        studentGrades.put("Alice", 88); // Overwrites existing value
        studentGrades.putIfAbsent("Eve", 82); // Only if key doesn't exist
        
        // Advanced operations (Java 8+)
        studentGrades.merge("Alice", 5, Integer::sum); // Alice: 88 + 5 = 93
        studentGrades.compute("Bob", (key, value) -> value * 2); // Bob: 92 * 2 = 184
        studentGrades.computeIfAbsent("Frank", key -> key.length() * 10);
        
        System.out.println("After updates: " + studentGrades);
        
        // Iterating over map
        System.out.println("\nIterating over entries:");
        for (Map.Entry entry : studentGrades.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        
        System.out.println("\nUsing forEach (Java 8+):");
        studentGrades.forEach((name, grade) -> 
            System.out.println(name + " scored " + grade));
    }
}

TreeMap and Word Frequency:


public class WordFrequency {
    public static void main(String[] args) {
        String text = "the quick brown fox jumps over the lazy dog the fox is quick";
        
        // Count word frequencies using TreeMap (sorted by key)
        Map wordCount = new TreeMap<>();
        
        String[] words = text.toLowerCase().split("\\s+");
        
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        
        System.out.println("Word frequencies (alphabetically sorted):");
        wordCount.forEach((word, count) -> 
            System.out.println(word + ": " + count));
        
        // Find most frequent word
        String mostFrequentWord = wordCount.entrySet().stream()
            .max(Map.Entry.comparingByValue())
            .map(Map.Entry::getKey)
            .orElse("No words");
        
        System.out.println("\nMost frequent word: " + mostFrequentWord);
        
        // Group by frequency
        Map> frequencyGroups = new TreeMap<>();
        for (Map.Entry entry : wordCount.entrySet()) {
            frequencyGroups.computeIfAbsent(entry.getValue(), 
                k -> new ArrayList<>()).add(entry.getKey());
        }
        
        System.out.println("\nWords grouped by frequency:");
        frequencyGroups.forEach((freq, words) -> 
            System.out.println("Frequency " + freq + ": " + words));
    }
}

Queue and Deque Interfaces

Queue and Deque provide FIFO and double-ended queue operations

Queue Implementations

Common Queue Implementations:

LinkedList: Implements Queue and Deque
ArrayDeque: Resizable array deque
PriorityQueue: Heap-based priority queue
BlockingQueue: Thread-safe queues

Queue Example:


import java.util.*;

public class QueueExample {
    public static void main(String[] args) {
        Queue queue = new LinkedList<>();
        
        // Adding elements
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        
        System.out.println("Queue: " + queue);
        
        // Accessing head element
        System.out.println("Head (peek): " + queue.peek());
        System.out.println("Head (element): " + queue.element());
        
        // Removing elements
        String removed = queue.poll(); // Removes and returns head
        System.out.println("Removed: " + removed);
        System.out.println("Queue after poll: " + queue);
        
        // Queue methods comparison
        // offer() vs add() - same for most implementations
        // poll() vs remove() - poll returns null if empty, remove throws exception
        // peek() vs element() - peek returns null if empty, element throws exception
    }
}

PriorityQueue Example:


public class PriorityQueueExample {
    static class Task implements Comparable {
        String name;
        int priority;
        
        public Task(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }
        
        @Override
        public int compareTo(Task other) {
            return Integer.compare(other.priority, this.priority); // Higher priority first
        }
        
        @Override
        public String toString() {
            return name + "(priority:" + priority + ")";
        }
    }
    
    public static void main(String[] args) {
        PriorityQueue taskQueue = new PriorityQueue<>();
        
        taskQueue.offer(new Task("Low priority task", 1));
        taskQueue.offer(new Task("High priority task", 5));
        taskQueue.offer(new Task("Medium priority task", 3));
        taskQueue.offer(new Task("Critical task", 10));
        
        System.out.println("Processing tasks by priority:");
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();
            System.out.println("Processing: " + task);
        }
        
        // Using PriorityQueue with numbers
        PriorityQueue numbers = new PriorityQueue<>();
        numbers.addAll(Arrays.asList(5, 2, 8, 1, 9, 3));
        
        System.out.println("\nNumbers in priority order (min-heap):");
        while (!numbers.isEmpty()) {
            System.out.print(numbers.poll() + " ");
        }
    }
}

Iterators and Enhanced For Loop

Iterators provide a standard way to traverse collections

Iterator Types and Usage

Iterator Examples:


import java.util.*;

public class IteratorExample {
    public static void main(String[] args) {
        List fruits = Arrays.asList("Apple", "Banana", "Cherry", "Date");
        
        // Enhanced for loop (for-each)
        System.out.println("Enhanced for loop:");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
        
        // Iterator
        System.out.println("\nUsing Iterator:");
        Iterator iterator = fruits.iterator();
        while (iterator.hasNext()) {
            String fruit = iterator.next();
            System.out.println(fruit);
        }
        
        // ListIterator (bidirectional)
        List mutableFruits = new ArrayList<>(fruits);
        System.out.println("\nUsing ListIterator:");
        ListIterator listIterator = mutableFruits.listIterator();
        
        // Forward iteration
        while (listIterator.hasNext()) {
            String fruit = listIterator.next();
            if (fruit.equals("Banana")) {
                listIterator.set("Blueberry"); // Modify during iteration
            }
        }
        
        // Backward iteration
        System.out.println("Backward iteration:");
        while (listIterator.hasPrevious()) {
            System.out.println(listIterator.previous());
        }
        
        System.out.println("Modified list: " + mutableFruits);
    }
}

Safe Removal During Iteration:


public class SafeIterationExample {
    public static void main(String[] args) {
        List numbers = new ArrayList<>(
            Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
        
        // ❌ WRONG - ConcurrentModificationException
        /*
        for (Integer number : numbers) {
            if (number % 2 == 0) {
                numbers.remove(number); // Throws exception!
            }
        }
        */
        
        // ✅ CORRECT - Using Iterator
        Iterator iterator = numbers.iterator();
        while (iterator.hasNext()) {
            Integer number = iterator.next();
            if (number % 2 == 0) {
                iterator.remove(); // Safe removal
            }
        }
        System.out.println("After removing even numbers: " + numbers);
        
        // ✅ CORRECT - Using removeIf (Java 8+)
        List numbers2 = new ArrayList<>(
            Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
        numbers2.removeIf(number -> number % 2 == 0);
        System.out.println("Using removeIf: " + numbers2);
        
        // ✅ CORRECT - Using streams (Java 8+)
        List numbers3 = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
        List oddNumbers = numbers3.stream()
            .filter(number -> number % 2 != 0)
            .collect(Collectors.toList());
        System.out.println("Using streams: " + oddNumbers);
    }
}

Collections Utility Class

Collections class provides static utility methods for collections

Common Collections Methods


import java.util.*;

public class CollectionsUtilityExample {
    public static void main(String[] args) {
        List numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3));
        System.out.println("Original list: " + numbers);
        
        // Sorting
        Collections.sort(numbers);
        System.out.println("Sorted: " + numbers);
        
        Collections.sort(numbers, Collections.reverseOrder());
        System.out.println("Reverse sorted: " + numbers);
        
        // Shuffling
        Collections.shuffle(numbers);
        System.out.println("Shuffled: " + numbers);
        
        // Searching (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 words = Arrays.asList("apple", "banana", "apple", "cherry", "apple");
        System.out.println("Frequency of 'apple': " + Collections.frequency(words, "apple"));
        
        // Reversing
        Collections.reverse(numbers);
        System.out.println("Reversed: " + numbers);
        
        // Rotating
        Collections.rotate(numbers, 2);
        System.out.println("Rotated by 2: " + numbers);
        
        // Filling
        List list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
        Collections.fill(list, "x");
        System.out.println("Filled with 'x': " + list);
        
        // Creating immutable collections
        List immutableList = Collections.unmodifiableList(
            Arrays.asList("read", "only", "list"));
        System.out.println("Immutable list: " + immutableList);
        
        // Synchronized collections
        List syncList = Collections.synchronizedList(new ArrayList<>());
        Set syncSet = Collections.synchronizedSet(new HashSet<>());
        Map syncMap = Collections.synchronizedMap(new HashMap<>());
        
        // Empty collections
        List emptyList = Collections.emptyList();
        Set emptySet = Collections.emptySet();
        Map emptyMap = Collections.emptyMap();
        
        // Singleton collections
        List singletonList = Collections.singletonList("only-item");
        Set singletonSet = Collections.singleton("only-item");
    }
}

Generics in Collections

Generics provide type safety and eliminate the need for casting

Generic Collections

Without Generics (Pre-Java 5):


// ❌ Old way - no type safety
List list = new ArrayList();
list.add("String");
list.add(Integer.valueOf(42));
list.add(new Date());

// Requires casting and can fail at runtime
String str = (String) list.get(0); // OK
String str2 = (String) list.get(1); // ClassCastException!

With Generics (Java 5+):


// ✅ New way - type safety
List stringList = new ArrayList();
stringList.add("String");
// stringList.add(42); // Compile-time error!

String str = stringList.get(0); // No casting needed

// Diamond operator (Java 7+)
List strings = new ArrayList<>();
Map map = new HashMap<>();

Complex Generic Examples:


public class GenericCollectionsExample {
    public static void main(String[] args) {
        // List of Lists
        List> matrix = new ArrayList<>();
        matrix.add(Arrays.asList("A", "B", "C"));
        matrix.add(Arrays.asList("D", "E", "F"));
        
        // Map with complex values
        Map> studentGrades = new HashMap<>();
        studentGrades.put("Alice", Arrays.asList(85, 92, 78));
        studentGrades.put("Bob", Arrays.asList(90, 87, 95));
        
        // Set of Maps
        Set> records = new HashSet<>();
        Map record1 = new HashMap<>();
        record1.put("name", "John");
        record1.put("age", 25);
        records.add(record1);
        
        // Wildcards
        List numbers = new ArrayList();
        List integers = new ArrayList();
        
        // Bounded type parameters
        Map> collections = new HashMap<>();
        collections.put("list", Arrays.asList("a", "b", "c"));
        collections.put("set", new HashSet<>(Arrays.asList("x", "y", "z")));
        
        System.out.println("Matrix: " + matrix);
        System.out.println("Student grades: " + studentGrades);
        System.out.println("Collections map: " + collections);
    }
}

Chapter Summary

Collections Framework:

List: ArrayList, LinkedList, Vector
Set: HashSet, LinkedHashSet, TreeSet
Map: HashMap, LinkedHashMap, TreeMap
Queue: LinkedList, ArrayDeque, PriorityQueue
Collections utility class methods

Practical Skills:

Choosing appropriate collection types
Using iterators safely
Understanding performance characteristics
Working with generics effectively
Applying collections in real-world scenarios

Next: Programming Examples and Applications

Thank You!

Questions?

Ready to explore Programming Examples!