ArrayList, LinkedList, HashMap, TreeMap — When Each One Is Actually the Right Choice

Why the complexity numbers aren't the whole story

Big-O complexity tells you how performance scales with size. It doesn't tell you the constant factor, the memory overhead per element, or whether the access pattern fits the CPU cache. A LinkedList has O(1) head insertion; an ArrayList has O(n) for the same operation. In practice, ArrayList is faster for most insertion workloads because its array-backed storage is cache-friendly and the O(n) shift is a System.arraycopy — one native call that copies contiguous memory.

Modern CPUs prefetch data sequentially. Arrays are sequential in memory. Linked structures scatter nodes across the heap. For collections of a few thousand elements, the cache advantage of arrays frequently outweighs the theoretical complexity advantage of linked structures.

ArrayList — the correct default for lists

ArrayList backs a List with a resizable array. Random access is O(1) — an array index operation. Iteration is cache-friendly — elements are contiguous in memory. Appending to the end is amortized O(1) — the array doubles when full (growth factor 1.5 in OpenJDK), so most appends are simple array writes.

List<Order> orders = new ArrayList<>();
orders.add(order);          // O(1) amortized — append to end
orders.get(42);             // O(1) — array index
orders.contains(order);     // O(n) — linear scan
orders.remove(0);           // O(n) — shifts all elements left

Pre-size when the approximate count is known:

List<Order> orders = new ArrayList<>(expectedSize);

Without pre-sizing, the array may resize several times as elements are added. Each resize allocates a new array and copies all existing elements — O(n) for each resize. With pre-sizing, no resizing occurs if expectedSize is accurate, saving several array copies and GC pressure.

When ArrayList is the wrong choice: frequent insertion or removal in the middle of a large list. remove(index) shifts all subsequent elements — O(n). If the list has 100,000 elements and you remove from index 0, 100,000 elements shift. For this access pattern, a different structure is needed — though often the right answer is to reconsider the data structure design rather than switch to LinkedList.

LinkedList — narrower than its name suggests

LinkedList implements both List and Deque. As a List, it rarely wins. As a Deque, it's more competitive but still often loses to ArrayDeque.

The LinkedList use case that actually holds up: a queue or deque with frequent insertion and removal from both ends, where the list is large and you want to avoid array reallocation:

// As a Deque
Deque<Task> taskQueue = new LinkedList<>();
taskQueue.addFirst(urgentTask);  // O(1) — add to head
taskQueue.addLast(normalTask);   // O(1) — add to tail
taskQueue.pollFirst();           // O(1) — remove from head

But ArrayDeque is almost always faster for this use case too. It uses a circular array — O(1) insertion and removal at both ends, no node allocation per element, cache-friendly storage. The only scenario where LinkedList wins is when you need to hold a ListIterator and remove elements at the iterator's position during iteration — LinkedList.ListIterator.remove() is O(1); the equivalent on ArrayList is O(n).

// The one LinkedList advantage — O(1) removal at iterator position
ListIterator<Order> it = linkedList.listIterator();
while (it.hasNext()) {
    Order order = it.next();
    if (shouldRemove(order)) {
        it.remove(); // O(1) for LinkedList, O(n) for ArrayList
    }
}

For most application code, the rule is: use ArrayList for lists, ArrayDeque for queues and stacks. Reach for LinkedList only when you specifically need iterator-position removal at scale.

HashMap — the correct default for maps

HashMap stores key-value pairs in a hash table. Lookup, insertion, and deletion are O(1) average — a hash computation followed by an array index. The hash table is backed by an array of buckets; each bucket holds a linked list (or a balanced tree for buckets with many collisions, since Java 8).

Map<String, Order> orderById = new HashMap<>();
orderById.put(order.getId(), order);    // O(1) average
orderById.get("ord-123");               // O(1) average
orderById.containsKey("ord-123");       // O(1) average

Load factor and initial capacity. The default load factor is 0.75 — the table resizes when 75% full. Resizing rehashes all entries into a new, larger array — O(n). If you know the approximate number of entries, pre-size to avoid resizing:

// Pre-size to hold 1000 entries without resizing
// capacity = expectedEntries / loadFactor + 1
Map<String, Order> orders = new HashMap<>(1334); // 1000 / 0.75 ≈ 1334

Hash collisions. HashMap performance degrades when many keys hash to the same bucket. A pathological case: string keys where an attacker controls the input and crafts keys with identical hash codes — hash flooding. Since Java 8, buckets with more than 8 entries convert from linked lists to balanced trees (Red-Black trees), capping worst-case lookup at O(log n) rather than O(n).

