β˜• Unit 10 β€’ Core Java Fundamentals

Java Collections Framework: Structures, Generics & Algorithms

A comprehensive deep dive into the java.util collection hierarchy: Array limitations and dynamic memory growth, Generics type safety, the core interfaces (List, Set, Queue, Deque, Map), concrete data structures (ArrayList, LinkedList, HashSet, TreeSet, HashMap, ArrayDeque), cursor traversal via Iterator and ListIterator, and custom element ordering with Comparable & Comparator.

Curriculum: Enterprise Java Software Engineering
Unit: 10 of 15
Prerequisite: Unit 08 (Packages & Interfaces), Unit 06 (OOP)
Target: JDK 21 LTS
01

The Need for Collections & Framework Architecture

🧩 Why Did Java Need a Unified Collections Framework?

Prior to JDK 1.2, Java programmers relied on basic arrays and disjointed ad-hoc utility classes like Vector, Hashtable, and Dictionary. Each had incompatible APIs, methods, and threading models. Furthermore, traditional Java arrays posed critical operational constraints:

  • Fixed Capacity: Arrays cannot grow or shrink dynamically once instantiated on the Heap. Resizing requires manual reallocation and copying.
  • Lack of High-Level Operations: Arrays lack built-in support for search, sorting, hashing, uniqueness enforcement, and priority queue ordering.
  • Type Homogeneity vs. Heterogeneity: Arrays store homogeneous types. To store varied data, developers used raw Object[] arrays requiring hazardous runtime downcasting.

The Java Collections Framework (JCF), designed primarily by Joshua Bloch in JDK 1.2, solved this by introducing a unified, high-performance architecture of reusable interfaces, algorithms, and data structures under java.util.

Visual Architecture: Java Collections Framework Inheritance Tree
<<interface>> java.lang.Iterable<T>
iterator(), forEach(), spliterator()
β–Ό extends
<<interface>> java.util.Collection<E>
add(), remove(), size(), contains(), toArray(), clear()
β–Ό extended by core branches
<<interface>> List<E>
Ordered, Index-based, Duplicates allowed
β–Ό implements
ArrayList
LinkedList
Vector βž” Stack
<<interface>> Set<E>
Unique elements, No duplicates
β–Ό implements / extends
HashSet
LinkedHashSet
NavigableSet βž” TreeSet
<<interface>> Queue<E>
FIFO / Priority processing
β–Ό implements / extends
PriorityQueue
Deque<E> βž” ArrayDeque
<<interface>> Map<K, V>
Key-Value Pairs (NOT a Collection!)
β–Ό implements / extends
HashMap
LinkedHashMap
SortedMap βž” TreeMap
Interface Duplicates Allowed? Ordering Guarantee Positional Index Access? Primary Implementations
List<E> Yes Insertion order maintained Yes (0-based integer index) ArrayList, LinkedList, Vector
Set<E> No (strictly unique) Implementation dependent (Hash vs Sorted) No HashSet, LinkedHashSet, TreeSet
Queue<E> Yes FIFO or Natural / Comparator priority No (head/tail access only) ArrayDeque, PriorityQueue, LinkedList
Map<K,V> Keys: No | Values: Yes Keys determine order (Hash, Insertion, Sorted) Via Key lookup (get(key)) HashMap, LinkedHashMap, TreeMap
02

Java Generics: Compile-Time Type Safety & Type Erasure

πŸ›‘οΈ Eliminating ClassCastException at Compile Time

Prior to JDK 5, collections stored raw references to Object. Programmers had to explicitly cast retrieved elements, leading to runtime failures if incompatible data was inserted:

List raw = new ArrayList(); raw.add("DevAscent"); raw.add(100); Integer n = (Integer) raw.get(0); // FAILS at RUNTIME!

