실무에서 “List” 라고 하면 대부분 ArrayList를 의미하며, List 인터페이스의 대표 구현체로 배열의 속도와 List의 편의성을 섞은 구조입니다.
하지만 내부는 결국 배열이므로, shift와 resize 비용을 이해해야 한다.”
내부 구조는 결국 배열이기 때문에 인덱스 접근(get/set)이 매우 빠르고, 순회 성능도 좋은 편입니다.
대신 “배열의 한계”도 그대로 가집니다. 특히 중간 삽입/삭제가 많으면 요소 이동(shift)이 발생해 비용이 커질 수 있습니다.
ArrayList는 내부 배열에 연속적으로 저장되므로 CPU 캐시에 유리합니다. 그래서 반복문으로 훑는 작업(검색/필터/매핑)이 빠르게 동작합니다.
반면, 리스트 중간에 요소를 넣거나 빼면 뒤쪽 요소들을 한 칸씩 움직여야 하므로 중간 삽입/삭제는 O(n)입니다.
💡 TIP
“ArrayList가 빠르다”는 건 보통 get/set/순회가 빠르다는 뜻입니다.
삽입/삭제가 많은 워크로드라면, 자료구조보다 먼저 데이터 접근 패턴을 다시 봐야 합니다.
ArrayList는 내부 배열이 가득 차면 자동으로 용량을 늘립니다. 이때는 새 배열을 만들고 기존 요소를 통째로 복사하기 때문에 그 순간만큼은 O(n)이 됩니다.
하지만 resize는 매번 발생하지 않도록 설계되어 있어, 전체적으로는 add가 평균 O(1)으로 동작합니다(Amortized O(1)).
💡 TIP / 참고사항
원소 수가 대략 예측 가능하면, 초기 용량(capacity)을 지정해 resize 횟수를 줄일 수 있습니다.
예: new ArrayList<>(1000) 처럼 미리 크게 잡아두면 대량 add에서 성능이 안정됩니다.
import java.util.*;
public class Example {
public static void main(String[] args) {
// 1) 기본 생성 (처음 capacity는 내부적으로 관리됨)
List<String> names = new ArrayList<>();
// 2) 끝에 추가 (평균 O(1))
names.add("A");
names.add("B");
names.add("C");
// 3) 인덱스 접근 O(1)
String second = names.get(1);// "B"
// 4) 순회 (캐시 친화적이라 빠른 편)
for (String n : names) {
System.out.println(n);
}
// 5) 중간 삽입/삭제는 shift 발생 (주의)
names.add(1, "X"); // [A, X, B, C]
names.remove(2); // [A, X, C]
}
}👍 GOOD
- 인덱스 기반 처리(정렬/DP/투포인터)가 필요할 때
- 데이터를 자주 읽고(조회), 순회가 많을 때
- append 중심(끝 추가)으로 데이터가 쌓일 때
👎 BAD
- 앞/중간 삽입·삭제가 매우 잦은 워크로드
- 크기 변동이 크고 resize 비용이 민감한 경우 (대량 add 반복)
- 동시성 환경에서 동기화 없이 공유 List로 쓰는 경우
💡 TIP / 참고사항
멀티스레드 환경에서 ArrayList를 공유하면 안전하지 않습니다.
필요하다면 Collections.synchronizedList(), CopyOnWriteArrayList 같은 대안을 고려해야 합니다(상황에 따라 비용이 큼).
✅ 핵심 요약
- ✔️ ArrayList는 동적 배열 기반 List로, get/set/순회가 빠르다.
- ✔️ 끝 삽입은 평균 O(1)이지만, resize 시 배열 복사 O(n)이 순간적으로 발생한다.
- ✔️ 중간 삽입/삭제는 shift 때문에 O(n)이라, 워크로드 패턴에 맞춰 선택해야 한다.