Java ArrayList 정리
1. ArrayList란?
ArrayList는 Java에서 가장 많이 사용하는 컬렉션(Collection) 중 하나로, 크기가 자동으로 늘어나고 줄어드는 동적 배열(Dynamic Array) 이다.
일반 배열(Array)은 크기를 한 번 정하면 변경할 수 없지만, ArrayList는 데이터를 추가하거나 삭제할 때 내부적으로 크기를 자동으로 조절해 준다.
예를 들어 일반 배열은 다음과 같이 크기를 미리 지정해야 한다.
int[] arr = new int[5];반면 ArrayList는 크기를 지정하지 않아도 된다.
ArrayList<Integer> list = new ArrayList<>();데이터를 계속 추가하면 내부적으로 더 큰 배열을 생성하고 기존 데이터를 복사하여 저장 공간을 늘려준다.
2. 왜 ArrayList를 사용할까?
예를 들어 회원 정보를 저장한다고 가정해보자.
배열을 사용하면
String[] users = new String[100];100명을 초과하면 더 이상 저장할 수 없다.
하지만 ArrayList는
ArrayList<String> users = new ArrayList<>();회원이 계속 추가되어도 자동으로 크기가 증가한다.
즉, 데이터 개수를 미리 알 수 없는 경우 ArrayList가 매우 유용하다.
3. 선언 방법
정수 저장
ArrayList<Integer> list = new ArrayList<>();문자열 저장
ArrayList<String> list = new ArrayList<>();사용자 객체 저장
ArrayList<User> users = new ArrayList<>();4. 주요 메서드
1) add()
데이터를 추가한다.
ArrayList<String> list = new ArrayList<>();
list.add("Java");
list.add("Spring");
list.add("MySQL");결과
[Java, Spring, MySQL]특정 위치에 추가
list.add(1, "Python");결과
[Java, Python, Spring, MySQL]2) get()
특정 위치의 데이터를 가져온다.
System.out.println(list.get(0));출력
Java3) set()
특정 위치의 데이터를 수정한다.
list.set(1, "JavaScript");결과
[Java, JavaScript, Spring, MySQL]4) remove()
인덱스로 삭제
list.remove(1);값으로 삭제
list.remove("Spring");5) contains()
데이터가 존재하는지 확인한다.
list.contains("Java");결과
true6) size()
저장된 데이터의 개수를 반환한다.
System.out.println(list.size());5. 반복문으로 출력하기
일반 for문
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}향상된 for문
for (String language : list) {
System.out.println(language);
}6. ArrayList의 내부 동작
ArrayList는 내부적으로 배열(Array) 을 사용한다.
예를 들어
list.add("A");
list.add("B");
list.add("C");메모리 구조는 다음과 같다.
Index
0 1 2
+----+----+----+
| A | B | C |
+----+----+----+만약 저장 공간이 모두 찼는데 새로운 데이터를 추가하면
기존 배열
[A][B][C]
↓
더 큰 배열 생성
[A][B][C][ ][ ][ ]새로운 배열을 생성한 뒤 기존 데이터를 복사하고, 마지막에 새로운 데이터를 추가한다.
7. 시간복잡도
| 기능 | 시간복잡도 |
|---|---|
| get() | O(1) |
| set() | O(1) |
| add(맨 뒤) | 평균 O(1) |
| add(중간) | O(N) |
| remove(중간) | O(N) |
| contains() | O(N) |
왜 get()은 O(1)일까?
ArrayList는 내부적으로 배열을 사용한다.
배열은 메모리 공간에 연속적으로 저장되기 때문에 원하는 위치를 바로 계산하여 접근할 수 있다.
list.get(3);처럼 특정 인덱스를 바로 조회할 수 있으므로 시간복잡도는 O(1) 이다.
왜 add(중간)은 O(N)일까?
예를 들어
[10][20][30][40]여기에 15를 두 번째 위치에 삽입하면
[10][15][20][30][40]이 되어야 한다.
이를 위해 기존의
- 20
- 30
- 40
을 한 칸씩 뒤로 이동해야 한다.
데이터를 이동하는 작업이 발생하기 때문에 시간복잡도는 O(N) 이다.
왜 remove(중간)도 O(N)일까?
예를 들어
[10][20][30][40]에서 20을 삭제하면
[10][30][40]가 되어야 한다.
이때 뒤에 있는 데이터들을 모두 앞으로 한 칸씩 이동해야 하므로 역시 O(N) 이다.
8. Array와 ArrayList 비교
| Array | ArrayList |
|---|---|
| 크기 고정 | 크기 자동 증가 |
| 기본 자료형 저장 가능 | 객체 타입 저장(기본형은 오토박싱 사용) |
| length 사용 | size() 사용 |
| 접근 속도 O(1) | 접근 속도 O(1) |
| 삽입·삭제 어려움 | 메서드로 쉽게 처리 가능 |
9. 코딩테스트에서 ArrayList를 사용하는 경우
ArrayList는 다음과 같은 상황에서 자주 사용된다.
- 입력의 개수를 미리 알 수 없는 경우
- 그래프의 인접 리스트 구현
- 결과를 동적으로 저장해야 하는 경우
- BFS, DFS에서 인접 노드 저장
- 데이터를 순차적으로 관리해야 하는 경우
정리
- ArrayList는 크기가 자동으로 조절되는 동적 배열이다.
- 내부적으로 배열을 사용하며 필요할 때 더 큰 배열을 생성해 데이터를 복사한다.
- 조회(get)는 O(1)로 매우 빠르다.
- 중간 삽입(add)과 삭제(remove)는 데이터 이동이 발생하므로 O(N)이다.
- Java 실무와 코딩테스트에서 가장 많이 사용하는 컬렉션 중 하나이므로 반드시 익혀두는 것이 좋다.