Generics parameterize types using angle brackets (<T>, <E>, <K,V>). The compiler enforces that only elements of the specified type can be placed into the collection, entirely catching type mismatches at compile time without manual casts.

  • Diamond Operator (<>): Introduced in Java 7, allows type inference on constructor invocation: List<String> list = new ArrayList<>();
  • Type Erasure: To maintain backward compatibility with legacy JVMs, the Java compiler strips all generic type information during compilation. At runtime, bytecode replaces parameterized types with their bounding class (or Object) and inserts automated synthetic cast operations. Generic types do not exist at JVM runtime!
  • Wildcards:
    • List<?>: Unbounded wildcard (read-only reference to any object type).
    • List<? extends Number>: Upper-bounded wildcard (Producer Extends - safe for reading numbers).
    • List<? super Integer>: Lower-bounded wildcard (Consumer Super - safe for writing integers).
03

The List Interface: ArrayList, LinkedList, Vector & Stack

πŸ“¦ 1. ArrayList (Dynamic Array)

Backed by a contiguous internal Object[] array.

  • Random Access: O(1) time complexity via array index math.
  • Growth Factor: Default initial capacity is 10. When full, capacity expands by 50% (newCapacity = oldCapacity + (oldCapacity >> 1)). Reallocation requires copying elements via System.arraycopy().
  • Insertion/Deletion: O(n) in the worst/average case due to memory block shifting. Append is amortized O(1).
  • Thread Safety: Non-synchronized (fast, not thread-safe).
πŸ”— 2. LinkedList (Doubly-Linked List)

Implements both List and Deque interfaces.

  • Node Architecture: Consists of private Node<E> instances with item, next, and prev pointers.
  • Random Access: O(n) time complexity. Must traverse sequentially from head or tail (optimizes by picking closer end).
  • Insertion/Deletion: O(1) constant time once the reference node is located (pointer reconfiguration without array shift).
  • Memory Overhead: Higher memory footprint due to three object references per node.
πŸ“œ 3. Legacy Collections: Vector and Stack

Vector: Similar to ArrayList, but all methods are declared synchronized. This guarantees thread safety at a severe performance penalty. When full, Vector doubles its capacity (100% growth) by default.
Stack: A subclass of Vector modeling Last-In-First-Out (LIFO) with push(), pop(), and peek(). Modern alternative: Java official documentation advises using ArrayDeque for stacks instead of Stack because Stack inherits synchronization locks and index-based vulnerabilities from Vector.

ListShowcase.java β€” ArrayList vs. LinkedList in Action
import java.util.*;

public class ListShowcase {
    public static void main(String[] args) {
        // ArrayList: Ideal for read-heavy workloads
        List<String> techStack = new ArrayList<>();
        techStack.add("Java 21");
        techStack.add("Spring Boot");
        techStack.add("PostgreSQL");
        techStack.add(1, "Docker"); // Inserts at index 1, shifts elements right

        System.out.println("Random Access [index 2]: " + techStack.get(2));

        // LinkedList: Ideal for frequent front/rear insertions
        LinkedList<String> pipeline = new LinkedList<>(techStack);
        pipeline.addFirst("Git Checkout");
        pipeline.addLast("Deploy Kubernetes");

        System.out.println("First stage: " + pipeline.getFirst());
        System.out.println("Total Pipeline Size: " + pipeline.size());
    }
}
04

The Set Interface: HashSet, LinkedHashSet & TreeSet

🚫 Enforcing Uniqueness: The equals() and hashCode() Contract

A Set collection rejects duplicate elements. When an element e is added via add(e), the set verifies whether an equivalent object already exists. If set.contains(e) evaluates to true, the addition is discarded and returns false.

⚑ 1. HashSet (Hash Table)

Backed internally by a HashMap instance.

  • Performance: Provides O(1) average-case time for add(), remove(), and contains().
  • Ordering: Makes no guarantees regarding iteration order; order can change dynamically as buckets rehash.
  • Nulls: Allows at most one null element (stored in bucket 0).
πŸ”— 2. LinkedHashSet (Hash Table + Doubly-Linked List)

