Java Collections Framework: Choosing the Right Data Structure

Java ships with a rich library of data structures under the java.util package. The problem is not finding a collection u2014 it is picking the right one. Using an ArrayList when you need fast membership checks, or a HashMap when you need sorted keys, is the kind of mismatch that shows up in code reviews and performance profiles.

This guide maps every important class to the use case it is designed for, explains the time complexity of its key operations, and provides working code you can copy directly into a project. By the end you will have an intuition for which collection to reach for in any situation.

The Collections Hierarchy at a Glance

The Java Collections Framework (JCF) organises its types around three root interfaces:

List<E> — an ordered sequence that allows duplicates and positional access.
Set<E> — an unordered collection that prohibits duplicates.
Map<K,V> — a mapping from unique keys to values (not a Collection sub-interface, but part of the framework).

A fourth interface, Queue<E>, models FIFO and priority-ordered processing. Deque<E> extends Queue to support both-ends access. The table below summarises the most important concrete classes before we go into each in depth.

Class	Interface	Ordered?	Sorted?	Duplicates?	Null keys/values?	Thread-safe?
`ArrayList`	List	Yes (insertion)	No	Yes	Yes	No
`LinkedList`	List, Deque	Yes (insertion)	No	Yes	Yes	No
`HashSet`	Set	No	No	No	One null	No
`LinkedHashSet`	Set	Yes (insertion)	No	No	One null	No
`TreeSet`	Set, SortedSet	Yes (sorted)	Yes	No	No	No
`HashMap`	Map	No	No	Values yes	One null key	No
`LinkedHashMap`	Map	Yes (insertion)	No	Values yes	One null key	No
`TreeMap`	Map, SortedMap	Yes (sorted)	Yes	Values yes	No null key	No
`PriorityQueue`	Queue	Priority order	Yes (heap)	Yes	No	No
`ArrayDeque`	Deque	Yes (insertion)	No	Yes	No	No

1. List: ArrayList vs LinkedList

ArrayList

ArrayList is backed by a resizable array. Random access by index is O(1). Appending to the end is amortised O(1). Inserting or removing in the middle requires shifting elements u2014 O(n). It is the right choice for the overwhelming majority of list use cases.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// --- ArrayList: the go-to List implementation ---
List fruits = new ArrayList<>();
fruits.add("Mango");        // O(1) amortised u2014 append to end
fruits.add("Apple");
fruits.add("Banana");
fruits.add(1, "Pineapple"); // O(n) u2014 shifts elements right from index 1
System.out.println(fruits);         // [Mango, Pineapple, Apple, Banana]
System.out.println(fruits.get(2));  // O(1) random access u2014 "Apple"
System.out.println(fruits.size());  // 4
fruits.remove("Apple");             // O(n) u2014 searches by value, then shifts
Collections.sort(fruits);           // in-place sort u2014 uses TimSort O(n log n)
System.out.println(fruits);         // [Banana, Mango, Pineapple]

LinkedList

LinkedList is a doubly-linked list. Inserting or removing at the front or back is O(1). Random access is O(n) because the list must traverse from either end. Use it when your workload is dominated by frequent insertions/deletions at both ends (i.e., when you need a deque). For general-purpose list use, ArrayList is almost always faster due to cache locality.

import java.util.LinkedList;
// LinkedList as a Deque (double-ended queue)
LinkedList deque = new LinkedList<>();
deque.addFirst("B");   // O(1) u2014 insert at head
deque.addFirst("A");   // O(1)
deque.addLast("C");    // O(1) u2014 insert at tail
deque.addLast("D");    // O(1)
System.out.println(deque);          // [A, B, C, D]
System.out.println(deque.pollFirst()); // "A" u2014 remove and return head O(1)
System.out.println(deque.pollLast());  // "D" u2014 remove and return tail O(1)
System.out.println(deque);          // [B, C]

