Unit IV: Collections Framework

Introduction to Collections Framework

Definition

The Java Collections Framework is a unified architecture for representing and manipulating collections. It provides interfaces, implementations, and algorithms to handle groups of objects.

Key Points

Provides ready-to-use data structures
Reduces programming effort
Increases performance with efficient algorithms
Provides interoperability between APIs
Located in java.util package

Core Interfaces

Interface	Description
Collection	Root interface for most collection types
List	Ordered collection, allows duplicates
Set	Unordered collection, no duplicates
Queue	Collection for holding elements prior to processing
Map	Key-value pairs, not part of Collection interface

Collection Hierarchy

Collection Framework Hierarchy

                        Iterable<E>
                            |
                      Collection<E>
                     /      |      \
                   /        |        \
               List<E>   Set<E>    Queue<E>
                 |          |          |
    ArrayList    |    HashSet    LinkedList
    LinkedList   |  LinkedHashSet  PriorityQueue
    Vector       |    TreeSet      ArrayDeque
      |          |
    Stack    SortedSet<E>
                 |
            NavigableSet<E>


                       Map<K,V>
                     /    |    \
                   /      |      \
             HashMap  Hashtable  SortedMap<K,V>
           LinkedHashMap   |           |
                           |    NavigableMap<K,V>
                      Properties        |
                                    TreeMap

Note

Map interface is NOT part of the Collection interface hierarchy. It represents a mapping between keys and values, not a group of objects.

Iterator

Definition

An Iterator is an object that enables you to traverse through a collection and remove elements if needed. It provides a uniform way to iterate over any Collection.

Iterator Methods

Method	Description
boolean hasNext()	Returns true if iteration has more elements
E next()	Returns the next element
void remove()	Removes the last element returned

IteratorDemo.java

import java.util.*;

public class IteratorDemo {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        
        // Using Iterator
        Iterator<String> it = names.iterator();
        while (it.hasNext()) {
            String name = it.next();
            System.out.println(name);
            
            // Safe removal during iteration
            if (name.equals("Bob")) {
                it.remove();  // Removes "Bob"
            }
        }
        
        System.out.println("After removal: " + names);
        
        // ListIterator - bidirectional
        List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3));
        ListIterator<Integer> listIt = numbers.listIterator();
        
        // Forward
        while (listIt.hasNext()) {
            System.out.println("Forward: " + listIt.next());
        }
        
        // Backward
        while (listIt.hasPrevious()) {
            System.out.println("Backward: " + listIt.previous());
        }
    }
}

Warning

Never modify a collection while iterating using for-each loop. Use Iterator's remove() method or use ConcurrentModificationException will be thrown.

List Interface

Definition

A List is an ordered collection (sequence) that allows duplicate elements. Elements can be accessed by their integer index (position).

List Implementations Comparison

Feature	ArrayList	LinkedList	Vector
Internal Structure	Dynamic array	Doubly linked list	Dynamic array
Thread-Safe	No	No	Yes (synchronized)
Random Access	O(1) - Fast	O(n) - Slow	O(1) - Fast
Insert/Delete	O(n) - Slow	O(1) - Fast	O(n) - Slow
Memory	Less overhead	More (node pointers)	Less overhead

ArrayList

ArrayListDemo.java

import java.util.*;

public class ArrayListDemo {
    public static void main(String[] args) {
        // Creating ArrayList
        ArrayList<String> list = new ArrayList<>();
        
        // Adding elements
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");
        list.add(1, "Avocado");  // Insert at index 1
        
        // Accessing elements
        System.out.println("Element at 0: " + list.get(0));
        System.out.println("Size: " + list.size());
        
        // Modifying elements
        list.set(0, "Apricot");  // Replace element at index 0
        
        // Searching
        System.out.println("Contains Banana: " + list.contains("Banana"));
        System.out.println("Index of Banana: " + list.indexOf("Banana"));
        
        // Removing elements
        list.remove("Banana");      // By object
        list.remove(0);             // By index
        
        // Iterating
        for (String fruit : list) {
            System.out.println(fruit);
        }
        
        // Converting to array
        String[] arr = list.toArray(new String[0]);
    }
}

LinkedList

LinkedListDemo.java

import java.util.*;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        
        // Add at beginning/end
        list.addFirst("First");
        list.addLast("Last");
        list.add("Middle");  // Same as addLast
        
        // Get first/last
        System.out.println("First: " + list.getFirst());
        System.out.println("Last: " + list.getLast());
        
        // Remove first/last
        list.removeFirst();
        list.removeLast();
        
        // As Queue (FIFO)
        LinkedList<String> queue = new LinkedList<>();
        queue.offer("A");  // Add to end
        queue.offer("B");
        System.out.println("Poll: " + queue.poll());  // Remove from front: A
        System.out.println("Peek: " + queue.peek());  // View front: B
        
        // As Stack (LIFO)
        LinkedList<String> stack = new LinkedList<>();
        stack.push("X");  // Add to front
        stack.push("Y");
        System.out.println("Pop: " + stack.pop());  // Remove from front: Y
    }
}

