Course contentsShow
← Java
Lesson 988 of 2,87023. Collections Framework OverviewFree lesson

Performance Characteristics Summary: Big-O Complexities

Quick reference for add, remove, contains, and get operations across ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap.

Performance Characteristics Summary: Big-O Complexities

What you'll learn: You'll get a quick-reference guide to the time complexity of common operations across the major collection types you've been learning.

Why Big-O Matters for Collections

Understanding Big-O notation helps you choose the right collection for your use case. A HashMap might feel "fast," but if you need sorted iteration, that TreeMap's O(log n) lookup becomes your friend. Let's see how the collections you've studied stack up.

Operation Complexity Chart

ArrayList

  • add (at end): O(1) amortized
  • remove (at end): O(1)
  • contains: O(n) — must scan entire list
  • get (by index): O(1) — direct array access

LinkedList

  • add (at beginning/end): O(1)
  • remove (at beginning/end): O(1)
  • contains: O(n) — must traverse nodes
  • get (by index): O(n) — must walk the chain

HashSet

  • add: O(1) average case
  • remove: O(1) average case
  • contains: O(1) average case — hash lookup magic

TreeSet

  • add: O(log n) — maintains sorted red-black tree
  • remove: O(log n)
  • contains: O(log n) — binary search structure

HashMap

  • put: O(1) average case
  • remove: O(1) average case
  • get: O(1) average case
  • containsKey: O(1) average case

TreeMap

  • put: O(log n)
  • remove: O(log n)
  • get: O(log n)
  • containsKey: O(log n)

The Pattern

Hash-based structures (HashSet, HashMap) trade memory and unordered storage for blazing O(1) speed. Tree-based structures (TreeSet, TreeMap) keep things sorted at the cost of O(log n) operations. Lists provide indexed access but suffer O(n) searches.

Key Takeaway: Choose ArrayList for indexed access, LinkedList for frequent head/tail operations, HashSet/HashMap for fastest lookups without ordering, and TreeSet/TreeMap when you need sorted iteration with acceptable O(log n) performance.