Java 일반 for문과 향상된 for문, 자료구조별 성능 차이

문제 발생

"향상된 for문이 항상 느리다" 또는 "항상 빠르다"는 식으로 일반화해서 알고 있는 경우가 많습니다. 실제로는 어떤 컬렉션을 순회하느냐에 따라 결과가 달라집니다.

원인 분석

인덱스 for문(for (int i = 0; i < list.size(); i++))은 list.get(i)를 호출합니다. ArrayList는 배열 기반이라 get(i)가 O(1)이지만, LinkedList는 연결 리스트라 get(i)가 매번 처음(또는 끝)부터 i번째까지 순회하는 O(n) 연산입니다. 즉 인덱스 for문으로 LinkedList를 순회하면 전체가 O(n²)이 됩니다.

향상된 for문(for (Element e : list))은 내부적으로 Iterator를 사용합니다. Iterator.next()는 ArrayList와 LinkedList 둘 다 O(1)이므로 전체 순회가 O(n)입니다.

// LinkedList에서 이렇게 하면 O(n^2)
for (int i = 0; i < linkedList.size(); i++) {
    process(linkedList.get(i)); // 매번 처음부터 탐색
}

// 향상된 for문은 Iterator를 쓰므로 O(n)
for (String item : linkedList) {
    process(item);
}

ArrayList에서는 두 방식의 점근 복잡도가 같지만(둘 다 O(n) 총합), 인덱스 for문은 배열 경계 검사와 메서드 호출 오버헤드가 있고 향상된 for문은 Iterator 객체 생성 비용이 있어 실무에서 체감 차이는 거의 없는 수준입니다. int[] 같은 원시 타입 배열의 경우 JIT가 인덱스 for문을 배열 범위 검사 없이 최적화하기 쉬워 미세하게 유리한 경우가 있지만, 이 차이는 마이크로벤치마크 수준이지 일반적인 애플리케이션 코드에서 체감할 정도는 아닙니다.

해결 방안

1. 컬렉션의 실제 자료구조를 먼저 확인합니다 — ArrayList/LinkedList 여부에 따라 인덱스 접근 비용이 다릅니다.
2. LinkedList를 순회할 때는 절대 인덱스 for문(get(i))을 쓰지 않습니다 — 향상된 for문이나 Iterator를 직접 씁니다.
3. 순회 중 요소를 제거해야 한다면 향상된 for문이 아니라 Iterator.remove()를 써야 합니다 — 향상된 for문에서 컬렉션을 직접 수정하면 ConcurrentModificationException이 발생합니다.
4. 정확한 성능 차이가 실제로 중요한 경로라면 JMH(Java Microbenchmark Harness)로 직접 측정합니다 — 마이크로벤치마크는 JIT 워밍업, 데드코드 제거 등 함정이 많아 System.currentTimeMillis()로 직접 재는 것은 신뢰하기 어렵습니다.

공식 문서

• Oracle Java Docs: LinkedList
• Oracle Java Docs: The for Statement

실제 JDK 버전과 사용 중인 컬렉션 구현체를 확인한 뒤 적용합니다.