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.

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;
  }
};