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.

2.2 `LinkedList`

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

2.3 `HashMap`

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

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.

2.6 `HashSet`

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

2.7 `ArrayDeque`

ArrayDeque is usually the best general-purpose choice for queue and stack behavior.

It often beats LinkedList because the data is stored more compactly and benefits from cache locality.

2.8 Choose by workload, not popularity

Implementation choice should follow dominant operations:

• heavy random reads → ArrayList
• front/back queue operations → ArrayDeque
• plain key lookup → HashMap
• stable iteration order → LinkedHashMap
• sorted navigation → TreeMap

2.9 Specialized implementations can be the best option

The real best choice is sometimes not one of the “default” implementations. EnumMap and EnumSet are extremely compact and fast when keys or values are enums. IdentityHashMap compares references instead of equals(), which is only correct for very specific identity-based use cases. ConcurrentHashMap is the better default for shared mutable maps in concurrent code, because it scales far better than wrapping a plain HashMap with coarse synchronization.

This is a good interview signal: first choose the right abstraction, then the right standard implementation, and finally check whether a specialized implementation matches the domain even better.

---

3. Practical Usage

ArrayList vs LinkedList

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

HashMap vs LinkedHashMap vs TreeMap

Practical selection checklist

Before choosing a concrete implementation, ask:

1. Is order part of correctness?
2. Is range navigation required?
3. Is memory overhead a concern?
4. Are inserts, reads, or deletes dominant?
5. Is the data model key-based, sequential, or double-ended?

---

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

HashMap vs LinkedHashMap vs TreeMap

---

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. Deep Dive

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());

Why `ArrayDeque` should replace `Stack`

Stack inherits from Vector, which means legacy synchronization and an awkward API history. ArrayDeque is the modern default for LIFO behavior.

Pre-sizing is a real optimization tool

Large batch inserts into ArrayList or HashMap can trigger repeated growth steps. Supplying a realistic initial capacity reduces allocations, copies, and rehashing.

---

8. Interview Questions

Why is `ArrayList` usually a better default than `LinkedList`?

Because most applications benefit more from compact layout, fast indexed reads, and cache locality than from linked-node insertion characteristics.

When is `LinkedHashMap` preferable to `HashMap`?

When deterministic iteration order matters, such as in stable output, tests, user-facing displays, or LRU-like access tracking.

What is treeification in `HashMap`?

It is the Java 8+ fallback where highly collided buckets convert from linked lists into balanced trees, improving worst-case behavior.

When would you still choose `TreeMap` over `HashMap`?

When sorted keys, navigation methods, or range queries are genuine requirements rather than nice-to-haves.

---

9. Glossary

---

10. 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)