[Data Structure] 배열(Array)

배열은 데이터 구조 중 가장 기본적이면서도 성능·메모리 모델의 핵심을 드러내는 구조입니다. 이 글은 Java를 기준으로 배열의 내부 원리(연속 저장, 주소 산술), 동적 배열(ArrayList)의 리사이즈 동작, 그리고 실무에서의 선택 전략(SoA 리팩터링, ArrayDeque, BitSet)을 깊이 있게 설명합니다.

토론 요약

연속 저장 + 고정 크기 요소일 때 인덱스 접근은 O(1)이며 상수 계수가 작습니다.
Java 원시 타입 배열(int[], double[])은 값이 연속 저장되어 캐시 지역성·선형 스캔 성능이 매우 좋습니다.
객체 배열(Object[], SomeClass[])은 “참조의 연속 저장”이므로 실제 객체는 힙 곳곳에 흩어져 간접 참조 비용과 캐시 미스가 증가합니다.
ArrayList는 내부적으로 배열을 사용하며, 용량 초과 시 새 배열 할당 + System.arraycopy로 복사합니다. 배치 삽입 전 ensureCapacity로 비용을 줄일 수 있습니다.
양끝 삽입/삭제는 ArrayDeque가 일반적으로 LinkedList보다 실제 성능이 좋습니다.
컬럼형(필드별) 처리에는 SoA(Struct of Arrays) 레이아웃과 BitSet 같은 전용 구조가 효과적입니다.

심화 설명

왜 배열 인덱스 접근이 O(1)인가

연속 메모리 블록에서 i번째 요소의 주소는 아래의 주소 산술로 한 번에 계산됩니다.

flowchart LR A[base 주소] -- + i × element_size --> B[요소 i의 주소]

CPU는 정수 덧셈/곱셈으로 주소를 계산하고, 이론적 RAM 모델에서는 메모리 접근을 상수 비용으로 간주합니다. 실제로는 캐시·TLB·페이지 폴트의 영향이 있으나, 알고리즘 복잡도는 데이터 크기와 무관한 상수로 모델링합니다.

참고: Java는 배열의 복잡도를 명시적으로 서술하지 않지만, C++ 표준 컨테이너(std::vector) 문서가 연속 저장과 랜덤 접근 O(1)을 공식화합니다. Java에서도 원시 배열은 같은 원리에 의해 상수 시간 접근으로 이해합니다.

배열 메모리 구조도

원시 타입 배열과 객체 배열의 메모리 레이아웃은 근본적으로 다릅니다.

원시 타입 배열: int[] arr = {10, 20, 30};

