skip to content

When is using List.contains/indexOf for membership testing the wrong choice, and what should you use instead?

level: seniorimportance: should knowfreq 40%

answer

  1. List.contains is O(n)
  2. Loop of lookups -> O(n*m)
  3. HashSet membership ~O(1)
  4. Set needs equals AND hashCode
  5. TreeSet for sorted/range, LinkedHashSet for order

basics

~10 s

List.contains/indexOf scan the whole list, so each check is O(n). If you do many membership checks, that becomes slow (O(n*m)). Use a HashSet instead, which checks membership in roughly O(1) on average.

solid answer

~40 s

List.contains and List.indexOf perform a linear, equals-based scan, so each call is O(n). That is fine for occasional checks or small lists, but if you repeatedly test membership against a large collection, or do it inside a loop, you get O(n*m) and it dominates runtime. The right tool is a hash-based set: build a HashSet from the data once (O(n)) and then each contains is average O(1). The tradeoff is extra memory and that the elements need a correct equals AND hashCode (the same equals that List relied on, plus a consistent hashCode). If you also need ordering use a LinkedHashSet, or for sorted/range queries a TreeSet (O(log n)). Keep a List when you need indexed access, duplicates, or insertion order and membership is rare.

code

java · 11 lines
java
List<String> known = loadKnown();      // large
List<String> incoming = loadIncoming();

// Slow: O(n*m)
// for (String x : incoming) if (known.contains(x)) handle(x);

// Fast: build a set once, then O(1) average lookups -> O(n + m)
Set<String> knownSet = new HashSet<>(known);
for (String x : incoming) {
    if (knownSet.contains(x)) handle(x);
}

go deeper

for a junior

Knows contains scans the list and that a HashSet is faster for checking membership many times.

for a middle

Can quantify O(n) per call and O(n*m) in a loop, and converts to a HashSet, remembering hashCode is now required.

for a senior

Chooses among HashSet/LinkedHashSet/TreeSet by ordering and range needs, weighs memory and the equals/hashCode contract, and keeps a List when index/duplicates/order matter.

for a principal

Drives data-structure choice from access patterns and scale, considers maintaining dual structures, hashing quality/collisions, and the cost of getting equals/hashCode wrong across a large codebase.

## The cost of List membership `List.contains(o)` and `indexOf(o)` walk the list element by element, calling `equals` until they find a match or hit the end. That is **O(n)** per call — there is no index or hash to jump to the element. `lastIndexOf` is the same, scanning from the back. ## When it becomes a problem One occasional check on a small list is negligible. The trap is **repeated** checks: ``` for (Item x : incoming) { // m items if (known.contains(x)) ... // O(n) each } ``` This is **O(n*m)** — quadratic when both grow. The classic symptom is code that is fine in tests but crawls on production-sized data. ## The fix: hash-based membership A `HashSet` stores elements in buckets indexed by `hashCode`, so `contains` is **average O(1)** (worst case O(n) with bad hashing). Convert once and reuse: ``` Set<Item> knownSet = new HashSet<>(known); // O(n) once for (Item x : incoming) { if (knownSet.contains(x)) ... // average O(1) each } ``` Now the loop is **O(n + m)**. ## Requirements and tradeoffs - **equals + hashCode:** hash sets use **both**. Elements must implement a correct `hashCode` consistent with `equals` (records do this for free). A List only needed `equals`; moving to a Set adds the `hashCode` requirement. - **Memory:** a `HashSet` uses more memory per element than an array-backed list. - **No duplicates / no index / no order:** a `HashSet` drops duplicates and has no positional access and no defined iteration order. If you need order, use `LinkedHashSet` (insertion order) or `TreeSet` (sorted, O(log n) ops, supports range queries via `subSet`/`headSet`/`tailSet`). ## When to keep the List - You need **indexed access** (`get(i)`), the **first/last position** (`indexOf`/`lastIndexOf`), or to preserve **duplicates** and **insertion order**, and membership tests are rare or the list is small. - You can also keep a List as the primary structure and maintain a parallel `Set` for fast membership when you need both. ## Rule of thumb Occasional check or tiny list -> `List.contains` is fine. Hot path or large data -> build a `Set`. The decision is about **how many lookups** you do, not just the data size.

  • If you need fast membership but also sorted order and range queries, which structure fits?
    TreeSet. It keeps elements sorted, gives O(log n) contains/add, and supports range views via subSet/headSet/tailSet. It needs Comparable elements or a Comparator.
  • You need both indexed access and frequent membership checks. What is a pragmatic approach?
    Keep the List as the canonical ordered/indexed structure and maintain a parallel HashSet of the same elements for O(1) membership, updating both on insert/remove.

saying these in an interview costs you the question

  • Calling list.contains inside a loop over large data
  • Thinking List has a fast membership index
  • Switching to HashSet but forgetting hashCode
  • Ignoring that a Set drops duplicates and order

context

resolving links…