Maintains insertion order while guaranteeing uniqueness.

  • Internal Architecture: Extends HashSet. Iteration visits elements in the exact order they were inserted by traversing an internal doubly-linked list running through all entries.
  • Performance: Slightly slower than HashSet due to pointer maintenance, but faster iteration over small subsets.
🌲 3. TreeSet (Red-Black Balanced Binary Search Tree)

Implements NavigableSet (and SortedSet), backed internally by a TreeMap:

  • Total Sorting: Elements are sorted in ascending natural order (via Comparable) or according to an injected Comparator.
  • Performance: Guaranteed O(log n) time cost for add(), remove(), and contains() operations.
  • Null Elements: Prohibits null elements (throws NullPointerException on comparison).
  • Navigable Methods: Provides powerful range and boundary queries: first(), last(), ceiling(e), floor(e), higher(e), lower(e), and subSet().
05

The Queue & Deque Interfaces: PriorityQueue & ArrayDeque

🚦 Queue Method Dual Contract: Exception vs. Special Return Value

The Queue interface defines two sets of methods for handling operational limits (e.g., empty queues or bounded capacity limits):

Operation Throws Exception (Strict) Returns Special Value (Safe)
Insert (Enqueue) add(e) β€” throws IllegalStateException offer(e) β€” returns false
Remove (Dequeue) remove() β€” throws NoSuchElementException poll() β€” returns null
Examine (Peek) element() β€” throws NoSuchElementException peek() β€” returns null
⭐ PriorityQueue (Binary Min-Heap)

Elements are ordered based on natural priority or an explicit Comparator, rather than FIFO order.

  • Head Element: The least element with respect to the specified ordering is positioned at the head.
  • Time Complexity: O(log n) for enqueue (offer) and dequeue (poll); O(1) for retrieval (peek).
  • Unbounded: Grows dynamically. Rejects null values.
πŸ”„ ArrayDeque (Resizable Circular Array)

Implements Deque (Double-Ended Queue), permitting efficient insertion and deletion at both ends.

  • LIFO & FIFO: Functions seamlessly as both a high-performance Queue (FIFO) and Stack (LIFO).
  • Superiority: Faster than Stack (no synchronization overhead) and faster than LinkedList (continuous array cache locality, no pointer allocations).
  • Methods: addFirst(), addLast(), pollFirst(), pollLast().
06

The Map Interface: HashMap, LinkedHashMap & TreeMap

πŸ—ΊοΈ Key-Value Store Architecture

A Map<K, V> maps unique keys to values. It does not inherit from java.util.Collection because its fundamental unit of storage is a key-value entry (Map.Entry<K,V>), not a single element.

βš™οΈ Deep Dive: How HashMap Works Internally (JDK 8+)

HashMap is implemented as an array of buckets (nodes). When you execute map.put(key, value):

  1. Hash Calculation: The key's hashCode() is passed through a bitwise spreading function: (h = key.hashCode()) ^ (h >>> 16) to reduce collisions.
  2. Bucket Indexing: The array index is calculated using fast bitwise modulo: index = (n - 1) & hash (where n is array length, always a power of 2).
  3. Collision Resolution: Multiple keys landing on the same bucket form a singly-linked list. If keys match via k1.equals(k2), the old value is overwritten.
  4. Treeification Optimization (JDK 8): When the number of collisions in a single bucket reaches the TREEIFY_THRESHOLD (8) and the total table capacity is at least 64, the linked list converts into a balanced Red-Black Tree (TreeNode). This guarantees worst-case lookup improves from O(n) to O(log n)!
  5. Rehashing: When elements exceed capacity * loadFactor (default capacity = 16, load factor = 0.75, threshold = 12), the bucket array doubles in size (32, 64, ...) and rehashes all nodes.
