ArrayList

배열 리스트 (ArrayList)

ArrayList: 동적 배열 기반의 List 구현체. 내부 배열을 자동으로 확장/축소한다.

---

왜 사용하는가?

기본 배열(int[])은 크기가 고정되어 동적으로 요소를 추가·삭제하기 어렵다. ArrayList는 크기를 자동으로 조절하며, 인덱스 기반 빠른 조회가 필요할 때 최적이다.

어떻게 쓰는가?

List<String> list = new ArrayList<>();

// 추가
list.add("A");        // 마지막에 추가 O(1)
list.add(0, "B");     // 특정 위치에 추가 O(n)

// 조회
String s = list.get(0);   // 인덱스 조회 O(1)

// 삭제
list.remove(0);        // 인덱스로 삭제 O(n)
list.remove("A");      // 값으로 삭제 O(n)

// 크기
int size = list.size();

어디 상황에서 자주 쓰는가?

• 데이터 조회(get)가 잦고, 추가·삭제가 주로 끝(마지막)에 일어나는 경우
• 데이터 순서가 중요한 경우
• 실무에서 List가 필요한 경우의 기본값 (가장 많이 사용됨)

시간 복잡도

연산	위치	시간복잡도
추가	마지막	O(1)
추가	앞 / 중간	O(n)
삭제	마지막	O(1)
삭제	앞 / 중간	O(n)
인덱스 조회	-	O(1)
값 검색	-	O(n)

장점

• 인덱스 기반 O(1) 조회 — 임의 접근이 빠름
• 메모리가 연속 배치 → CPU 캐시 효율 우수
• Java에서 가장 널리 쓰이는 컬렉션, 사용법이 단순

단점

• 앞·중간 추가·삭제 시 O(n) — 요소 이동 발생
• 내부 배열 용량 초과 시 배열 복사(resize) 발생 → 일시적 성능 저하
• 미리 할당된 빈 공간으로 메모리 낭비 가능