Java Collections Deep Dive: ArrayList, HashMap, TreeMap, LinkedHashMap and When to Use Each

The Java Collections Framework is one of the most tested topics in Java interviews. Knowing that HashMap is O(1) and TreeMap is O(log n) is not enough — interviewers want to know why, when to use each, and what happens under the hood. This guide goes beyond the surface.

The Collection Hierarchy

code
Iterable
  └── Collection
        ├── List
        │     ├── ArrayList
        │     ├── LinkedList
        │     └── Vector (legacy)
        ├── Set
        │     ├── HashSet
        │     ├── LinkedHashSet
        │     └── TreeSet
        └── Queue
              ├── LinkedList
              ├── PriorityQueue
              └── ArrayDeque

Map (not a Collection)
  ├── HashMap
  ├── LinkedHashMap
  ├── TreeMap
  └── Hashtable (legacy)

List Implementations

ArrayList

Backed by a resizable array. When full, it creates a new array 1.5× larger and copies elements.

Operation	Complexity	Notes
get(i)	O(1)	Random access via index
add(element)	O(1) amortized	Occasional resize is O(n)
add(i, element)	O(n)	Shifts elements right
remove(i)	O(n)	Shifts elements left
contains(element)	O(n)	Linear scan

java
List<String> list = new ArrayList<>();
list.add("Alice");
list.add("Bob");
list.add(0, "Zara");       // O(n) -- inserts at index 0, shifts others
list.remove("Bob");         // O(n) -- finds by value, then shifts
list.get(1);                // O(1) -- direct index access

// Pre-size if you know the capacity
List<String> sized = new ArrayList<>(10000);

Use ArrayList when: You need random access by index, add/remove mostly at the end, and iteration is frequent.

LinkedList

Doubly linked list. Each element is a node with references to previous and next.

Operation	Complexity	Notes
get(i)	O(n)	Must traverse from head or tail
add(element)	O(1)	Append to tail
addFirst/addLast	O(1)	Direct node insertion
remove(i)	O(n)	Find first, then O(1) removal
Iterator remove	O(1)	Direct node removal

java
LinkedList<String> list = new LinkedList<>();
list.addFirst("Alice");   // O(1)
list.addLast("Bob");      // O(1)
list.removeFirst();       // O(1)
list.peekFirst();         // O(1) -- look without removing

Use LinkedList when: You need frequent insertions/removals at the beginning or end (as a Deque). For most List use cases, ArrayList is faster due to better cache locality.

Map Implementations

HashMap

The most commonly used Map. Uses a hash table internally — an array of buckets, with linked lists or trees for collisions.

java
Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Alice", 99);  // overwrites

scores.get("Alice");                    // 99
scores.getOrDefault("Carol", 0);       // 0
scores.putIfAbsent("Dave", 100);       // only inserts if key absent
scores.computeIfAbsent("Eve", k -> computeScore(k));

// Iteration (order not guaranteed)
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Java 8+ forEach
scores.forEach((name, score) -> System.out.printf("%s: %d%n", name, score));

Operation	Average	Worst case
get	O(1)	O(n)
put	O(1)	O(n)
containsKey	O(1)	O(n)

Worst case occurs with hash collisions — all keys hash to the same bucket. Java 8+ converts buckets from linked lists to red-black trees when they exceed 8 entries, making worst case O(log n) instead of O(n).

Initial capacity and load factor: Default capacity is 16, load factor is 0.75. When 75% full, it resizes (rehashes). Set initial capacity if you know the size to avoid rehashing:

java
Map<String, Integer> map = new HashMap<>(10000); // pre-sized

LinkedHashMap

Maintains insertion order (or access order) by adding a doubly-linked list connecting all entries.

java
// Insertion-ordered
Map<String, Integer> map = new LinkedHashMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);
// Iteration order: C, A, B (insertion order)

// Access-ordered (for LRU cache)
Map<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
        return size() > 100; // evict when over capacity
    }
};

LinkedHashMap with access ordering and removeEldestEntry is a classic LRU cache implementation.

Use LinkedHashMap when: You need insertion or access order, or building a bounded LRU cache.

TreeMap

Red-black tree implementation. Keys are always sorted (natural order or custom Comparator).

java
TreeMap<String, Integer> tree = new TreeMap<>();
tree.put("banana", 3);
tree.put("apple", 1);
tree.put("cherry", 2);

