Working with Collections Framework
1. Understanding Collection Interface Hierarchy
Collection hierarchy
Iterable
└── Collection
├── List (ordered, indexed, duplicates)
│ ├── ArrayList, LinkedList, Vector, Stack
├── Set (no duplicates)
│ ├── HashSet, LinkedHashSet, TreeSet (SortedSet/NavigableSet)
└── Queue
├── PriorityQueue, ArrayDeque
└── Deque (double-ended)
Map (not a Collection)
├── HashMap, LinkedHashMap, TreeMap, Hashtable, IdentityHashMap
| Interface | Key Operations |
|---|
| Collection | add, remove, contains, size, iterator |
| List | get(i), set(i,e), indexOf |
| Set | Uniqueness via equals/hashCode |
| Map | put, get, containsKey, keySet, values, entrySet |
2. Using ArrayList
| Method | Complexity |
|---|
get(i) / set(i,e) | O(1) |
add(e) end | O(1) amortized |
add(i,e) / remove(i) | O(n) |
contains(o) | O(n) |
| Capacity | Backing array, grows by ~50% |
3. Using LinkedList
| Method | Complexity |
|---|
get(i) | O(n) |
addFirst/addLast | O(1) |
remove(iterator) | O(1) |
| Implements | List, Deque |
Note: ArrayList outperforms LinkedList in most real workloads due to cache locality.
4. Using Vector LEGACY
| Aspect | Detail |
|---|
| Thread-safe | All methods synchronized |
| Modern alternative | Collections.synchronizedList(...) or CopyOnWriteArrayList |
5. Using Stack LEGACY
| Aspect | Detail |
|---|
| Methods | push, pop, peek, empty, search |
| Modern alternative | ArrayDeque as stack (faster, not synchronized) |
6. Choosing List Implementation
| Need | Choice |
|---|
| Random access, end-add | ArrayList |
| Frequent middle insert | LinkedList (rarely worth it) |
| Stack/Queue/Deque | ArrayDeque |
| Thread-safe iteration | CopyOnWriteArrayList |
| Immutable | List.of(...) |
7. Using HashSet
| Property | Detail |
|---|
| Order | None (hash order) |
| Null | One null allowed |
| Complexity | O(1) average for add/contains/remove |
| Backing | HashMap |
8. Using LinkedHashSet
| Property | Detail |
|---|
| Order | Insertion order |
| Performance | Slightly slower than HashSet |
| Use case | Predictable iteration + uniqueness |
9. Using TreeSet
| Property | Detail |
|---|
| Order | Natural or comparator |
| Complexity | O(log n) |
| Implements | NavigableSet |
| Methods | first, last, higher, lower, floor, ceiling, subSet |
| Backing | Red-black tree |
10. Using HashMap
Example: HashMap operations
Map<String, Integer> counts = new HashMap<>();
counts.merge("apple", 1, Integer::sum);
counts.computeIfAbsent("user", k -> loadCount(k));
counts.forEach((k, v) -> System.out.println(k + "=" + v));
| Method | Use |
|---|
put(k,v) / get(k) | O(1) avg |
putIfAbsent(k,v) | Only if missing |
computeIfAbsent(k, fn) | Lazy init |
compute(k, biFn) | Update with old value |
merge(k, v, biFn) | Combine if exists |
getOrDefault(k, def) | Default value |
| Null | One null key, multiple null values |
11. Using LinkedHashMap
| Property | Detail |
|---|
| Order | Insertion (or access if configured) |
| LRU cache | Override removeEldestEntry() |
12. Using TreeMap
| Method | Use |
|---|
firstKey/lastKey | Endpoints |
floorKey/ceilingKey | ≤ / ≥ key |
headMap/tailMap/subMap | Range views |
| Complexity | O(log n) |
13. Using Hashtable LEGACY
| Aspect | Detail |
|---|
| Thread-safe | All methods synchronized |
| Null | Forbidden |
| Modern alternative | ConcurrentHashMap |
14. Understanding IdentityHashMap
| Aspect | Detail |
|---|
| Equality | == instead of equals |
| Hash | System.identityHashCode(o) |
| Use case | Object graph traversal, cycle detection |