Big-O cheat sheet

Collections · lesson 30 of 42 · 3 min read

The real cost of the operations you repeat, for the collections you actually use.

Open this lesson in the learning hub

Key points

  • ArrayList: get O(1), append amortised O(1), insert or remove in the middle O(n), contains O(n).
  • LinkedList: add or remove at either end O(1), anything by index or by value O(n).
  • HashMap and HashSet: get, put and contains O(1) on average, O(log n) in a treeified bucket.
  • TreeMap and TreeSet: every lookup, insert and range query O(log n), and the keys stay sorted.
  • ArrayDeque: both ends O(1). PriorityQueue: offer and poll O(log n), peek O(1).
  • Constants still matter: scanning a 100-element ArrayList often beats a HashMap lookup. Measure before you switch.

Choose by the operation you repeat most, not by the collection you type most.

Nulls in collections Sequenced collections (Java 21)

This is a reading copy. The full lesson — with the visual explainer, the interactive lab and a Run button for the code — lives in the Collections course, and every lesson in it is listed on the Collections contents page.