Vector and Stack

VectorStackDemo.java

import java.util.*;

public class VectorStackDemo {
    public static void main(String[] args) {
        // Vector - synchronized ArrayList (legacy)
        Vector<Integer> vector = new Vector<>();
        vector.add(10);
        vector.add(20);
        vector.add(30);
        
        // Enumeration (legacy iterator)
        Enumeration<Integer> e = vector.elements();
        while (e.hasMoreElements()) {
            System.out.println(e.nextElement());
        }
        
        // Stack - extends Vector (LIFO)
        Stack<String> stack = new Stack<>();
        stack.push("A");
        stack.push("B");
        stack.push("C");
        
        System.out.println("Top: " + stack.peek());      // C
        System.out.println("Pop: " + stack.pop());       // C
        System.out.println("Search B: " + stack.search("B"));  // 2 (1-based from top)
        System.out.println("Empty? " + stack.empty());
    }
}

Exam Tip

Use ArrayList for random access, LinkedList for frequent insertions/deletions. Vector and Stack are legacy classes; prefer ArrayList with Collections.synchronizedList() or ArrayDeque instead.

Set Interface

Definition

A Set is a collection that contains no duplicate elements. It models the mathematical set abstraction.

Set Implementations Comparison

Feature	HashSet	LinkedHashSet	TreeSet
Ordering	No order	Insertion order	Sorted order
Internal Structure	Hash table	Hash table + Linked list	Red-black tree
Performance	O(1)	O(1)	O(log n)
Null Elements	One null allowed	One null allowed	No null (NullPointerException)

SetDemo.java

import java.util.*;

public class SetDemo {
    public static void main(String[] args) {
        // HashSet - no order, no duplicates
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Banana");
        hashSet.add("Apple");
        hashSet.add("Cherry");
        hashSet.add("Apple");  // Duplicate - ignored
        System.out.println("HashSet: " + hashSet);  // No specific order
        
        // LinkedHashSet - maintains insertion order
        Set<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("Banana");
        linkedSet.add("Apple");
        linkedSet.add("Cherry");
        System.out.println("LinkedHashSet: " + linkedSet);  // Insertion order
        
        // TreeSet - sorted order
        Set<String> treeSet = new TreeSet<>();
        treeSet.add("Banana");
        treeSet.add("Apple");
        treeSet.add("Cherry");
        System.out.println("TreeSet: " + treeSet);  // [Apple, Banana, Cherry]
        
        // Set operations
        Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4));
        Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5, 6));
        
        // Union
        Set<Integer> union = new HashSet<>(set1);
        union.addAll(set2);
        System.out.println("Union: " + union);  // [1, 2, 3, 4, 5, 6]
        
        // Intersection
        Set<Integer> intersection = new HashSet<>(set1);
        intersection.retainAll(set2);
        System.out.println("Intersection: " + intersection);  // [3, 4]
        
        // Difference
        Set<Integer> difference = new HashSet<>(set1);
        difference.removeAll(set2);
        System.out.println("Difference: " + difference);  // [1, 2]
    }
}

TreeSet Navigation Methods

TreeSetNavigation.java

import java.util.*;

public class TreeSetNavigation {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet<>();
        set.addAll(Arrays.asList(10, 20, 30, 40, 50));
        
        System.out.println("First: " + set.first());        // 10
        System.out.println("Last: " + set.last());          // 50
        System.out.println("Lower(30): " + set.lower(30)); // 20 (strictly less)
        System.out.println("Floor(30): " + set.floor(30)); // 30 (less or equal)
        System.out.println("Higher(30): " + set.higher(30)); // 40 (strictly greater)
        System.out.println("Ceiling(30): " + set.ceiling(30)); // 30 (greater or equal)
        
        // SubSet, HeadSet, TailSet
        System.out.println("SubSet(20,40): " + set.subSet(20, 40));  // [20, 30]
        System.out.println("HeadSet(30): " + set.headSet(30));      // [10, 20]
        System.out.println("TailSet(30): " + set.tailSet(30));      // [30, 40, 50]
        
        // Descending
        System.out.println("Descending: " + set.descendingSet());
    }
}

Queue Interface

Definition

A Queue is a collection designed for holding elements prior to processing. Typically follows FIFO (First-In-First-Out) order.

Queue Methods

Operation	Throws Exception	Returns Special Value
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

