Level 1 · 20 min

Java Collections

Java Collections Framework provides a unified architecture for representing and manipulating groups of objects. Understanding the right data structure for each use case is critical for writing efficient, scalable backend code.

ArrayList vs LinkedList

ArrayList is backed by a dynamic array, providing O(1) random access but O(n) insertions at arbitrary positions. LinkedList uses doubly-linked nodes, giving O(1) insertions at head/tail but O(n) access by index. In practice, ArrayList outperforms LinkedList for most workloads due to CPU cache locality — array elements are stored contiguously, making sequential access extremely fast.

HashMap Internals

HashMap uses an array of buckets with chaining (linked lists or balanced trees for bins with more than 8 entries since Java 8). The hash function distributes keys across buckets using the formula: index = hash(key) & (capacity - 1). A load factor of 0.75 triggers resizing at 75% capacity, which is a deliberate trade-off between memory usage and collision rate. When resizing, HashMap allocates a new array of double the capacity and rehashes all existing entries — an O(n) operation. This is why pre-sizing a HashMap with an expected capacity (new HashMap<>(expectedSize / 0.75 + 1)) avoids resize penalties when the final size is known. Note that HashMap's state is distributed: as Goetz et al. note in Java Concurrency in Practice, a HashMap's state 'is partially stored in the HashMap object itself, but also in many Map.Entry objects' — this distributed state is why concurrent modification without synchronization can corrupt the internal structure permanently, not just produce stale reads. Use ConcurrentHashMap for concurrent access; it segments the lock to allow 16 concurrent writers by default in Java 7, and uses CAS + synchronized on individual bins in Java 8.

Trade-offs in Practice

Choose ArrayList for random reads and bulk operations. Choose ArrayDeque (not LinkedList) for queue/stack operations — it has better cache performance. Choose LinkedHashMap when you need insertion-order iteration alongside O(1) lookups. Use TreeMap when you need sorted key ordering with O(log n) operations.

Key Takeaways

ArrayList wins for random access; ArrayDeque wins for queue/stack; LinkedList rarely wins in modern JVMs.
HashMap resizes at 75% load factor — pre-size with new HashMap<>(expectedSize / 0.75 + 1) when size is known.
Collections.unmodifiableList() is a view, not a copy — the underlying list can still be mutated. Use List.copyOf() for true immutability.

Code example

// Pre-sized HashMap to avoid rehashing
Map<String, Integer> wordCount = new HashMap<>(1024);

// ArrayDeque as a stack (faster than Stack/LinkedList)
Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
String top = stack.pop(); // "second"

// LinkedHashMap: access-order LRU cache
Map<String, Object> lru = new LinkedHashMap<>(16, 0.75f, true) {
  @Override
  protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) {
    return size() > 100;
  }
};