Visual Architecture: HashMap.put(K, V) Collision Resolution & Treeification
Key & Value
put("ID-402", user)
βž” hash() & (n-1)&hash βž”
Bucket Array [index]
Locate Slot
βž” Collision? βž”
Bucket < 8 items
Singly-Linked List (O(n))
βž” >= 8 items & cap >= 64 βž”
Treeified Node
Red-Black Tree (O(log n))
πŸ•’ LinkedHashMap

Extends HashMap by adding a doubly-linked list through all entries.

  • Insertion Order: Iterates entries in the exact sequence they were added.
  • Access Order (LRU Cache): Can be configured via new LinkedHashMap<>(16, 0.75f, true) to re-order entries based on access (most recently accessed at tail). Overriding removeEldestEntry() creates a production Least-Recently-Used (LRU) Cache.
🌲 TreeMap

Implements NavigableMap, backed by a Red-Black tree.

  • Sorted Keys: Keys are kept strictly sorted according to natural ordering or an injected Comparator.
  • Search Complexity: O(log n) performance for containsKey(), get(), put(), and remove().
  • Range Queries: Supports firstKey(), lastKey(), headMap(), and subMap().
07

Iterators: Safe Traversal & ConcurrentModificationException

⚠️ The Fail-Fast Mechanism & Safe Element Removal

Standard collection iterators are fail-fast. Each collection maintains an internal state counter called modCount (number of structural modifications). If a collection is structurally modified (via list.add() or list.remove()) while a loop is traversing it, the iterator's expected count mismatches modCount, immediately throwing ConcurrentModificationException.

The Solution: Always use the iterator's own iterator.remove() method, which synchronizes expectedModCount with modCount.

Feature Iterator<E> ListIterator<E>
Applicability Any Collection (List, Set, Queue) Only List implementations
Directionality Forward only (hasNext(), next()) Bidirectional (hasPrevious(), previous())
Index Inspection No index awareness nextIndex(), previousIndex()
Modification Operations remove() only remove(), set(e) (modify), add(e) (insert)
08

Object Sorting: Comparable vs. Comparator

🏷️ Comparable<T> (Natural Ordering)

Located in java.lang. Implemented by the target entity class itself:

  • Defines single natural ordering logic via:
    public int compareTo(T other)
  • Return Values:
    • Negative int (< 0): this precedes other.
    • Zero (0): this equals other.
    • Positive int (> 0): this succeeds other.
  • Modifies source code; cannot provide multiple sorting strategies.
πŸŽ›οΈ Comparator<T> (Custom Multiple Orderings)

Located in java.util. Implemented as independent external classes or lambdas:

  • Defines custom strategy via:
    public int compare(T o1, T o2)
  • Enables multiple sorting behaviors for the same entity (e.g., Sort by Salary, Sort by Name, Sort by Hire Date).
  • Does not modify original entity class.
  • Modern Java 8+ composition:
    Comparator.comparing(Emp::getName).thenComparing(Emp::getSalary)
09

Unit 10 Practical Capstone: High-Throughput E-Commerce Dispatch Engine

πŸš€ Real-World Architecture Simulation

This comprehensive application unites the core components of the Collections Framework:

  • PriorityQueue: Dispatches orders ordered by customer VIP tier using a custom Comparator.
  • HashMap & LinkedHashMap: Stores inventory and tracks the recent audit trail.
  • TreeSet: Maintains a real-time, ascending price index of all active items using Comparable.
  • ListIterator: Performs safe, concurrent modification-free order adjustments.
OrderDispatchEngine.java β€” Complete Capstone Implementation
import java.util.*;

// 1. Entity implementing Comparable for Natural Sorting (by Price)
class Product implements Comparable<Product> {
    private final String sku;
    private final String name;
    private final double price;

    public Product(String sku, String name, double price) {
        this.sku = sku;
        this.name = name;
        this.price = price;
    }

    public String getName() { return name; }
    public double getPrice() { return price; }

    @Override
    public int compareTo(Product other) {
        return Double.compare(this.price, other.price);
    }

    @Override
    public String toString() {
        return String.format("[%s] %s ($%.2f)", sku, name, price);
    }
}