QueueDemo.java

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        // LinkedList as Queue
        Queue<String> queue = new LinkedList<>();
        
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        
        System.out.println("Queue: " + queue);
        System.out.println("Peek: " + queue.peek());    // First
        System.out.println("Poll: " + queue.poll());    // First (removed)
        System.out.println("After poll: " + queue);
        
        // PriorityQueue - elements ordered by priority
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(30);
        pq.offer(10);
        pq.offer(20);
        
        System.out.println("PriorityQueue peek: " + pq.peek());  // 10 (smallest)
        
        // Poll removes in priority order
        while (!pq.isEmpty()) {
            System.out.println("Poll: " + pq.poll());  // 10, 20, 30
        }
        
        // PriorityQueue with custom comparator (max heap)
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(
            Collections.reverseOrder()
        );
        maxPQ.offer(30);
        maxPQ.offer(10);
        maxPQ.offer(20);
        System.out.println("Max heap peek: " + maxPQ.peek());  // 30
    }
}

Deque (Double-Ended Queue)

DequeDemo.java

import java.util.*;

public class DequeDemo {
    public static void main(String[] args) {
        // ArrayDeque - resizable array implementation
        Deque<String> deque = new ArrayDeque<>();
        
        // Add at both ends
        deque.addFirst("First");
        deque.addLast("Last");
        deque.offerFirst("New First");
        deque.offerLast("New Last");
        
        System.out.println("Deque: " + deque);
        
        // Remove from both ends
        System.out.println("Remove First: " + deque.removeFirst());
        System.out.println("Remove Last: " + deque.removeLast());
        
        // Use as Stack (LIFO)
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Pop: " + stack.pop());  // 3
        
        // Use as Queue (FIFO)
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println("Poll: " + queue.poll());  // 1
    }
}

Map Interface

Definition

A Map is an object that maps keys to values. It cannot contain duplicate keys; each key can map to at most one value.

Map Implementations Comparison

Feature	HashMap	LinkedHashMap	TreeMap	Hashtable
Ordering	No order	Insertion order	Sorted by keys	No order
Null Keys	One allowed	One allowed	Not allowed	Not allowed
Null Values	Allowed	Allowed	Allowed	Not allowed
Thread-Safe	No	No	No	Yes
Performance	O(1)	O(1)	O(log n)	O(1)

MapDemo.java

import java.util.*;

public class MapDemo {
    public static void main(String[] args) {
        // HashMap
        Map<String, Integer> map = new HashMap<>();
        
        // Adding entries
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);
        
        // Accessing values
        System.out.println("Alice's age: " + map.get("Alice"));
        System.out.println("Contains Bob: " + map.containsKey("Bob"));
        System.out.println("Contains 30: " + map.containsValue(30));
        
        // Default value if key not found
        System.out.println("David: " + map.getOrDefault("David", 0));
        
        // Updating values
        map.put("Alice", 26);  // Replace
        map.replace("Bob", 31);
        
        // Removing entries
        map.remove("Charlie");
        
        // Iterating - keySet
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
        
        // Iterating - entrySet (preferred)
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
        
        // Iterating - forEach
        map.forEach((key, value) -> System.out.println(key + " -> " + value));
        
        // LinkedHashMap - maintains insertion order
        Map<String, Integer> linkedMap = new LinkedHashMap<>();
        linkedMap.put("C", 3);
        linkedMap.put("A", 1);
        linkedMap.put("B", 2);
        System.out.println("LinkedHashMap: " + linkedMap);  // {C=3, A=1, B=2}
        
        // TreeMap - sorted by keys
        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("C", 3);
        treeMap.put("A", 1);
        treeMap.put("B", 2);
        System.out.println("TreeMap: " + treeMap);  // {A=1, B=2, C=3}
    }
}

TreeMap Navigation

TreeMapNavigation.java

import java.util.*;

public class TreeMapNavigation {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(10, "Ten");
        map.put(20, "Twenty");
        map.put(30, "Thirty");
        map.put(40, "Forty");
        
        System.out.println("First Key: " + map.firstKey());    // 10
        System.out.println("Last Key: " + map.lastKey());      // 40
        System.out.println("Lower Key(25): " + map.lowerKey(25));    // 20
        System.out.println("Higher Key(25): " + map.higherKey(25));  // 30
        
        // SubMap
        System.out.println("SubMap(15,35): " + map.subMap(15, 35));
        System.out.println("HeadMap(30): " + map.headMap(30));
        System.out.println("TailMap(30): " + map.tailMap(30));
    }
}

Sorting Collections

Collections.sort() Method

SortingDemo.java

import java.util.*;