2. Set: HashSet, LinkedHashSet, TreeSet

HashSet — fastest membership test

import java.util.HashSet;
import java.util.Set;
// HashSet: O(1) add, remove, contains u2014 no ordering guarantee
Set tags = new HashSet<>();
tags.add("java");
tags.add("streams");
tags.add("java");       // duplicate u2014 silently ignored
System.out.println(tags.size());          // 2
System.out.println(tags.contains("java")); // true  u2014 O(1)
System.out.println(tags);                 // order not predictable

LinkedHashSet — insertion-order Set

import java.util.LinkedHashSet;
// LinkedHashSet: same O(1) ops as HashSet, but preserves insertion order
var ordered = new LinkedHashSet();
ordered.add("banana");
ordered.add("apple");
ordered.add("cherry");
ordered.add("apple");  // duplicate
System.out.println(ordered);
// Output: [banana, apple, cherry]  u2014 insertion order maintained, no duplicate

TreeSet — sorted Set

import java.util.TreeSet;
// TreeSet: O(log n) ops; elements kept in natural sorted order
TreeSet scores = new TreeSet<>();
scores.add(85);
scores.add(42);
scores.add(99);
scores.add(67);
System.out.println(scores);           // [42, 67, 85, 99]
System.out.println(scores.first());   // 42  u2014 smallest
System.out.println(scores.last());    // 99  u2014 largest
System.out.println(scores.headSet(80)); // [42, 67]  u2014 elements < 80
System.out.println(scores.tailSet(70)); // [85, 99]  u2014 elements >= 70

3. Map: HashMap, LinkedHashMap, TreeMap

HashMap — the everyday key-value store

import java.util.HashMap;
import java.util.Map;
// HashMap: O(1) amortised get/put/containsKey; keys unordered
Map wordCount = new HashMap<>();
String[] words = {"java", "is", "fast", "java", "is", "great", "java"};
for (String w : words) {
    // getOrDefault returns 0 if key absent; we then add 1
    wordCount.put(w, wordCount.getOrDefault(w, 0) + 1);
}
System.out.println(wordCount);
// {java=3, is=2, fast=1, great=1}  (order varies)
// Java 8+ convenience methods
wordCount.computeIfAbsent("new", k -> 0);       // put only if absent
wordCount.merge("java", 1, Integer::sum);        // add 1 to existing value
System.out.println(wordCount.getOrDefault("missing", -1)); // -1

LinkedHashMap — insertion-order Map

import java.util.LinkedHashMap;
// LinkedHashMap: same as HashMap but iterates in insertion order.
// Commonly used as an LRU cache by overriding removeEldestEntry().
var config = new LinkedHashMap();
config.put("host", "localhost");
config.put("port", "8080");
config.put("timeout", "30");
// Entries come out in the order they were inserted
config.forEach((k, v) -> System.out.println(k + " = " + v));
// host = localhost
// port = 8080
// timeout = 30

TreeMap — sorted Map

import java.util.TreeMap;
// TreeMap: O(log n); keys kept in natural (or custom Comparator) order.
// Implements NavigableMap u2014 useful for range queries.
TreeMap scores = new TreeMap<>();
scores.put("Charlie", 88);
scores.put("Alice",   95);
scores.put("Bob",     72);
System.out.println(scores);           // {Alice=95, Bob=72, Charlie=88} u2014 sorted by key
System.out.println(scores.firstKey()); // Alice
System.out.println(scores.lastKey());  // Charlie
// All entries with keys strictly less than "Charlie"
System.out.println(scores.headMap("Charlie")); // {Alice=95, Bob=72}

4. Queue and Deque: PriorityQueue and ArrayDeque

PriorityQueue — smallest element first

