5.1 Collections Framework Hierarchy & Core Interfaces
← Back to Chapter 5: Collections Framework
The Java Collections Framework (java.util) defines unified interfaces, polymorphic implementations, and high-performance utility algorithms for grouping objects.
1. Top-Level Hierarchy Architecture
Iterable<T>
│
Collection<E>
┌─────────────────┼─────────────────┐
▼ ▼ ▼
List<E> Queue<E> Set<E>
(Ordered, dupes) (FIFO / heap) (Unique elements)
│ │
Deque<E> SortedSet<E>
(Double-ended) │
NavigableSet<E>
* Map<K, V> is a separate hierarchy (Key-Value mappings, not a Collection)
2. Core Interfaces & Characteristics
| Interface | Ordering Guarantee | Allows Duplicates? | Positional Indexing? | Primary Concrete Implementations |
|---|---|---|---|---|
List<E> | Preserves insertion order | Yes | Yes (get(int index)) | ArrayList, LinkedList, Vector |
Set<E> | Varies by implementation | No (enforces mathematical uniqueness) | No | HashSet, LinkedHashSet, TreeSet |
Queue<E> | FIFO or Priority based | Yes | No (poll(), peek()) | ArrayDeque, PriorityQueue, LinkedList |
Deque<E> | Double-ended (LIFO & FIFO) | Yes | No | ArrayDeque, LinkedList |
Map<K, V> | Varies by implementation | Unique keys, duplicate values | Key-based (get(Object key)) | HashMap, LinkedHashMap, TreeMap |
3. Algorithmic Complexity Comparison
| Data Structure | Access by Index | Search by Value | Insertion (Head/Tail) | Deletion (Head/Tail) |
|---|---|---|---|---|
ArrayList | O(1) | O(n) | O(1) amortized tail / O(n) head | O(1) tail / O(n) head |
LinkedList | O(n) | O(n) | O(1) head/tail | O(1) head/tail |
HashSet | N/A | O(1) average | O(1) average | O(1) average |
TreeSet | N/A | O(log n) | O(log n) | O(log n) |
HashMap | N/A | O(1) key lookup | O(1) average | O(1) average |
TreeMap | N/A | O(log n) key lookup | O(log n) | O(log n) |
ArrayDeque | N/A | O(n) | O(1) head & tail | O(1) head & tail |