Collections Framework — Implementations

A deep dive into ArrayList, LinkedList, HashMap, TreeMap, HashSet, and LinkedHashMap — when to use each, their performance characteristics, and critical trade-offs.

1. Definition

What is it?

The JCF provides concrete implementations of its interfaces. Each makes specific trade-offs between memory, access speed, ordering, and thread safety. Choosing the right implementation is one of the most impactful performance decisions in Java.

Why does it matter?

Using LinkedList where ArrayList suffices can cause 10×+ slowdowns for random access. Choosing HashMap over TreeMap saves O(log n) per operation but loses ordering. These choices compound at scale.

Where do they fit?

List → ArrayList, LinkedList
Set  → HashSet, LinkedHashSet, TreeSet
Map  → HashMap, LinkedHashMap, TreeMap

---

2. Core Concepts

2.1 `ArrayList`

Backed by a resizable array (Object[]). Default initial capacity: 10.

Operation	Complexity	Notes
get(index)	O(1)	Direct array access
add(element) at end	O(1) amortized	Resize = new array ×1.5
add(index, element)	O(n)	Shifts elements right
remove(index)	O(n)	Shifts elements left
contains(object)	O(n)	Linear scan

2.2 `LinkedList`

Doubly linked list — each node holds prev/next references. Implements both List and Deque.

Operation	Complexity	Notes
get(index)	O(n)	Traversal from head/tail
addFirst() / addLast()	O(1)	Pointer update
removeFirst() / removeLast()	O(1)	Pointer update
Memory per element	~48 bytes	Node header + data + 2 refs

2.3 `HashMap`

Hash table with array of buckets. Default capacity: 16, load factor: 0.75.

Operation	Complexity	Notes
get(key)	O(1) avg	O(log n) worst (Java 8+ treeified bucket)
put(key, value)	O(1) avg	May trigger resize
containsKey(key)	O(1) avg

Java 8+: Buckets with ≥8 entries convert from linked list → Red-Black Tree (O(log n) worst case).

2.4 `LinkedHashMap`

Extends HashMap with a doubly-linked list through all entries:

• Insertion order (default)
• Access order (new LinkedHashMap<>(cap, 0.75f, true)) → LRU cache

Same O(1) as HashMap with small constant overhead.

2.5 `TreeMap`

Red-Black Tree — self-balancing BST. O(log n) for all operations. Keys sorted by natural order or provided Comparator. null keys not allowed.

Operation	Complexity
get / put / remove	O(log n)
firstKey() / lastKey()	O(log n)
headMap() / subMap()	O(log n)

2.6 `HashSet`

Backed by HashMap<E, PRESENT> (PRESENT = static dummy Object). All operations delegate to the backing map — identical performance.

---

3. Practical Usage

ArrayList vs LinkedList

Scenario	Choice	Why
Read-heavy, random access	ArrayList	O(1) get
Add/remove middle frequently	ArrayList	Cache-friendly despite O(n) shift
Queue/stack use case	ArrayDeque	Better than LinkedList for both ends
Need both List + Deque	LinkedList	Rare; usually ArrayDeque is better

Counterintuitive: ArrayList beats LinkedList even for middle insertions at typical sizes due to CPU cache locality.

HashMap vs LinkedHashMap vs TreeMap

Need	Choice
Fastest get/put, no order	HashMap
Preserve insertion order	LinkedHashMap
LRU cache	LinkedHashMap(cap, 0.75f, true) + removeEldestEntry
Sorted keys, range queries	TreeMap

---

4. Code Examples

Basic Example — ArrayList vs LinkedList

List<Integer> arrayList = new ArrayList<>(100_000);
List<Integer> linkedList = new LinkedList<>();