import java.util.PriorityQueue;
// Min-heap by default: poll() always returns the smallest element in O(log n)
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.offer(30);
minHeap.offer(10);
minHeap.offer(20);
while (!minHeap.isEmpty()) {
    System.out.print(minHeap.poll() + " ");  // 10 20 30
}
// Max-heap: reverse the comparator
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(30);
maxHeap.offer(10);
maxHeap.offer(20);
System.out.println(maxHeap.peek());  // 30  u2014 peek without removing

ArrayDeque — preferred stack and queue implementation

ArrayDeque is faster than both Stack (legacy, synchronised) and LinkedList for stack and queue use because it is backed by a resizable circular array with no node allocation overhead.

import java.util.ArrayDeque;
import java.util.Deque;
// Using ArrayDeque as a stack (LIFO)
Deque stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
stack.push("third");
System.out.println(stack.pop());   // "third"  u2014 O(1) LIFO
System.out.println(stack.peek());  // "second" u2014 look without removing
// Using ArrayDeque as a queue (FIFO)
Deque queue = new ArrayDeque<>();
queue.offer("task-1");
queue.offer("task-2");
queue.offer("task-3");
System.out.println(queue.poll());  // "task-1"  u2014 O(1) FIFO

5. Immutable and Unmodifiable Collections (Java 9+)

// List.of / Set.of / Map.of produce truly immutable, compact instances.
// Any mutating call throws UnsupportedOperationException.
List immutableList = List.of("a", "b", "c");
Set  immutableSet  = Set.of(1, 2, 3);
Map immutableMap = Map.of("one", 1, "two", 2);
// Map.copyOf and List.copyOf create an immutable *copy* of an existing collection
var mutable = new ArrayList<>(List.of("x", "y", "z"));
List snapshot = List.copyOf(mutable);   // safe immutable snapshot
mutable.add("w");
System.out.println(snapshot);  // [x, y, z]  u2014 snapshot is unaffected

6. Decision Guide: Which Collection to Use

You need…	Use
A general-purpose ordered list with fast random access	`ArrayList`
A list with frequent insertions/deletions at both ends	`ArrayDeque` (as Deque) or `LinkedList`
Fast membership checks, no duplicates, order doesn’t matter	`HashSet`
No duplicates, insertion order matters	`LinkedHashSet`
No duplicates, elements always sorted	`TreeSet`
Fast key-value lookup, order doesn’t matter	`HashMap`
Key-value lookup, insertion order matters (e.g. LRU cache)	`LinkedHashMap`
Key-value lookup, keys always sorted or range queries needed	`TreeMap`
Process items by priority (min or max heap)	`PriorityQueue`
A stack (LIFO)	`ArrayDeque` (`push` / `pop`)
A FIFO queue	`ArrayDeque` (`offer` / `poll`)
Thread-safe list	`CopyOnWriteArrayList` (read-heavy) or `Collections.synchronizedList`
Thread-safe map	`ConcurrentHashMap`

7. Time Complexity Reference

Operation	ArrayList	LinkedList	HashSet/HashMap	TreeSet/TreeMap
get(index)	O(1)	O(n)	—	—
add (end)	O(1)*	O(1)	O(1)*	O(log n)
add (middle)	O(n)	O(n) to find + O(1)	—	—
remove by value	O(n)	O(n)	O(1)*	O(log n)
contains / get	O(n)	O(n)	O(1)*	O(log n)
Iteration	O(n)	O(n)	O(n)	O(n) in sorted order

* Amortised — occasional resizing costs O(n) but is rare enough to average out to O(1).

Conclusion

The choice of collection has a direct impact on performance, correctness, and code clarity. The mental model is straightforward: reach for ArrayList and HashMap by default; upgrade to TreeSet or TreeMap when you need sorted order; use LinkedHashMap or LinkedHashSet when insertion order matters; use ArrayDeque for stacks and queues. For concurrency, leave the single-threaded collections behind and go directly to ConcurrentHashMap or CopyOnWriteArrayList. When in doubt, refer back to the complexity table and let the access pattern of your algorithm guide the choice.

@ankurm