JAVA/제네릭(Generic), 컬렉션(Collection Framework)
[컬렉션 프레임워크] ArrayList
jiyoon0000
2025. 4. 2. 16:11
컬렉션 프레임워크
& 시간 복잡도(Big-O)
1. 컬렉션 프레임워크란?
자바에서는 데이터를 효율적으로 관리하기 위해 컬렉션(Collection) 프레임워크라는 도구를 제공한다.
이는 데이터를 저장하고 처리하는 자료구조와 알고리즘을 표준화해 놓은 자바의 라이브러리 집합이다.
* 주요 컬렉션 프레임워크
- List : 순서 O, 중복 O
- ArrayList, LinkedList
- Set : 순서 X, 중복 X
- HashSet, TreeSet
- Map : Key-Value
- HashMap, TreeMap
각 자료구조는 특정 상황에서 성능, 메모리, 기능의 차이를 가지기 때문에 선택의 기준이 중요한데, 이때 고려하는 것이 시간 복잡도(Big-O)이다.
2. 시간 복잡도(Big-O)
* 시간 복잡도 : 프로그래밍에서 알고리즘의 성능을 판단하는 경우, 데이터의 양이 많아졌을 때 알고리즘이 얼마나 빨리 실행되는지를 수학적으로 나타낸 것
* Big-O 표기법
입력 데이터가 커질수록 성능이 어떻게 변하는가를 수학적으로 추상화한 표현
- O(1) : 입력 데이터 크기와 무관한 일정한 시간(상수 시간)
- O(n) : 입력 데이터 크기에 비례해 시간 증가(선형)
- O(log n) : 입력이 커져도 느리게 증가(이진 탐색)
- O(n log n) : 효율적 정렬 알고리즘(퀵 정렬, 병합 정렬)
- O(n²) : 이중 루프 등 반복 횟수가 제곱으로 증가 -> 비효율적
| 표기 | 특징 | 예시 |
| O(1) | 데이터 양과 무관 | 배열의 인덱스로 접근 |
| O(log n) | 절반씩 줄이며 탐색 | 이진 탐색 |
| O(n) | 데이터 수만큼 반복 | 리스트 순회 |
| O(n log n) | 효율적인 정렬 | 퀵 정렬, 병합 정렬 |
| O(n²) | 버블 정렬 | 이중 반복문 |
* 컬렉션 선택 기준 : 시간 복잡도로 판단
| 자료 구조 | 조회 | 삽입 | 삭제 | 특징 |
| Array | O(1) | O(n) | O(n) | 빠르지만 유연성 없음 |
| ArrayList | O(1) | O(n) | O(n) | 배열 기반, 자동 확장 |
| LinkedList | O(n) | O(1) | O(1) | 삽입/삭제 빠름, 조회 느림 |
| HashMap | O(1) | O(1) | O(1) | 키 기반 검색 빠름 |
| TreeMap | O(log n) | O(log n) | O(log n) | 정렬된 키 유지 |
결론 : 시간 복잡도는 코드의 성능을 예측할 수 있는(빨라질 수 있는 이유, 느려질 수 있는 원인) 척도로 자료구조를 선택할 때 Big-O를 고려하면 성능과 유지보수성을 확보할 수 있다
배열
-배열의 구조와 한계
* 배열이란?
자바에서 가장 기본적인 자료구조로 동일한 타입의 데이터를 연속된 메모리 공간에 저장하며, 인덱스를 이용해 빠르게 접근 할 수 있음
- 장점
- 빠른 조회 : 인덱스를 통한 직접 접근 -> O(1)
- 메모리 효율 : 연속된 공간으로 캐시 적중률 높음
- 선언과 사용이 쉬움
- 단점
- 크기 고정 : 선언 시 크기 지정 필요, 이후 변경 불가
- 삽입, 삭제 비효율 : 중간에 요소를 넣거나 삭제하려면 나머지 요소들을 이동시켜야 함 -> O(n)
- 기능 부족 : 동적 크기 증가, 정렬, 삭제 등의 기능은 직접 구현해야 함
* 배열의 특징
- 정적 구조 : 크기가 고정되며, 선언 이후 변경 불가
- 인덱스 기반 접근 : 빠른 위치 접근 가능, O(1)
- 단순한 구조 : 사용법은 직관적이지만 삽입, 삭제, 확장 같은 기능은 제한적
* 배열의 검색 방식
1. 인덱스를 이용한 직접 조회(Direct Access)
- 배열은 순차적 메모리 구조를 가지므로, 인덱스를 통해 즉시 데이터에 접근할 수 있다
- 시간 복잡도는 O(1) -> 매우 빠름
- 인덱스를 알고 있는 경우 가장 빠른 방식의 조회가 가능
int[] arr = {10, 20, 30, 40};
System.out.println(arr[2]); // 30
2. 값을 기준으로 탐색(Linear Search, 검색 연산)
- 배열 내에 특정한 값이 존재하는지 확인하려면 처음부터 끝까지 순차적으로 확인해야하는데 이 과정을 선형 탐색(linear search)이라고 한다
- 시간복잡도는 O(n) -> 데이터 양이 많아질수록 느려지고, 검색 효율이 낮다
- 배열은 위치를 알면 빠르게 접근할 수 있지만, 값 자체를 찾는데는 성능이 떨어진다
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) return i;
}
* 배열의 한계
- 크기 유연성 부족
- 처음에 지정한 크기를 변경할 수 없음
- 더 많은 데이터를 저장하려면 새 배열 생성 후 복사 필요
- 삽입/삭제 비효율
- 중간에 값을 넣거나 삭제할 경우 요소들을 하나씩 밀거나 당겨야 함 -> O(n)
- 기능 부족
- 정렬, 자동 확장, 삭제 등은 직접 구현
- 코드의 복잡도 증가
- 값 검색 시 성능 저하
- 위치는 빠르게 찾을 수 있지만 특정 값을 찾으려면 전체 순회해야 함
- 조회는 빠르지만 검색은 느림
결론 : 배열은 조회는 빠르지만 크기 조절, 삽입, 삭제, 기능 확장 측면에서 한계가 있음
-> 이 단점을 해결하기 위해 ArrayList 사용
ArrayList
1. ArrayList란?
자바에서 제공하는 List 인터페이스의 대표적인 구현체로 배열 기반의 동적 리스트 구조를 가짐
기존 배열의 한계였던 고정 크기 문제, 삽입/삭제의 번거로움, 기능 부족 문제를 보완하여 편리하고 유연한 리스트 구조 제공
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b");
System.out.println(list.get(1)); // b
2. ArrayList의 특징
- 자동 크기 확장 : 요소가 추가되면 내부 배열의 용량을 자동으로 늘림
- 빠른 조회 성능 : 인덱스 접근 -> O(1)
- 삽입/삭제 느림 : 요소 이동(밀거나 당겨야 함) -> O(n)
- 제네릭 지원 : 타입 안전성 확보
- 순서 보장, 중복 허용
- 내부에 Object 배열(Object[])을 사용하므로 기본형은 Wrapper 클래스(참조형)로 사용해야 함(int -> Integer)
* ArrayList 시간 복잡도
| 연산 | 시간 복잡도 | 설명 |
| 조회(get) | O(1) | 배열 기반이라 인덱스로 바로 접근 |
| 탐색(contains) | O(n) | 처음부터 끝까지 확인 |
| 삽입(add) | 평균 O(1), 중간 삽입은 O(n) | 맨 뒤 추가는 빠름 |
| 삭제(remove) | O(n) | 삭제 후 요소 이동 필요 |
get() - O(1) : list.get(3)
add(E) - O(1~n) : list.add("apple")3. ArrayList 내부 구조 및 사용법
* ArrayList 내부 구조
- 새로운 요소가 추가될 때 공간이 부족 할 경우
- 새로운 더 큰 배열 생성(기존의 1.5~2배 크기) 후 기존 데이터를 새로운 배열로 복사
- 초기 용량은 기본적으로 10
// 내부 구조 핵심 코드
Object[] elementData; // 실제 데이터를 담는 배열
int size; // 현재 저장된 요소 개수
* ArrayList 기본 사용법
public class MyArrayListV3Main {
public static void main(String[] args) {
MyArrayListV3 list = new MyArrayListV3();
list.add("a");
list.add("b");
list.add("c");
System.out.println(list);
System.out.println("addLast");
list.add(3, "addLast"); // O(1)
System.out.println(list);
System.out.println("addFirst");
list.add(0,"addFirst"); // O(n)
System.out.println(list);
Object removed1 = list.remove(4);
System.out.println("remove(4)=" + removed1); // remove Last O(1)
System.out.println(list);
Object removed2 = list.remove(0);
System.out.println("remove(0)=" + removed2); // remove First O(n)
System.out.println(list);
}
}
4. ArrayList 주요 기능 및 메서드
| 메서드 | 설명 |
| add(E e) | 요소 추가 |
| add(int index, E e) | 특정 위치에 요소 삽입 |
| get(int index) | 인덱스로 요소 조회 |
| remove(Object o) | 해당 값을 가진 요소 삭제 |
| remove(int index) | 인덱스로 요소 삭제 |
| contains(Object o) | 특정 요소 존재 여부 확인 |
| size() | 요소 수 반환 |
| clear() | 모든 요소 제거 |
| isEmpty() | 리스트가 비어있는지 확인 |
5. 동적 ArrayList
ArrayList는 내부적으로 Object 배열을 사용하는데, 초기에는 크기가 10인 배열을 만들고 공간이 부족하면 더 큰 배열로 자동복사한다.
* 동작 방식
- 요소 추가
- 공간 부족 -> 새 배열 생성(1.5~2배)
- 기존 배열 -> 새 배열로 복사
- 새 배열로 교체 후 추가
package collection.array;
import java.util.Arrays;
public class MyArrayListV3 {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV3() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV3(int initialCapacity) {
elementData = new Object[initialCapacity];
}
public int size() {
return size;
}
public void add(Object e) {
if (size == elementData.length){
grow();
}
elementData[size] = e;
size++;
}
// 코드 추가
public void add(int index, Object e) {
if (size == elementData.length) {
grow();
}
// 데이터 이동
shiftRightFrom(index);
elementData[index] = e;
size++;
}
// 코드 추가, 요소의 마지막부터 index까지 오른쪽으로 밀기
private void shiftRightFrom(int index) {
for (int i = size; i > index ; i--) {
elementData[i] = elementData[i - 1];
}
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
elementData = Arrays.copyOf(elementData,newCapacity);
}
public Object get(int index) {
return elementData[index];
}
public Object set(int index, Object element) {
Object oldValue = get(index);
elementData[index] = element;
return oldValue;
}
// 코드 추가
public Object remove(int index) {
Object oldValue = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
return oldValue;
}
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])){
return i;
}
}
return -1;
}
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) +
" size= " + size + ", capacity= " + elementData.length;
}
}
6. ArrayList에 제네릭 적용
ArrayList는 내부적으로 Object 배열을 사용
- 어떤 타입이든 저장 가능하지만 타입 불안정성 발생
- 데이터를 꺼낼 때 매번 형변환이 필요하고, 잘못된 형 변환시 런타임 오류 발생
- 결론 : 제네릭 사용
* 제네릭 사용 장점
- 타입 안전성 확보 : 잘못된 타입 저장 시 컴파일 오류
- 형변환 불필요 : 코드 간결하고 안전함
- 유지보수 용이, 재사용성 강화
package collection.array;
import java.util.Arrays;
public class MyArrayListV4<E> {
private static final int DEFAULT_CAPACITY = 5;
private Object[] elementData;
private int size = 0;
public MyArrayListV4() {
elementData = new Object[DEFAULT_CAPACITY];
}
public MyArrayListV4(int initialCapacity) {
elementData = new Object[initialCapacity];
}
public int size() {
return size;
}
public void add(E e) {
if (size == elementData.length){
grow();
}
elementData[size] = e;
size++;
}
// 코드 추가
public void add(int index, E e) {
if (size == elementData.length) {
grow();
}
// 데이터 이동
shiftRightFrom(index);
elementData[index] = e;
size++;
}
// 코드 추가, 요소의 마지막부터 index까지 오른쪽으로 밀기
private void shiftRightFrom(int index) {
for (int i = size; i > index ; i--) {
elementData[i] = elementData[i - 1];
}
}
private void grow() {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
elementData = Arrays.copyOf(elementData,newCapacity);
}
@SuppressWarnings("unchecked")
public E get(int index) {
return (E) elementData[index];
}
public E set(int index, E element) {
E oldValue = get(index);
elementData[index] = element;
return oldValue;
}
// 코드 추가
public E remove(int index) {
E oldValue = get(index);
shiftLeftFrom(index);
size--;
elementData[size] = null;
return oldValue;
}
private void shiftLeftFrom(int index) {
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1];
}
}
public int indexOf(E o) {
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])){
return i;
}
}
return -1;
}
public String toString() {
return Arrays.toString(Arrays.copyOf(elementData, size)) +
" size= " + size + ", capacity= " + elementData.length;
}
}
최종 결론 : ArrayList를 언제 사용해야 할까?
- 데이터의 삽입/삭제 빈도가 적고 조회 중심인 경우
- 배열보다 더 유연한 자료구조가 필요할 때
* ArrayList의 한계
1. 중간 삽입/삭제 성능 저하
- 요소를 추가하거나 삭제할 때, 해당 인덱스 이후의 모든 요소를 이동시켜야 함
- 시간 복잡도 : O(n)
- 대용량 데이터 처리 시 LinkedList보다 비효율적일 수 있음
list.add(0, "data"); // 첫 위치 삽입 → 모든 요소 뒤로 이동
list.remove(1); // 중간 삭제 → 뒤 요소 앞으로 이동
2. 초기 공간 낭비 또는 잦은 복사
- 초기 용량은 10으로 고정되어 있고, 용량이 부족해지면 새 배열을 만들고 기존 데이터를 복사하는 비용(cost) 발생
- 요소가 적을 경우, 불필요한 메모리 공간을 차지할 수 있음
3. 기본형을 직접 저장 불가
- 내부적으로 Object[]를 사용 -> int, double 등은 Wrapper 클래스(Integer, Double 등)로 박싱
- 박싱(Boxing)/언박싱(Unboxing)으로 인한 성능 저하 가능성 존재
ArrayList<int> list = new ArrayList<>(); // 오류!
ArrayList<Integer> list = new ArrayList<>(); // 가능
4. 동기화 지원하지 않음(멀티스레드 환경에 부적합)
- ArrayList는 스레드에 안전하지 않음
- 여러 스레드가 동시에 접근할 시 문제 발생 가능성 높음
- 한 스레드가 데이터를 추가할 때, 다른 스레드가 삭제한다면 오류 발생 가능성 높음
- 여러 스레드가 동시에 접근할 시 문제 발생 가능성 높음
- 멀티 스레드 환경에서는 Collections.synchronizedList() 또는 CopyOnWriteArrayList 등 대안 필요
총정리
- ArrayList는 배열 기반의 동적 자료구조로 크기 자동 확장 기능 제공 -> 배열의 한계 보완
- 조회 성능이 뛰어나고 사용법이 단순해 가장 많이 쓰이는 리스트 구조
- 내부는 Object[] 배열로 구성되며, 기본형은 Wrapper 클래스로 변환해서 사용
- 삽입/삭제에는 성능 부담이 있어 조회 중심의 데이터 처리에 적합
- 제네릭을 적용하면 타입 안정성 확보 + 형변환 없이 사용 가능
- 멀티스레드 환경에서는 안전하지 않음
<참고> - 김영한의 실전 자바 중급2편 강의 섹션 4. 컬렉션 프레임워크 ArrayList