public class SortingDemo {
    public static void main(String[] args) {
        // Sorting List of Strings
        List<String> names = new ArrayList<>(
            Arrays.asList("Charlie", "Alice", "Bob")
        );
        
        Collections.sort(names);  // Natural order (alphabetical)
        System.out.println("Sorted: " + names);
        
        Collections.sort(names, Collections.reverseOrder());  // Reverse
        System.out.println("Reversed: " + names);
        
        // Sorting List of Integers
        List<Integer> numbers = new ArrayList<>(
            Arrays.asList(30, 10, 50, 20, 40)
        );
        
        Collections.sort(numbers);
        System.out.println("Sorted numbers: " + numbers);
        
        // Sorting with custom Comparator
        Collections.sort(names, (s1, s2) -> s1.length() - s2.length());
        System.out.println("Sorted by length: " + names);
        
        // Using List.sort() method (Java 8+)
        names.sort(String::compareToIgnoreCase);
        System.out.println("Case-insensitive: " + names);
    }
}

Comparable vs Comparator

Comparison

Feature	Comparable	Comparator
Package	java.lang	java.util
Method	compareTo(Object o)	compare(Object o1, Object o2)
Sorting Logic	Single (natural ordering)	Multiple (custom orderings)
Modifies Class	Yes (implements interface)	No (separate class/lambda)
Usage	Collections.sort(list)	Collections.sort(list, comparator)

Comparable Example

ComparableDemo.java

import java.util.*;

class Student implements Comparable<Student> {
    private String name;
    private int age;
    
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    // Natural ordering by age
    @Override
    public int compareTo(Student other) {
        return this.age - other.age;  // Ascending by age
    }
    
    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
    
    public String getName() { return name; }
    public int getAge() { return age; }
}

public class ComparableDemo {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Alice", 22));
        students.add(new Student("Bob", 20));
        students.add(new Student("Charlie", 25));
        
        Collections.sort(students);  // Uses compareTo
        System.out.println("Sorted by age: " + students);
    }
}

Comparator Example

ComparatorDemo.java

import java.util.*;

public class ComparatorDemo {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("Alice", 22));
        students.add(new Student("Bob", 20));
        students.add(new Student("Charlie", 25));
        
        // Comparator using anonymous class
        Comparator<Student> byName = new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                return s1.getName().compareTo(s2.getName());
            }
        };
        
        // Comparator using lambda
        Comparator<Student> byNameLambda = 
            (s1, s2) -> s1.getName().compareTo(s2.getName());
        
        // Comparator using method reference
        Comparator<Student> byNameRef = 
            Comparator.comparing(Student::getName);
        
        // Sort by name
        Collections.sort(students, byNameRef);
        System.out.println("Sorted by name: " + students);
        
        // Reverse order
        students.sort(Comparator.comparing(Student::getAge).reversed());
        System.out.println("Sorted by age (desc): " + students);
        
        // Multiple criteria
        students.sort(
            Comparator.comparing(Student::getAge)
                      .thenComparing(Student::getName)
        );
        System.out.println("Sorted by age, then name: " + students);
    }
}

Exam Tip

Use Comparable when there is a single natural ordering for objects. Use Comparator when you need multiple ways to sort the same objects.

Properties Class

Definition

The Properties class represents a persistent set of properties that can be saved to a stream or loaded from a stream. It is used for configuration files.

PropertiesDemo.java

import java.util.*;
import java.io.*;

public class PropertiesDemo {
    public static void main(String[] args) {
        Properties props = new Properties();
        
        // Setting properties
        props.setProperty("database.url", "jdbc:mysql://localhost:3306/mydb");
        props.setProperty("database.user", "admin");
        props.setProperty("database.password", "secret");
        
        // Getting properties
        String url = props.getProperty("database.url");
        String timeout = props.getProperty("database.timeout", "30");  // Default
        
        System.out.println("URL: " + url);
        System.out.println("Timeout: " + timeout);
        
        // Saving to file
        try (FileOutputStream fos = new FileOutputStream("config.properties")) {
            props.store(fos, "Database Configuration");
        } catch (IOException e) {
            e.printStackTrace();
        }
        
        // Loading from file
        Properties loadedProps = new Properties();
        try (FileInputStream fis = new FileInputStream("config.properties")) {
            loadedProps.load(fis);
        } catch (IOException e) {
            e.printStackTrace();
        }
        
        // Iterating properties
        loadedProps.forEach((key, value) -> 
            System.out.println(key + " = " + value));
        
        // System properties
        System.out.println("Java version: " + System.getProperty("java.version"));
        System.out.println("OS name: " + System.getProperty("os.name"));
    }
}

Note

Properties extends Hashtable<Object, Object> but should only be used with String keys and values. For type-safe configurations, consider other approaches.