// 2. Customer Order for Priority Processing
class CustomerOrder {
    public enum Tier { STANDARD, PREMIUM, VIP }

    private final String orderId;
    private final Tier tier;
    private final double totalAmount;

    public CustomerOrder(String orderId, Tier tier, double totalAmount) {
        this.orderId = orderId;
        this.tier = tier;
        this.totalAmount = totalAmount;
    }

    public String getOrderId() { return orderId; }
    public Tier getTier() { return tier; }
    public double getTotalAmount() { return totalAmount; }

    @Override
    public String toString() {
        return String.format("Order(%s | %s | $%.2f)", orderId, tier, totalAmount);
    }
}

// 3. Execution Controller
public class OrderDispatchEngine {
    public static void main(String[] args) {
        System.out.println("==================================================");
        System.out.println("   DEVASCENT COLLECTIONS DISPATCH & ROUTING ENGINE  ");
        System.out.println("==================================================");

        // A. TreeSet: Auto-Sorted Catalog (Natural Ordering via Comparable)
        TreeSet<Product> catalog = new TreeSet<>();
        catalog.add(new Product("SKU-101", "Mechanical Keyboard", 129.99));
        catalog.add(new Product("SKU-102", "4K Ultra Monitor", 449.50));
        catalog.add(new Product("SKU-103", "Ergonomic Mouse", 59.00));

        System.out.println("--- Sorted Product Catalog (Ascending Price) ---");
        for (Product p : catalog) {
            System.out.println("  β€’ " + p);
        }

        // B. PriorityQueue with Custom Comparator (VIP Tier first, then Order Amount desc)
        Comparator<CustomerOrder> dispatchComparator = Comparator
                .comparing(CustomerOrder::getTier, Comparator.reverseOrder())
                .thenComparing(CustomerOrder::getTotalAmount, Comparator.reverseOrder());

        PriorityQueue<CustomerOrder> orderQueue = new PriorityQueue<>(dispatchComparator);
        orderQueue.offer(new CustomerOrder("ORD-101", CustomerOrder.Tier.STANDARD, 85.00));
        orderQueue.offer(new CustomerOrder("ORD-102", CustomerOrder.Tier.VIP, 120.00));
        orderQueue.offer(new CustomerOrder("ORD-103", CustomerOrder.Tier.PREMIUM, 350.00));
        orderQueue.offer(new CustomerOrder("ORD-104", CustomerOrder.Tier.VIP, 920.00));

        System.out.println("\n--- Dispatching Priority Orders ---");
        while (!orderQueue.isEmpty()) {
            System.out.println("  πŸš€ Dispatched: " + orderQueue.poll());
        }

        // C. ListIterator: Safe Traversal and Modification
        List<String> warehouseBays = new ArrayList<>(
                Arrays.asList("Bay-A1", "Bay-B2", "Bay-C3", "Bay-D4")
        );
        ListIterator<String> it = warehouseBays.listIterator();
        while (it.hasNext()) {
            String bay = it.next();
            if (bay.equals("Bay-B2")) {
                it.set("Bay-B2-MAINTENANCE"); // In-place mutation safely
            }
        }
        System.out.println("\nUpdated Warehouse Bays: " + warehouseBays);
        System.out.println("==================================================");
    }
}
Execution Result (javac & java)
$ javac OrderDispatchEngine.java $ java OrderDispatchEngine ================================================== DEVASCENT COLLECTIONS DISPATCH & ROUTING ENGINE ================================================== --- Sorted Product Catalog (Ascending Price) --- β€’ [SKU-103] Ergonomic Mouse ($59.00) β€’ [SKU-101] Mechanical Keyboard ($129.99) β€’ [SKU-102] 4K Ultra Monitor ($449.50) --- Dispatching Priority Orders --- πŸš€ Dispatched: Order(ORD-104 | VIP | $920.00) πŸš€ Dispatched: Order(ORD-102 | VIP | $120.00) πŸš€ Dispatched: Order(ORD-103 | PREMIUM | $350.00) πŸš€ Dispatched: Order(ORD-101 | STANDARD | $85.00) Updated Warehouse Bays: [Bay-A1, Bay-B2-MAINTENANCE, Bay-C3, Bay-D4] ==================================================
10

