library
beginnerJava Collections Framework Overview
Navigate the JCF hierarchy: know which interface to use, which implementation to pick, and the time complexities.
The Java Collections Framework (JCF) is a unified architecture for representing and manipulating collections.
JCF = a well-organized kitchen. Lists = shelves (ordered). Sets = spice rack (no duplicates). Maps = labeled drawers (key → value). Queues = prep station (FIFO). Each has different containers optimized for different access patterns.
Key Concepts
1
Core interfaces:
- Collection: root interface (except Map)
- List: ordered, allows duplicates. Access by index.
- Set: unordered (usually), no duplicates.
- Queue: ordered for processing. FIFO or priority-based.
- Deque: double-ended queue. Stack + Queue.
- Map: key-value pairs. Not a Collection.
2
Key implementations and complexities:
3
List:
- ArrayList: O(1) get, O(1) amortized add, O(n) insert/remove. Default choice.
- LinkedList: O(n) get, O(1) add at ends, O(1) remove if you have iterator. Use as Queue/Deque.
4
Set:
- HashSet: O(1) add/remove/contains. Unordered. Default choice.
- LinkedHashSet: O(1) ops + insertion order.
- TreeSet: O(log n) ops. Sorted (natural or Comparator).
5
Map:
- HashMap: O(1) get/put. Unordered. Default choice.
- LinkedHashMap: O(1) ops + insertion/access order.
- TreeMap: O(log n) ops. Sorted by key.
- ConcurrentHashMap: thread-safe, lock-striped.
6
Queue:
- ArrayDeque: O(1) offer/poll. Stack + Queue. Default choice.
- PriorityQueue: O(log n) offer/poll. Min-heap.
- LinkedBlockingQueue: thread-safe, for producer-consumer.
7
Choosing:
- Need order? → List
- Need uniqueness? → Set
- Need key-value? → Map
- Need FIFO/LIFO? → Deque (ArrayDeque)