for (int i = 0; i < 100_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// O(1)
String a = "ArrayList get: " + arrayList.get(50_000);

// O(n) — traverses ~50k nodes
String b = "LinkedList get: " + linkedList.get(50_000);

// LinkedList shines at ends only
Deque<Integer> deque = (Deque<Integer>) linkedList;
deque.addFirst(999); // O(1)

Advanced Example — LRU Cache with LinkedHashMap

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LruCache(int maxSize) {
        super(maxSize, 0.75f, true); // accessOrder = true
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// Usage
LruCache<Integer, String> cache = new LruCache<>(3);
cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three");
cache.get(1);        // access key 1 → moved to "recent" end
cache.put(4, "four"); // evicts key 2 (least recently used)
System.out.println(cache.keySet()); // [3, 1, 4]

Advanced Example — TreeMap range queries

TreeMap<String, Integer> freq = new TreeMap<>();
List.of("banana", "apple", "cherry", "avocado", "blueberry")
    .forEach(w -> freq.merge(w, 1, Integer::sum));

System.out.println(freq.firstKey());              // apple
System.out.println(freq.subMap("b", "c").keySet()); // [banana, blueberry]
System.out.println(freq.floorKey("apricot"));     // apple

Common Pitfall — Mutable HashMap key

// ❌ Mutable key breaks HashMap
class MutableKey {
    int value;
    public int hashCode() { return value; }
    public boolean equals(Object o) { return o instanceof MutableKey m && m.value == value; }
}

Map<MutableKey, String> map = new HashMap<>();
MutableKey key = new MutableKey(42);
map.put(key, "hello");
key.value = 99;                   // hashCode changed!
System.out.println(map.get(key)); // null — entry lost in wrong bucket

// ✅ Always use immutable keys: String, Integer, record, UUID

Common Pitfall — Not pre-sizing HashMap

// ❌ Starts at 16, multiple rehashes for 10k entries
Map<String, Integer> map = new HashMap<>();

// ✅ Pre-size: capacity = expectedEntries / 0.75 + 1
Map<String, Integer> map = new HashMap<>(13_334); // ~10k / 0.75
// Java 19+:
Map<String, Integer> map = HashMap.newHashMap(10_000);

---

5. Trade-offs

ArrayList vs LinkedList

Aspect	ArrayList	LinkedList
⚡ Random get(i)	O(1)	O(n)
⚡ Append at end	O(1) amortized	O(1)
⚡ Insert at middle	O(n) shift	O(n) traverse
⚡ Remove from front	O(n) shift	O(1)
💾 Memory/element	~4 bytes (ref)	~48 bytes (node)
🔧 Cache locality	Excellent	Poor
🔄 Also implements	RandomAccess	Deque

HashMap vs LinkedHashMap vs TreeMap

Aspect	HashMap	LinkedHashMap	TreeMap
⚡ get/put	O(1) avg	O(1) avg	O(log n)
💾 Memory	Base	+2 refs/entry	+2 refs + color bit
🔧 Order	❌ None	✅ Insertion/access	✅ Sorted
🔧 Range queries	❌	❌	✅
🔧 null keys	✅ 1 allowed	✅ 1 allowed	❌ NPE

---

6. Common Mistakes

1. Iterating Map with keySet + get

// ❌ Two lookups per entry
for (String key : map.keySet()) {
    Integer value = map.get(key); // redundant lookup
}

// ✅ Use entrySet or forEach
for (Map.Entry<String, Integer> e : map.entrySet()) {
    process(e.getKey(), e.getValue());
}
map.forEach((k, v) -> process(k, v)); // Java 8+

2. Using TreeMap when HashMap suffices

// ❌ O(log n) for simple lookup
Map<String, User> users = new TreeMap<>();

// ✅ O(1) avg — use TreeMap only when sorting is needed
Map<String, User> users = new HashMap<>();

3. Forgetting HashSet depends on equals + hashCode

// ❌ Missing equals/hashCode — duplicates allowed in HashSet
class Point { int x, y; }
Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
set.add(new Point(1, 2)); // not a duplicate! Different objects
System.out.println(set.size()); // 2 — bug!

// ✅ Add @Override equals() and hashCode()
record Point(int x, int y) {} // records auto-generate these

---

7. Senior-level Insights

Why ArrayList beats LinkedList for insertions

CPU cache lines are 64 bytes. ArrayList's contiguous array allows cache prefetching — when you access index i, the CPU preloads i+1, i+2, etc. LinkedList nodes are scattered in the heap → every node access is a potential cache miss. This makes ArrayList 3–10× faster in practice even for O(n) operations on typical sizes.

HashMap treeification (Java 8+)

Malicious or poorly distributed hashCode implementations can cause O(n) worst-case for HashMap. Java 8 added treeification: when a bucket holds ≥8 entries AND the table has ≥64 buckets, the bucket converts to a Red-Black Tree → O(log n) worst case, preventing DoS attacks via hash flooding.

EnumMap and EnumSet — the forgotten gems

For enum keys, always use these specializations:

// Array-backed, no hashing, O(1) via ordinal index
Map<DayOfWeek, List<Task>> schedule = new EnumMap<>(DayOfWeek.class);
Set<DayOfWeek> workdays = EnumSet.range(MONDAY, FRIDAY);

Deterministic test output

HashMap iteration order is non-deterministic and changes between JVM runs. For tests that verify map contents:

// ✅ Predictable order in tests
Map<String, Integer> sorted = new TreeMap<>(hashMap);
assertEquals("{a=1, b=2}", sorted.toString());

---

8. Glossary

Term	Definition
Load factor	Ratio of entries to buckets (default 0.75); triggers resize when exceeded
Rehashing	Creating a new, larger bucket array and re-inserting all entries — O(n)
Treeification	Java 8+ conversion of a HashMap bucket to Red-Black Tree at ≥8 entries
Cache locality	How well data fits into CPU cache lines; contiguous arrays have excellent locality
Amortized O(1)	Average O(1) over many operations despite occasional O(n) spikes (e.g., resize)
LRU cache	Least Recently Used — evicts the least recently accessed entry when full

---

9. Cheatsheet

• 📋 ArrayList — default List. O(1) get. Pre-size: new ArrayList<>(n)
• 🔗 LinkedList — avoid as List. Use as Deque only. ~48 bytes/node overhead
• 🗺️ HashMap — default Map. O(1) avg. Treeifies at ≥8 entries/bucket
• 🔗 LinkedHashMap — HashMap + insertion/access order. LRU cache with removeEldestEntry
• 🌲 TreeMap — O(log n), sorted keys. Use for range queries, firstKey(), headMap()
• 🔑 HashSet = HashMap under the hood. Requires correct equals/hashCode
• ⚠️ Mutable HashMap/HashSet keys = lost entries — use immutable keys always
• 📏 Pre-size HashMap: new HashMap<>((int)(n / 0.75) + 1) to avoid rehashing
• 🚀 EnumMap/EnumSet for enum keys — array-backed, no hashing needed
• 🔄 Iterate Map with entrySet() or forEach(), never keySet() + get(key)