A program can be correct and still too slow. A lookup that scans a million-element list ten times per second will bring a server to its knees, while a HashMap answers the same question in microseconds. Big-O notation is how engineers talk about that difference without naming specific computers or stopwatch times. It measures how an algorithm's work grows as its input grows — the shape of the curve, not the height. This lesson maps those curves onto Java's collections so you can pick the right container for the work at hand.
flowchart LR
subgraph ArrayList
A1["get by index"] --> A2["O(1)"]
A3["add at end"] --> A4["O(1) amortized"]
A5["add middle"] --> A6["O(n)"]
end
subgraph LinkedList
L1["get by index"] --> L2["O(n)"]
L3["add at end"] --> L4["O(1)"]
L5["add middle"] --> L6["O(1) with iterator"]
end
style A2 fill:#3776ab,color:#fff
style A4 fill:#3776ab,color:#fff
style L4 fill:#3776ab,color:#fff
style A6 fill:#b45309,color:#fff
style L2 fill:#b45309,color:#fff
style L6 fill:#b45309,color:#fff
Reading the curves
O(1) means constant time: the operation takes roughly the same effort whether the collection holds one item or one million. O(n) means linear: double the size, double the work. O(log n) grows so slowly that it behaves like constant time for most real sizes — ten operations for a thousand items, twenty for a million. O(n log n) is the cost of efficient sorting. O(n squared) is the danger zone: doubling the input quadruples the work, and it collapses under load.
Big-O drops constants and lower-order terms. An algorithm that does 3n + 10 operations is O(n). The 3 and the 10 matter in profiling, but they do not change the shape of the disaster when n grows large.
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("first");
list.add("second");
System.out.println(list.get(0));
System.out.println(list.size());
}
}
ArrayList: the default list
An ArrayList is a resizable array. Accessing by index — list.get(500) — is O(1) because the array lives in one contiguous chunk of memory and the computer jumps straight to the offset. Adding to the end is O(1) on average, though occasionally the array fills up and must be copied into a larger backing array; that occasional copy is why the notation says amortized O(1).
The weakness is the middle. Inserting or removing at position i shifts every element after it one slot left or right. In the worst case — position 0 in a million-element list — that is a million moves, so insert and remove are O(n).
LinkedList: nodes and pointers
A LinkedList is a chain of nodes, each holding an element and a pointer to the next node. Adding or removing at the ends is O(1) because only the nearest neighbour's pointer changes. Inserting in the middle is also O(1) — if you already have a reference to the node before it.
The weakness is access. list.get(500) starts at the head and follows 500 pointers. Doubling the list doubles the walk, so get is O(n). In practice, LinkedList loses to ArrayList on most workloads because array storage is cache-friendly: the CPU fetches adjacent elements in bulk, while chasing pointers scatters memory accesses. The Java Collections Framework documentation itself warns that LinkedList is usually the wrong choice.
flowchart LR HM["HashMap"] --> HG["O(1) average get/put"] HM --> HU["unsorted keys"] TM["TreeMap"] --> TG["O(log n) guaranteed"] TM --> TS["sorted keys"] style HM fill:#3776ab,color:#fff style TM fill:#c2410c,color:#fff
import java.util.LinkedList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new LinkedList<>();
list.add("alpha");
list.add("beta");
list.add(0, "zero");
System.out.println(list.get(0));
System.out.println(list.get(list.size() - 1));
}
}
HashMap and TreeMap: dictionaries with different guarantees
A HashMap offers O(1) average time for put and get. It hashes the key to find a bucket, then checks that bucket for a match. The guarantee is average, not worst-case: if every key collides into the same bucket, performance degrades to O(n). In practice, with decent hashCode implementations, this is rare.
A TreeMap stores keys in a balanced binary search tree. Every put and get is O(log n) guaranteed, and the keys are always kept in sorted order. When you need sorted traversal or range queries — every key between Tuesday and Friday — TreeMap is the right tool. When you only need fast lookups and do not care about order, HashMap wins.
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<String, Integer> scores = new HashMap<>();
scores.put("Ada", 95);
scores.put("Linus", 88);
System.out.println(scores.get("Ada"));
System.out.println(scores.size());
}
}
flowchart LR AR["ArrayList contiguous memory"] --> AC["CPU caches blocks fast sequential access"] LL["LinkedList scattered nodes"] --> LC["chase pointers cache misses"] style AR fill:#3776ab,color:#fff style LL fill:#b45309,color:#fff
Choosing for the workload
Start with the operations your program actually performs, not the ones you imagine it might. If the dominant operation is random access by index, ArrayList is unbeatable. If you are building a lookup table keyed by username, HashMap is the default. If you need the keys in alphabetical order for a report, TreeMap saves you from sorting afterwards. If you are only ever adding and removing at the ends and never accessing by index, LinkedList becomes defensible. Measure first, optimise second — but choose the right structure at the outset and you often never need to optimise at all.
ArrayList access and removal. Predict the exact output (two lines).
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(30);
System.out.println(list.get(1));
list.remove(1);
System.out.println(list.get(1));
}
}
get(1) returns the second element, which is 20.
After remove(1), the list is [10, 30], so get(1) is now 30.
What is the time complexity of ArrayList.get(i) for a valid index i?
ArrayList is backed by an array. The JVM computes the memory offset directly from the index, so any valid index is reached in constant time regardless of list size.
Which collection always keeps its keys in sorted order and guarantees O(log n) put and get?
TreeMap uses a red-black tree, a balanced binary search tree. This guarantees O(log n) operations and maintains keys in their natural or Comparator-defined order. HashMap offers no ordering guarantee.
Why does ArrayList usually outperform LinkedList in practice, even for workloads with many insertions?
Modern CPUs fetch memory in cache lines. ArrayList's contiguous storage means adjacent elements are already in cache when one is accessed. LinkedList nodes can be scattered across the heap, causing cache misses on every pointer chase.
Your program receives millions of user IDs and must check whether each has been seen before. Order does not matter. Which collection gives the best average-case performance for this workload?
HashSet offers average O(1) add and contains, making it ideal for duplicate detection at scale. The other structures require linear or logarithmic scans that become bottlenecks when the input reaches millions.
Recap
- Big-O describes growth, not seconds. O(1) is flat, O(n) is linear, O(n squared) is dangerous.
- ArrayList gives O(1) index access and amortised O(1) append; middle insert is O(n).
- LinkedList gives O(1) add/remove at the ends but O(n) random access; cache locality usually makes ArrayList faster in practice.
- HashMap gives O(1) average lookup and put; TreeMap gives O(log n) guaranteed and keeps keys sorted.
- Choose the structure that matches your dominant operation, then verify with measurement.
You now have the tools to organise data, sort it, and reason about its performance.