University Exam & Technical Interview Viva Preparation Guide

Q1. Why does Map NOT extend the Collection interface?
Collection represents a group of individual, autonomous elements (E). A Map operates on paired key-value associations (Map.Entry<K,V>). Key and value operations are incompatible with Collection methods (e.g., does add(e) add a key or value? What does iterator() iterate over?). Therefore, Joshua Bloch architected Map as its own parallel root hierarchy while providing view collections via keySet(), values(), and entrySet().
Q2. What is the internal difference between ArrayList and LinkedList? When should each be chosen?
ArrayList is backed by a contiguous dynamic Object[] array providing O(1) constant-time random access, but O(n) insertion/deletion in the middle due to memory shifts. LinkedList is a doubly-linked list with independent node objects, offering O(1) insertion/deletion once the pointer is reached, but O(n) positional search. Choose ArrayList for read-heavy operations (majority of enterprise apps). Choose LinkedList or ArrayDeque for queue/deque workloads with constant head/tail modifications.
Q3. How does HashMap resolve hash collisions in JDK 8 and later?
HashMap calculates the bucket index using (n - 1) & hash. If multiple keys hash to the same bucket, elements are chained as a singly-linked list. However, if the bucket reaches 8 nodes (TREEIFY_THRESHOLD) and total table capacity is at least 64, the list transforms into a balanced Red-Black Tree. This improves worst-case lookup time from O(n) to O(log n), defending against Denial-of-Service (Hash Collision DoS) attacks.
Q4. What is the contract between equals() and hashCode()? What breaks if violated?
If two objects are equal according to equals(Object), they must produce the identical integer hashCode(). If two objects have the same hashCode(), they are not required to be equal (hash collision). If this contract is violated by overriding equals() without hashCode(), hashing collections (HashSet, HashMap) will store duplicate keys or fail to find previously inserted keys with get(key) because the lookup lands on the wrong bucket.
Q5. Why is ArrayDeque preferred over Stack and LinkedList for LIFO stacks?
The legacy java.util.Stack class extends Vector, meaning every method call incurs unnecessary synchronization lock overhead. Moreover, LinkedList allocates a new node object on the heap for every single push, incurring garbage collection pressure and poor CPU cache locality. ArrayDeque is backed by a circular primitive array with zero method synchronization, no extra node wrapper allocations, and superior cache-line prefetching.
Q6. What is a ConcurrentModificationException and what causes it?
It is an unchecked exception thrown by fail-fast iterators when a collection detects structural modifications (additions or removals) made directly via the collection API (e.g., list.remove(item)) while an iterator is actively traversing it. The iterator detects that modCount != expectedModCount and aborts immediately. To avoid it, use iterator.remove(), a concurrent collection (e.g., CopyOnWriteArrayList), or remove via streams/predicates (list.removeIf(...)).
Q7. What is the difference between Comparable and Comparator?
Comparable<T> (in java.lang) defines the "natural ordering" of an entity via compareTo(T other) and requires modifying the entity class directly. Comparator<T> (in java.util) defines external, customizable sorting logic via compare(T o1, T o2), allowing multiple diverse sorting strategies (e.g., sorting users by age, name, or registration date) without modifying the entity class.
Q8. What is Generics Type Erasure, and why does List<String>.class not exist?
Type Erasure is the compile-time mechanism where the Java compiler replaces all generic type parameters with their raw bounds (usually Object) and inserts explicit casts in bytecode, completely removing generic types from the compiled .class file. This was implemented to ensure binary compatibility with legacy pre-Java 5 JVMs. Because generic types do not exist at runtime, List<String>.class is invalid syntax; only the raw List.class exists in JVM Metaspace.