[JAVA] 배열(Array) vs ArrayList vs Vector

과거에는 배열(Array), ArrayList, Vector를 기본적인 연속 메모리 기반 자료구조로 많이 비교했지만,
현대 Java에서 주로 사용하는 것은 배열과 ArrayList이고, Vector는 레거시로 간주된다.

 

이 세 가지는 모두 인덱스로 접근이 가능한 연속 메모리 기반 구조라는 공통점을 가지지만,
메모리 할당 방식과 크기 관리, 동기화 여부에서 큰 차이가 있다.

1. 세 가지 자료구조 한눈에 보기

먼저 전체적인 특징을 간단히 정리한다.

 

구분	배열(Array)	ArrayList	Vector
크기	고정	동적	동적
내부 구조	원시 배열	Object[]	Object[]
메모리 위치	힙	힙	힙
인덱스 접근	O(1)	O(1)	O(1)
동기화	없음	없음	있음
권장 여부	제한적	대부분	거의 없음

 

2. 배열(Array)

2.1  개념과 특징

배열은 크기가 고정된 가장 기본적인 자료구조이다.

• 선언 시 크기가 결정된다.
• 크기를 변경할 수 없다.
• Java에서 배열은 항상 힙(Heap)에 할당된다.
• 스택(Stack)에는 배열의 참조값만 저장된다.

int[] arr = new int[5];

Java에는 C/C++과 달리
스택 배열이라는 개념이 존재하지 않는다.
(JIT 최적화로 실제 물리 메모리 배치는 달라질 수 있지만, Java 언어/스펙 관점에서는 배열은 힙 객체라고 보면 된다.)

 

2.2 메모리 구조

스택 영역                힙 영역
┌──────────┐      ┌──────────────────────┐
│ arr ref  ├───→  │ [0][1][2][3][4]       │
└──────────┘      └──────────────────────┘

• 스택에는 arr 참조만 저장된다.
• 실제 데이터는 힙에 연속된 메모리로 저장된다.

 

2.3 시간 복잡도

연산	시간복잡도
접근	O(1)
삽입	O(n)
삭제	O(n)
순회	O(n)

중간 삽입이나 삭제가 느린 이유는
뒤에 있는 모든 요소를 이동시켜야 하기 때문이다.

 

2.4 장단점

장점

• 접근 속도가 매우 빠르다.
• 캐시 지역성이 뛰어나다.
• 메모리 오버헤드가 거의 없다.

단점

• 크기 변경이 불가능하다.
• 크기 예측이 어렵다면 사용하기 불편하다.

 

3. ArrayList

3.1 개념과 특징

ArrayList는 동적으로 크기가 변하는 배열 기반 컬렉션이다.

• Java Collections Framework에 포함된다.
• 내부적으로 Object[] 배열을 사용한다.
• 크기 초과 시 자동으로 확장된다.

ArrayList<Integer> list = new ArrayList<>();

 

 

3.2 내부 구조

스택 영역              힙 영역
┌──────────┐     ┌──────────────────┐
│ list ref ├──→  │ Object[] array   │
└──────────┘     │ capacity = 10    │
                 │ size = 0         │
                 └──────────────────┘

디폴트 생성자로 만든 ArrayList는 논리적인 초기 용량이 10이며,
JDK 8+ 기준 구현체는 실제 배열 할당을 첫 add() 시점까지 미루지만,
개념적으로는 “초기 capacity 10짜리 Object[]를 가진 동적 배열”로 이해해도 된다.

 

3.3 용량 확장 방식

ArrayList는 용량이 가득 차면
기존 용량의 1.5배로 확장한다.

10 → 15 → 22 → 33 → ...

확장 시에는 다음 과정이 발생한다.

1. 더 큰 배열 생성
2. 기존 요소 전체 복사
3. 배열 참조 교체

이 과정에서 O(n) 비용이 발생한다.

 

3.4 Amortized O(1)

add() 메서드는 평균적으로 O(1)이다.

