Skip to content
Tutorials Center
My learning

Topics

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

Java Counting steps instead of time

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.

Java Same job, different collection

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 is O(n log n).
  • size() is O(1) on all standard collections (ConcurrentHashMap.size() is an estimate under concurrent updates; ConcurrentLinkedQueue.size() is O(n)).
  • Resizing: ArrayList grows by about 50% and HashMap doubles; give an initial capacity when you know the size. A HashMap resizes when the load factor (0.75 by default) is exceeded.
  • Hash quality: O(1) assumes hashCode() spreads keys. A constant hash code turns a HashMap into 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 is O(n) for the search plus the shift; removeIf does one pass, O(n) total.
  • subList and reversed() views cost O(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.