Java Reference ยท Collections
Complexity of Java collections
Big-O costs of the common operations on ArrayList, LinkedList, HashMap, TreeMap, ArrayDeque, PriorityQueue and more, with a demo showing why it matters.
Choosing a collection is mostly choosing which operations are cheap. This page lists the typical costs of the standard java.util collections, where n is the number of elements. "Amortized" means the average over many calls: an occasional expensive step (such as resizing) is spread across the cheap ones.
Big-O ignores constants. A LinkedList insert in the middle is O(1) only once you hold the position; finding the position costs O(n). Cache behavior also matters: arrays of references beat linked nodes in practice even when the Big-O is the same, so ArrayList and ArrayDeque usually win against LinkedList.
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Complexity table
| Collection | Get / contains | Add | Remove | Notes |
|---|---|---|---|---|
ArrayList |
get(i) O(1); contains O(n) |
end: amortized O(1); middle: O(n) |
by index O(n) |
Random access, compact. |
LinkedList |
get(i) O(n); contains O(n) |
ends O(1); middle O(1) after finding position |
ends O(1) |
Poor cache behavior; rarely the best choice. |
ArrayDeque |
peek ends O(1) |
ends amortized O(1) |
ends O(1) |
Best stack and queue. |
HashSet / HashMap |
O(1) average |
O(1) average |
O(1) average |
Worst case O(log n) per bucket since Java 8 (treeified bins). |
LinkedHashSet / LinkedHashMap |
O(1) average |
O(1) average |
O(1) average |
Adds insertion order, small overhead. |
TreeSet / TreeMap |
O(log n) |
O(log n) |
O(log n) |
Sorted; first, floor, ceiling, range views. |
PriorityQueue |
peek O(1); contains O(n) |
offer O(log n) |
poll O(log n); remove(obj) O(n) |
Binary heap, iteration not sorted. |
EnumMap / EnumSet |
O(1) |
O(1) |
O(1) |
Array or bit vector. |
BitSet |
O(1) |
O(1) |
O(1) |
Bulk operations O(n / 64). |
ConcurrentHashMap |
O(1) average |
O(1) average |
O(1) average |
Lock-free reads. |
CopyOnWriteArrayList |
get O(1) |
O(n) (copies) |
O(n) |
Cheap reads and iteration, expensive writes. |
Usage notes
- Whole-collection operations are
O(n): iteration,toArray(), copy constructors,equals(),hashCode(). Sorting isO(n log n). size()isO(1)on all standard collections (ConcurrentHashMap.size()is an estimate under concurrent updates;ConcurrentLinkedQueue.size()isO(n)).- Resizing:
ArrayListgrows by about 50% andHashMapdoubles; give an initial capacity when you know the size. AHashMapresizes when the load factor (0.75 by default) is exceeded. - Hash quality:
O(1)assumeshashCode()spreads keys. A constant hash code turns aHashMapinto a tree or list lookup. - Mutable keys break sets and maps: if a key's hash or ordering changes while stored, lookups fail.
remove(Object)on a list isO(n)for the search plus the shift;removeIfdoes one pass,O(n)total.subListandreversed()views costO(1)to create but the underlying operations keep their own cost.- Measure, don't guess: constants and memory layout can reverse the ranking at small sizes; profile with realistic data before replacing a simple
ArrayList.