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:
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.
ArrayListLinkedListVector β Stack
HashSetLinkedHashSetNavigableSet β TreeSet
PriorityQueueDeque<E> β ArrayDeque
HashMapLinkedHashMapSortedMap β 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 |
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.
<>): Introduced in Java 7, allows type inference on constructor invocation: List<String> list = new ArrayList<>();Object) and inserts automated synthetic cast operations. Generic types do not exist at JVM runtime!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).List Interface: ArrayList, LinkedList, Vector & StackArrayList (Dynamic Array)
Backed by a contiguous internal Object[] array.
O(1) time complexity via array index math.10. When full, capacity expands by 50% (newCapacity = oldCapacity + (oldCapacity >> 1)). Reallocation requires copying elements via System.arraycopy().O(n) in the worst/average case due to memory block shifting. Append is amortized O(1).LinkedList (Doubly-Linked List)
Implements both List and Deque interfaces.
Node<E> instances with item, next, and prev pointers.O(n) time complexity. Must traverse sequentially from head or tail (optimizes by picking closer end).O(1) constant time once the reference node is located (pointer reconfiguration without array shift).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.
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());
}
}
Set Interface: HashSet, LinkedHashSet & TreeSetequals() 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.
HashSet (Hash Table)
Backed internally by a HashMap instance.
O(1) average-case time for add(), remove(), and contains().null element (stored in bucket 0).LinkedHashSet (Hash Table + Doubly-Linked List)Maintains insertion order while guaranteeing uniqueness.
HashSet. Iteration visits elements in the exact order they were inserted by traversing an internal doubly-linked list running through all entries.HashSet due to pointer maintenance, but faster iteration over small subsets.TreeSet (Red-Black Balanced Binary Search Tree)
Implements NavigableSet (and SortedSet), backed internally by a TreeMap:
Comparable) or according to an injected Comparator.O(log n) time cost for add(), remove(), and contains() operations.null elements (throws NullPointerException on comparison).first(), last(), ceiling(e), floor(e), higher(e), lower(e), and subSet().Queue & Deque Interfaces: PriorityQueue & ArrayDeque
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.
O(log n) for enqueue (offer) and dequeue (poll); O(1) for retrieval (peek).null values.ArrayDeque (Resizable Circular Array)
Implements Deque (Double-Ended Queue), permitting efficient insertion and deletion at both ends.
Stack (no synchronization overhead) and faster than LinkedList (continuous array cache locality, no pointer allocations).addFirst(), addLast(), pollFirst(), pollLast().Map Interface: HashMap, LinkedHashMap & TreeMap
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.
HashMap Works Internally (JDK 8+)
HashMap is implemented as an array of buckets (nodes). When you execute map.put(key, value):
hashCode() is passed through a bitwise spreading function: (h = key.hashCode()) ^ (h >>> 16) to reduce collisions.index = (n - 1) & hash (where n is array length, always a power of 2).k1.equals(k2), the old value is overwritten.TreeNode). This guarantees worst-case lookup improves from O(n) to O(log n)!capacity * loadFactor (default capacity = 16, load factor = 0.75, threshold = 12), the bucket array doubles in size (32, 64, ...) and rehashes all nodes.put("ID-402", user)
LinkedHashMap
Extends HashMap by adding a doubly-linked list through all entries.
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.
Comparator.O(log n) performance for containsKey(), get(), put(), and remove().firstKey(), lastKey(), headMap(), and subMap().ConcurrentModificationException
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) |
Comparable vs. ComparatorComparable<T> (Natural Ordering)
Located in java.lang. Implemented by the target entity class itself:
public int compareTo(T other)< 0): this precedes other.0): this equals other.> 0): this succeeds other.Comparator<T> (Custom Multiple Orderings)
Located in java.util. Implemented as independent external classes or lambdas:
public int compare(T o1, T o2)Comparator.comparing(Emp::getName).thenComparing(Emp::getSalary)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.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("==================================================");
}
}
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().
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.
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.
equals() and hashCode()? What breaks if violated?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.
ArrayDeque preferred over Stack and LinkedList for LIFO stacks?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.
ConcurrentModificationException and what causes it?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(...)).
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.
List<String>.class not exist?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.