Iteration order. HashMap provides no iteration order guarantee. Iteration order may change between runs, between JVM versions, or after a resize. Never write code that depends on HashMap iteration order.

LinkedHashMap — insertion order with hash performance

LinkedHashMap extends HashMap with a doubly-linked list connecting entries in insertion order (or access order if configured). Lookup is still O(1) — the hash table. Iteration is O(n) in insertion order rather than arbitrary order.

Map<String, Config> config = new LinkedHashMap<>();
config.put("timeout", "30");
config.put("retries", "3");
config.put("endpoint", "https://api.example.com");

// Iteration is in insertion order — predictable, useful for display/serialization
config.forEach((k, v) -> System.out.println(k + "=" + v));

LinkedHashMap in access-order mode is the foundation for an LRU cache — when removeEldestEntry is overridden:

private static final int MAX_ENTRIES = 1000;

Map<String, User> lruCache = new LinkedHashMap<String, User>(
        MAX_ENTRIES, 0.75f, true) { // true = access order
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, User> eldest) {
        return size() > MAX_ENTRIES;
    }
};

This is a bounded LRU cache in 10 lines. The least-recently-accessed entry is evicted when capacity is exceeded. Not thread-safe — use Collections.synchronizedMap() or Caffeine for concurrent LRU.

TreeMap — sorted keys with O(log n) operations

TreeMap stores entries in a Red-Black tree, maintaining keys in sorted order. Lookup, insertion, and deletion are O(log n). Iteration is in natural key order (or Comparator order).

TreeMap<LocalDate, List<Order>> ordersByDate = new TreeMap<>();
ordersByDate.put(LocalDate.now(), todayOrders);

// Navigation operations — not available in HashMap
ordersByDate.firstKey();                              // smallest key
ordersByDate.headMap(LocalDate.now());               // keys < today
ordersByDate.subMap(startDate, endDate);             // keys in range
ordersByDate.floorKey(LocalDate.now().minusDays(7)); // largest key ≤ one week ago

The navigation methods (headMap, tailMap, subMap, floorKey, ceilingKey) are the reason to use TreeMap. If you only need sorted iteration without range queries, sorting a HashMap's entries at iteration time is often simpler. If you need range queries on sorted keys, TreeMap is the right structure.

TreeMap is 3–5x slower than HashMap for individual operations on large maps due to tree traversal vs array indexing. This matters in hot paths. For configuration maps, reporting maps, and anything queried infrequently, the difference is irrelevant.

HashSet and TreeSet

HashSet is a HashMap with dummy values — same performance characteristics, no ordering. TreeSet is a TreeMap with dummy values — sorted iteration, O(log n) operations, navigation methods.

contains() on HashSet is O(1). contains() on ArrayList is O(n). For membership testing at any scale, prefer Set over List:

// O(n) membership test — scans the list
List<String> validStatuses = List.of("pending", "processing", "shipped");
if (validStatuses.contains(order.getStatus())) { ... }

// O(1) membership test
Set<String> validStatuses = Set.of("pending", "processing", "shipped");
if (validStatuses.contains(order.getStatus())) { ... }

For small, fixed sets of known values, EnumSet is faster than HashSet — a bitfield operation rather than a hash lookup.

ArrayDeque — the underused structure

ArrayDeque is a double-ended queue backed by a circular array. It should be the default for stack and queue use cases:

Deque<Task> stack = new ArrayDeque<>(); // use as stack
stack.push(task);    // addFirst
stack.pop();         // removeFirst

Deque<Task> queue = new ArrayDeque<>(); // use as queue
queue.offer(task);   // addLast
queue.poll();        // removeFirst

ArrayDeque is faster than Stack (synchronized, based on Vector) and faster than LinkedList for queue operations. It's the correct replacement for both. The only missing feature compared to LinkedList: ArrayDeque does not permit null elements — a restriction that rarely matters in practice.

The decision in practice

For ordered sequence with index access: ArrayList. Pre-size when count is known.

For queue or stack: ArrayDeque. Not Stack, not LinkedList.

For key-value lookup: HashMap. Pre-size when count is known.

For key-value with insertion-order iteration: LinkedHashMap.

For key-value with sorted keys or range queries: TreeMap.

For membership testing: HashSet. EnumSet when keys are enum constants.

For sorted unique values: TreeSet.

For any of these in a concurrent context: ConcurrentHashMap, CopyOnWriteArrayList, ConcurrentLinkedDeque — covered in the concurrency articles. The non-concurrent collections are not thread-safe and will corrupt under concurrent modification without external synchronization.