graph TB subgraph Stack["Stack"] direction LR ARR["arr
(참조)"] end subgraph Heap["Heap Memory - 연속 저장"] direction LR H1["0x1000
10"] H2["0x1004
20"] H3["0x1008
30"] end ARR -->|가리킴| H1 H1 -->|연속| H2 H2 -->|연속| H3 style H1 fill:#2D5016,stroke:#fff,color:#fff style H2 fill:#2D5016,stroke:#fff,color:#fff style H3 fill:#2D5016,stroke:#fff,color:#fff

배열의 모든 요소가 메모리상 인접하게 저장
배열[i] 주소 = base(0x1000) + i × 4(int 크기)
첫 요소 접근 시 캐시 라인에 인접 요소들도 로드 → 캐시 히트 확률 높음

객체 배열: Item[] items = {new Item(), new Item()};

graph TB subgraph Stack["Stack"] direction LR ITEMS["items
(참조)"] end subgraph Heap["Heap Memory - 참조만 연속, 객체는 분산"] direction TB subgraph Refs["참조 배열
(연속 저장)"] R1["0x2000
Ref1→0x5100"] R2["0x2008
Ref2→0x8A00"] R3["0x2010
Ref3→0x3500"] end subgraph Obj["실제 객체
(분산 저장)"] O1["0x5100
Item1
id,price,ts"] O2["0x8A00
Item2
id,price,ts"] O3["0x3500
Item3
id,price,ts"] end end ITEMS -->|가리킴| R1 R1 -->|참조| O1 R2 -->|참조| O2 R3 -->|참조| O3 style R1 fill:#1E3A5F,stroke:#fff,color:#fff style R2 fill:#1E3A5F,stroke:#fff,color:#fff style R3 fill:#1E3A5F,stroke:#fff,color:#fff style O1 fill:#5D1A3A,stroke:#fff,color:#fff style O2 fill:#5D1A3A,stroke:#fff,color:#fff style O3 fill:#5D1A3A,stroke:#fff,color:#fff

배열에는 참조만 연속 저장
실제 객체는 힙의 여러 곳에 분산 저장
각 요소 접근마다 다른 메모리 영역으로 점프 → 캐시 미스 증가
간접 참조 비용 추가

ArrayList의 내부 구조

graph TB subgraph Stack["Stack"] AL["list
(참조)"] end subgraph Heap["Heap Memory"] subgraph ALObj["ArrayList 객체"] SIZE["size: 3"] CAP["capacity: 10"] ARRAY["elementData
(Object[] 참조)"] end subgraph MEM["elementData 배열
(인덱스 기반 접근)"] direction LR E0["[0]
Object Ref"] E1["[1]
Object Ref"] E2["[2]
Object Ref"] E3["[3]
null"] E4["[4]
null"] end end AL -->|가리킴| ALObj ARRAY -->|가리킴| E0 E0 -->|메모리상
인접| E1 E1 -->|메모리상
인접| E2 style SIZE fill:#3D5A30,stroke:#fff,color:#fff style CAP fill:#3D5A30,stroke:#fff,color:#fff style ARRAY fill:#3D5A30,stroke:#fff,color:#fff style E0 fill:#1E3A5F,stroke:#fff,color:#fff style E1 fill:#1E3A5F,stroke:#fff,color:#fff style E2 fill:#1E3A5F,stroke:#fff,color:#fff style E3 fill:#4A4A4A,stroke:#fff,color:#fff

ArrayList는 내부적으로 Object[] 배열 사용 (링크드 리스트 아님!)
size: 실제 요소 개수
capacity: 할당된 배열 크기 (size > capacity 시 자동 확장)
접근 방식: elementData[i] - 인덱스 기반 직접 접근 (O(1))
요소들 사이의 포인터/링크 없음 - 배열이므로 연속 메모리의 인덱스로 접근

Java에서 연속 저장 가정이 깨지는 경우

원시 타입 배열: 값이 연속 저장됨 → 캐시 친화적, 선형 스캔 우수.
객체 배열(Object[], SomeClass[]): 배열에는 “참조”만 연속 저장되고, 실제 객체는 힙에 흩어져 있음 → 간접 참조로 상수 계수 증가, 캐시 미스도 증가.
불리언 대량 처리: boolean[] 대신 BitSet을 사용하면 비트 패킹과 집합/비트 연산이 효율적.

캐시 미스(Cache Miss)란?

캐시 미스는 CPU가 필요한 데이터를 L1/L2 캐시에서 찾지 못하고, 더 느린 메인 메모리(RAM)로부터 가져와야 할 때 발생하는 현상입니다.

왜 캐시 미스가 중요한가? CPU는 데이터에 접근할 때 다음과 같은 계층을 거칩니다:

L1 캐시: ~4 사이클 (약 1-2 나노초)
L2 캐시: ~10-20 사이클
L3 캐시: ~40-75 사이클
메인 메모리: ~200-300 사이클 (약 50-100 나노초)

캐시 미스 1회가 발생하면 수십 배의 성능 저하가 일어납니다. 예를 들어, 1 나노초 작업 100개를 할 수 있는 시간에 메모리 접근 1회가 드는 것입니다.

객체 배열에서 캐시 미스가 증가하는 이유

원시 배열 예시: int[] nums = {1, 2, 3, 4, ...};

메모리 레이아웃:
[주소: 1000] [1][2][3][4][5]...
         연속 저장됨

CPU가 nums[0]을 접근하면 인접한 nums[1], nums[2] 등도 같은 캐시 라인에 로드됩니다. 다음 반복에서 nums[1] 접근은 이미 캐시에 있으므로 캐시 히트(Hit)입니다.

객체 배열 예시: Item[] items = {new Item(), new Item(), ...};

배열 레이아웃 (참조들만 연속):
[주소: 1000] [Ref1][Ref2][Ref3]...

실제 객체 위치 (힙에 흩어짐):
[주소: 5000] Item1 데이터
[주소: 8500] Item2 데이터
[주소: 3200] Item3 데이터  ← 캐시 미스!

배열은 연속이지만, 각 참조가 가리키는 실제 객체가 메모리 여기저기에 흩어져 있습니다. 루프에서 items[i].price 접근 시마다 새로운 메모리 주소로 점프하므로, 캐시가 도움이 되지 않습니다.

성능 측정 예시

// AoS (Array of Structs) - 캐시 미스 많음
class Item {
    int id;
    double price;
    long ts;
}
Item[] items = new Item[1000000];
for (int i = 0; i < items.length; i++) {
    items[i] = new Item(i, Math.random() * 1000, System.nanoTime());
}

// 가격 합계 계산 - 캐시 미스 빈번
double sum = 0;
long start = System.nanoTime();
for (int i = 0; i < items.length; i++) {
    sum += items[i].price;  // 매번 객체 참조 → 캐시 미스 가능성
}
System.out.println("AoS time: " + (System.nanoTime() - start) / 1e6 + " ms");

// SoA (Struct of Arrays) - 캐시 미스 적음
int[] ids = new int[1000000];
double[] prices = new double[1000000];
long[] ts = new long[1000000];

// 값 채우기
for (int i = 0; i < 1000000; i++) {
    ids[i] = i;
    prices[i] = Math.random() * 1000;
    ts[i] = System.nanoTime();
}

// 가격 합계 - 메모리 접근이 규칙적
sum = 0;
start = System.nanoTime();
for (int i = 0; i < prices.length; i++) {
    sum += prices[i];  // 항상 연속 메모리 접근 → 캐시 히트 높음
}
System.out.println("SoA time: " + (System.nanoTime() - start) / 1e6 + " ms");

실제 벤치마크 결과 (ArrayPerformance 기반, 100만 요소):

유형	소요시간	ns/elem	상대성능
원시 배열 (`int[]`)	0.24 ms	0.24 ns	1배 (기준)
SoA (필드별 원시 배열)	1.26 ms	1.26 ns	5.25배 느림
객체 배열 AoS (`Item[]`)	1.67 ms	1.67 ns	6.96배 느림

분석:

원시 배열: 메모리상 값이 연속 저장되어 캐시 라인에 여러 요소 로드 → 최고 성능
SoA: 각 필드가 별도 배열이므로 여러 배열 접근 필요 → 상수 계수 증가
AoS: 객체 참조는 연속이나 실제 데이터는 힙 곳곳 분산 → 캐시 미스 빈번

결론: 배열의 “O(1) 접근”은 주소 계산 측면의 복잡도일 뿐, 실제 성능은 캐시 지역성(Spatial & Temporal Locality)에 크게 영향을 받습니다. 원시 값 배열은 자동으로 데이터 지역성이 좋지만, 객체 배열은 간접 참조로 인해 캐시 미스가 급증할 수 있습니다.

동적 배열 `ArrayList`의 리사이즈

내부 배열 용량이 초과되면 더 큰 배열을 할당하고 기존 요소를 System.arraycopy로 복사합니다(그 이벤트 비용 O(n)). 평소 add는 상각 O(1)이지만, 리사이즈 이벤트 비용을 무시할 수 없습니다.

벤치마크 결과 (ArrayListResizingBenchmark 기반, 100만 요소):

전략	소요시간	상대성능	설명
용량 미할당 (`new ArrayList<>()`)	46.77 ms	1배 (기준)	동적 리사이즈 반복 → 메모리 할당/복사 오버헤드 누적
`ensureCapacity` 사용	18.71 ms	2.50배 빠름	사전 확보로 리사이즈 이벤트 최소화
생성자 용량 설정 (`new ArrayList<>(1000000)`)	11.46 ms	4.08배 빠름	미리 할당 → 리사이즈 0회 → 최고 성능

권장사항:

예상 크기를 알 경우: 생성자로 용량 지정 (new ArrayList<>(expectedSize)) - 4배 성능 이득
예상 크기 불명확: ensureCapacity(N) 호출 후 배치 삽입 - 2.5배 성능 이득
배치 삽입 없는 점진적 추가: 용량 미할당도 상각 성능이 충분할 수 있음

LinkedList vs ArrayList vs ArrayDeque

각 구현의 시간 복잡도는 같아 보이지만, 상수 계수와 캐시 성능에서 큰 차이가 있습니다.

벤치마크 결과 (ListPerformanceBenchmark 기반, 10만 요소 × 1만 회 연산):

Head 삽입 (index 0에 삽입)

구현	소요시간	상대성능	복잡도
ArrayList	157.52 ms	1배 (기준)	O(n) - 배열 시프팅
ArrayDeque	3.54 ms	44.5배 빠름	O(1) - 원형 버퍼
LinkedList	1.78 ms	88.5배 빠름	O(1) - 포인터 갱신

양끝 큐 연산 (Queue 패턴)

구현	소요시간	상대성능
ArrayDeque	2.62 ms	1배 (최고)
LinkedList	5.58 ms	2.13배 느림

분석: Deque 패턴에서 ArrayDeque가 LinkedList보다 2배 빠릅니다. 원형 버퍼의 캐시 친화성 vs LinkedList의 메모리 간접 참조.

랜덤 접근 (get by index)

구현	소요시간	상대성능
ArrayList	1.21 ms	1배 (최고)
LinkedList	612.64 ms	505배 느림

중간 삽입 (random position)

구현	소요시간	상대성능
ArrayList	96.34 ms	1배
LinkedList	1145.14 ms	11.89배 느림

순회 반복 (iteration)

구현	소요시간	상대성능
ArrayList	5.40 ms	1배 (최고)
LinkedList	29.85 ms	5.53배 느림

종합 권장사항:

사용 패턴	추천	이유
랜덤 접근 주도	ArrayList	500배 이상 빠름
양끝 큐/덱 연산	ArrayDeque	LinkedList보다 2배 빠르고 메모리 효율도 우수
첫 위치만 지속 삽입	LinkedList	O(1)이나 임의 위치 섞이면 비추천
중간 삽입/삭제 빈번	알고리즘 재설계	표준 List로는 O(n) 피불가능

주의: 이론상 복잡도(Big-O)와 실제 성능(상수 계수 + 캐시)은 다릅니다. LinkedList는 O(1) 연산이지만 메모리 간접 참조로 배열보다 느릴 수 있습니다.

SoA(Struct of Arrays) 리팩터링

AoS(Array of Structs: 객체 배열) 대신 각 필드를 별도의 원시 배열로 분리하여 컬럼형 처리 성능을 극대화합니다.

AoS (Array of Structs) - 캐시 미스 많음

class Item {
    int id;
    double price;
    long ts;
}
Item[] items = new Item[1000000];
// 초기화...

// 특정 필드만 접근
double sum = 0;
long start = System.nanoTime();
for (int i = 0; i < items.length; i++) {
    sum += items[i].price;  // 매번 객체 참조 → 캐시 미스 가능
}
System.out.printf("AoS time: %.2f ms (%.2f ns/elem)\n", 
    (System.nanoTime() - start) / 1e6, 
    (double)(System.nanoTime() - start) / items.length);

SoA (Struct of Arrays) - 캐시 히트 높음

class StructOfArrays {
    int[] ids;
    double[] prices;
    long[] timestamps;
}

StructOfArrays data = new StructOfArrays(1000000);
// 초기화...

double sum = 0;
long start = System.nanoTime();
for (int i = 0; i < data.prices.length; i++) {
    sum += data.prices[i];  // 연속 메모리 직접 접근 → 캐시 히트
}
System.out.printf("SoA time: %.2f ms (%.2f ns/elem)\n", 
    (System.nanoTime() - start) / 1e6, 
    (double)(System.nanoTime() - start) / data.prices.length);

성능 비교 (100만 요소 기준):

방식	소요시간	ns/elem	상대성능
AoS (Item[])	1.67 ms	1.67 ns	1배 (기준)
SoA (필드별 배열)	1.26 ms	1.26 ns	1.33배 빠름

분석:

AoS: 객체 참조 로드 → 실제 객체(힙) 접근 → 필드 오프셋 계산 → 값 로드 (다단계 메모리 접근, 캐시 미스 빈번)
SoA: 배열 인덱스 → 즉시 값 로드 (직접 접근, 캐시 히트)
100만 요소 기준 약 410μs 절감 (루프 내 누적되면 병목 제거)

언제 SoA를 사용할 것인가?

특정 필드만 반복 접근하는 컬럼형 처리
대용량 데이터에서 필드 서브셋만 집계/필터링
캐시 성능이 중요한 고성능 코드

주의사항:

멀티 필드 접근이 자주 필요하면 AoS가 더 나을 수 있음
SoA는 구현이 복잡해짐 (필드별 배열 관리)
메모리 이점: SoA는 필드별 배열을 선택적 로드 가능 (스토리지 효율)

실무 적용 예제

배치 삽입 전 용량 예약

// 예상 원소 수가 있을 때
List<Integer> list = new ArrayList<>(100_000);
// 또는
list.ensureCapacity(100_000);
for (int i = 0; i < 100_000; i++) list.add(i);

덱 패턴 처리

Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1);
dq.addLast(2);
dq.removeFirst();
dq.removeLast();

결론/팁

읽기 중심·랜덤 접근: ArrayList + ensureCapacity.
양끝 삽입/삭제: ArrayDeque.
첫 위치만 지속 삽입/삭제: LinkedList(임의 위치가 섞이면 비추천).
컬럼형 처리: SoA(필드별 원시 배열) + 필요 시 BitSet.
중간 삽입/삭제가 매우 빈번하고 대용량: 표준 리스트로는 근본적으로 O(n). 문제 재정의(덱), 특화 구조(트리/스킵 리스트/갭 버퍼) 고려.

참고 문서(공식)

Java SE 공식 문서 인덱스
ArrayList API(ensureCapacity)
ArrayDeque API
LinkedList API
BitSet API
JLS Arrays(배열 타입/개념)

이 글은 Java 공식 문서를 참고했으며, 복잡도 표기는 전산학 표준 모델(연속 저장 + 주소 산술)에 기반한 설명입니다. 추가 실측은 워크로드 특성에 따라 마이크로벤치로 검증하시길 권합니다.

자신만의 철학을 만들어가는 중입니다.

최상단으로 이동했습니다!

Twitter Facebook LinkedIn

[Data Structure] 배열(Array)

카테고리

토론 요약

심화 설명

왜 배열 인덱스 접근이 O(1)인가

배열 메모리 구조도

Java에서 연속 저장 가정이 깨지는 경우

캐시 미스(Cache Miss)란?

동적 배열 `ArrayList`의 리사이즈

LinkedList vs ArrayList vs ArrayDeque

Head 삽입 (index 0에 삽입)

양끝 큐 연산 (Queue 패턴)

랜덤 접근 (get by index)

중간 삽입 (random position)

순회 반복 (iteration)

SoA(Struct of Arrays) 리팩터링

실무 적용 예제

배치 삽입 전 용량 예약

덱 패턴 처리

결론/팁

참고 문서(공식)

JLS Arrays(배열 타입/개념)

공유하기

댓글남기기

다른 포스트

[Java] Assert로 프로그래머의 실수를 잡아내기

[Spring] Spring Batch 병렬 처리로 배치 시간 7배 단축하기

[Reference] Windows 명령 프롬프트(CMD) 명령어 정리

[Spring] Spring Batch 입문자를 위한 핵심 개념 완벽 이해

[Data Structure] 배열(Array)

카테고리

토론 요약

심화 설명

왜 배열 인덱스 접근이 O(1)인가

배열 메모리 구조도

Java에서 연속 저장 가정이 깨지는 경우

캐시 미스(Cache Miss)란?

동적 배열 ArrayList의 리사이즈

LinkedList vs ArrayList vs ArrayDeque

Head 삽입 (index 0에 삽입)

양끝 큐 연산 (Queue 패턴)

랜덤 접근 (get by index)

중간 삽입 (random position)

순회 반복 (iteration)

SoA(Struct of Arrays) 리팩터링

실무 적용 예제

배치 삽입 전 용량 예약

덱 패턴 처리

결론/팁

참고 문서(공식)

JLS Arrays(배열 타입/개념)

공유하기

댓글남기기

다른 포스트

[Java] Assert로 프로그래머의 실수를 잡아내기

[Spring] Spring Batch 병렬 처리로 배치 시간 7배 단축하기

[Reference] Windows 명령 프롬프트(CMD) 명령어 정리

[Spring] Spring Batch 입문자를 위한 핵심 개념 완벽 이해

목차

동적 배열 `ArrayList`의 리사이즈