• 대부분의 추가 연산은 O(1)
• 확장 시점에는 O(n)

전체적으로 보면 Amortized O(1)이 된다.

 

3.5 성능 최적화

예상 크기를 알고 있다면
초기 용량을 지정하는 것이 좋다.

ArrayList<Integer> list = new ArrayList<>(100000);

불필요한 재할당과 복사를 방지할 수 있다.

 

3.6 시간 복잡도

연산	시간복잡도
get	O(1)
add	O(1) 평균
add(index)	O(n)
remove	O(n)
contains	O(n)

 

4. Vector

4.1 개념과 특징

Vector는 ArrayList와 유사하지만, 대부분의 public 메서드가 synchronized로 감싸져 있어
개별 메서드 호출 단위에서는 스레드 세이프하다.
다만 “체크 후 동작(check-then-act)” 같은 복합 연산은 여전히 외부 동기화가 필요하다.

Vector<Integer> vector = new Vector<>();

• 멀티스레드 환경에서 개별 메서드 호출 단위에서는 스레드 세이프하다.
• 단일 스레드 환경에서도 불필요한 락 오버헤드가 발생한다.
• 확장 시 기본적으로 2배씩 증가한다(생성자에서 capacityIncrement를 지정해 n씩 증가하게 할 수도 있다).

 

4.2 Vector를 권장하지 않는 이유

1. 불필요한 동기화로 인한 성능 저하
2. 읽기 작업에도 락이 걸림
3. 더 나은 대체재가 존재함

대신 다음 방식을 사용한다.

List<Integer> list = new ArrayList<>();
List<Integer> syncList =
    Collections.synchronizedList(new ArrayList<>());
List<Integer> copyList =
    new CopyOnWriteArrayList<>();

Vector는 레거시 클래스 로 분류된다.
다만 Vector도 그렇고 Collections.synchronizedList도 그렇고,
복합 연산(반복+수정 등) 에서는 외부에서 같은 락으로 감싸야 한다.

 

5. 배열 vs ArrayList vs Vector 비교

항목	배열	ArrayList	Vector
크기	고정	동적	동적
내부 배열	int[] 등	Object[]	Object[]
확장	불가	1.5배	2배
동기화	❌	❌	✅
성능	최고	우수	낮음
권장	제한적	대부분	거의 없음

 

일반적인 단일 스레드 환경에서, 배열 > ArrayList > Vector 순으로 성능이 좋은 편이다.

 

6. 언제 무엇을 선택할까

배열을 사용하는 경우

• 크기가 고정된 경우
• 최고 성능과 메모리 효율이 필요한 경우
  (특히 int, long 같은 primitive 타입을 다룰 때 효과가 크다)

ArrayList를 사용하는 경우

• 대부분의 일반적인 상황
• 크기가 동적으로 변하는 경우
• 컬렉션 API가 필요한 경우

Vector

• 현대 Java에서는 거의 사용하지 않음

 

7. 캐시 지역성과 성능

배열과 ArrayList는 연속 메모리 구조이기 때문에
CPU 캐시 히트율이 매우 높다.

 

특히 ArrayList는 내부적으로 연속된 Object[]에 요소 참조를 저장하기 때문에,
“참조 배열” 관점에서는 캐시 친화적이다.

다만 primitive 배열처럼 실제 데이터까지 완전히 연속적이지는 않을 수 있다.

 

LinkedList는 노드가 메모리 곳곳에 흩어져 있어 캐시 효율이 낮다.

이 때문에 중간 삽입이 많지 않다면 ArrayList가 더 빠른 경우가 많다.

 

8. 핵심 정리

• Java 배열은 힙에 할당된다.
• Array는 언어 차원의 기능이고, List는 컬렉션 프레임워크(인터페이스)다.
• ArrayList는 내부적으로 Object[]를 사용한다.
• ArrayList의 add는 Amortized O(1)이다.
• Vector는 레거시 동기화 컬렉션이다.