Quadratic Removal¶

Rule details


Rule ID	`quadratic-removal`
Severity	WARNING — likely performance problem
Confidence	MEDIUM — likely correct, some context-dependent
Category	Loop amplifiers
Complexity	O(n²) → O(n)

Description¶

Detects remove() calls on lists inside loops. Each ArrayList.remove() shifts all subsequent elements one position, making it O(n) per removal. In a loop, this compounds to O(n²).

This rule excludes Map.remove() (O(1) for HashMap), Set.remove() (O(1) for HashSet), Iterator.remove() (safe), and removeFirst()/removeLast() (which indicate Queue/Deque usage where removal is O(1)).

Typical¶

Java

for (String cancelledId : cancelledOrderIds) {
    orders.remove(cancelledId);    // Shifts remaining elements each time: O(n) per call
}

After¶

JavaJava (alternative)Java (filter)

Set<String> cancelledSet = new HashSet<>(cancelledOrderIds);
orders.removeAll(cancelledSet);    // Single pass: O(n)

orders.removeIf(o -> cancelledOrderIds.contains(o));  // Single pass with Iterator

List<String> remaining = orders.stream()
    .filter(o -> !cancelledOrderIds.contains(o))
    .collect(Collectors.toList());

Suggestion¶

Use removeAll() with a Set, Iterator.remove(), or filter into a new collection