// Navigation methods
tree.firstKey();          // "apple"
tree.lastKey();           // "cherry"
tree.floorKey("b");       // "banana" (largest key <= "b")
tree.ceilingKey("b");     // "banana" (smallest key >= "b")
tree.headMap("cherry");   // map of keys strictly less than "cherry"
tree.tailMap("banana");   // map of keys >= "banana"
tree.subMap("apple", "cherry"); // map of keys in range [apple, cherry)

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

Use TreeMap when: You need sorted keys, range queries, or floor/ceiling operations.

Set Implementations

HashSet, LinkedHashSet, TreeSet

These are wrappers around the corresponding Map implementations (backed by HashMap, LinkedHashMap, TreeMap with dummy values).

java
Set<String> hashSet      = new HashSet<>();     // O(1) ops, no order
Set<String> linkedSet    = new LinkedHashSet<>();// O(1) ops, insertion order
Set<String> treeSet      = new TreeSet<>();      // O(log n) ops, sorted order

// Common use: deduplicate while preserving order
List<String> withDups = List.of("c", "a", "b", "a", "c");
Set<String> unique = new LinkedHashSet<>(withDups); // [c, a, b]

Queue and Deque

PriorityQueue

Min-heap by default. poll() always returns the smallest element.

java
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.poll(); // 1 (minimum)
minHeap.peek(); // 3 (next minimum, no removal)

// Max heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom objects
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority)
);

Use PriorityQueue when: You need to repeatedly access the smallest (or largest) element — task scheduling, Dijkstra's algorithm, top-K problems.

ArrayDeque

Double-ended queue backed by a resizable array. Faster than LinkedList for stack and queue operations.

java
Deque<String> deque = new ArrayDeque<>();

// As a queue (FIFO)
deque.offerLast("Alice");
deque.offerLast("Bob");
deque.pollFirst(); // "Alice"

// As a stack (LIFO) -- preferred over java.util.Stack
deque.push("Alice");  // same as addFirst
deque.push("Bob");
deque.pop();          // "Bob" (LIFO)
deque.peek();         // "Alice"

Use ArrayDeque instead of Stack and LinkedList for stack/queue use cases — it is faster and has clearer semantics.

Choosing the Right Collection

Need	Best choice
Index-based list	ArrayList
Frequent head/tail insert	ArrayDeque or LinkedList
Key-value, fast lookup	HashMap
Key-value, insertion order	LinkedHashMap
Key-value, sorted keys	TreeMap
Unique elements, fast lookup	HashSet
Unique elements, sorted	TreeSet
Min/max priority access	PriorityQueue
LRU cache	LinkedHashMap (access order)
Thread-safe map	ConcurrentHashMap

Common Interview Questions

Q: How does HashMap handle collisions?

Each bucket in the hash table holds a linked list of entries. When multiple keys hash to the same bucket, they are chained. Java 8+ converts a bucket to a red-black tree when it holds more than 8 entries, changing worst-case lookup from O(n) to O(log n).

Q: What is the difference between HashMap and Hashtable?

Hashtable is synchronized (thread-safe) but uses coarse-grained locking — slow under contention. HashMap is not synchronized but faster. For concurrent use, prefer ConcurrentHashMap — it uses fine-grained locking and has far better throughput than Hashtable.

Q: Why is it important to override both equals and hashCode together?

HashMap uses hashCode() to find the bucket and equals() to confirm the key matches. If two objects are equals() but have different hash codes, they will end up in different buckets and HashMap will never find the stored value. The contract: if a.equals(b), then a.hashCode() == b.hashCode().

Practice Java on Froquiz

Collections are tested in almost every Java interview. Test your Java knowledge on Froquiz — covering collections, generics, OOP, concurrency, and more.

Summary

• ArrayList: random access O(1), insert/remove middle O(n) — default choice for lists
• LinkedList: O(1) head/tail ops, O(n) random access — use as Deque, not List
• HashMap: O(1) average — default choice for key-value; buckets use linked list → tree on collision
• LinkedHashMap: HashMap + insertion or access order — use for LRU caches
• TreeMap: O(log n) sorted keys, navigation methods — use for range queries
• PriorityQueue: O(log n) insert/poll, O(1) peek — min-heap by default
• ArrayDeque: faster stack/queue than LinkedList — preferred Deque implementation
• Always override both equals and hashCode for custom keys in HashMap/HashSet