배열

배열이란 무엇인가?

배열(Array)은 동일한 자료형의 데이터를 연속된 메모리 공간에 저장하는 자료구조입니다.
각 원소는 인덱스(index) 로 구분되며 대부분의 언어에서는 0부터 시작합니다.

즉 배열은 연속된 메모리 덩어리 속에 데이터를 가지런히 놓고 arr[i] 라는 표현만으로 곧바로 특정 원소를 O(1) 시간에 접근할 수 있게 해주는 구조입니다.

 

int[] numbers = {10, 20, 30, 40}; System.out.println(numbers[2]); // 30 출력 (O(1))

---

 

배열의 핵심 개념 – “연속된 메모리”

배열이 빠른 이유는  데이터가 메모리에 연속적으로 저장되기 때문입니다.
컴퓨터는 배열의 첫 번째 주소(base address)만 알면
arr[i] = base_address + (i * element_size) 로 원하는 위치를 즉시 계산할 수 있습니다.

이 덕분에 배열은 랜덤 접근(Random Access) 이 가능하며 CPU 캐시(Cache Locality)와도 매우 친화적이라 순차 반복 시 특히 빠른 성능을 보입니다.

---

배열은 언제 쓰면 좋은가?

데이터 개수가 명확하고 변동이 적을 때	메모리 낭비 없이 효율적
인덱스 기반 접근이 많을 때	O(1) 즉시 접근
데이터를 순차적으로 읽을 때	캐시 지역성 극대화
정렬 및 이분 탐색이 필요할 때	메모리 연속성 덕분에 빠른 탐색 가능

반대로, 중간 삽입/삭제가 잦은 경우에는 배열이 비효율적입니다.
그럴 땐 연결 리스트(LinkedList) 나 Deque 같은 구조가 더 적합합니다.

추후에  연결 리스트(LinkedList) 와 Deque  구조도 정리할 예정입니다.

 

---

시간복잡도 정리

인덱스 접근	O(1)	주소 계산으로 즉시 접근
맨 뒤 추가 (append)	O(1) (평균)	가끔 리사이즈 시 O(n)
중간 삽입/삭제	O(n)	나머지 요소 이동 필요
맨 앞 삽입/삭제	O(n)	모든 요소 이동 발생
탐색	O(n)	순차 비교 필요
정렬	O(n log n)	알고리즘에 따라 다름

동적 배열(Dynamic Array)은 리사이즈 시 한 번의 O(n) 복사가 있지만 평균적으로는 amortized O(1) 이 보장됩니다.
(대표적인 예: Java의 ArrayList, Python의 list)

---

 정적 배열 vs 동적 배열

크기 변경	불가능	자동 확장/축소 가능
메모리 할당	고정 크기	필요 시 재할당
대표 예시	C의 int a[100]	Java의 ArrayList, Python의 list
복사 비용	없음	리사이즈 시 O(n) 복사 발생
활용	크기가 명확한 데이터	변동성 있는 데이터

---

배열의 장점

1. 빠른 임의 접근 (O(1))
   • 인덱스 계산만으로 즉시 원소에 접근 가능
2. 캐시 효율성 우수
   • 연속 메모리 덕분에 순차 순회 시 CPU 캐시 적중률이 높음
3. 구현 단순
   • 자료구조 중 가장 단순하고 메모리 오버헤드가 적음
4. 정렬·탐색 알고리즘과 궁합이 좋음
   • 정렬된 배열에서의 이분 탐색(binary search)은 고전적 조합

---

배열의 단점

1. 중간 삽입/삭제 비용이 큼 (O(n))
   • 중간에 데이터를 삽입하면 그 뒤에 데이터들을 뒤로 한칸씩 이동해야 함
2. 크기 변경이 어려움
   • 정적 배열은 고정 크기, 동적 배열은 리사이즈 시 복사 비용 발생
3. 큰 연속 메모리 필요
   • 너무 큰 배열은 할당 실패나 단편화 이슈 발생 가능
4. 삽입/삭제가 잦은 구조엔 부적합
   • 연결 리스트나 트리를 사용하는 게 효율적

---

 언어별 배열 비교

C	정적 배열 기본, 메모리 직접 관리	빠르지만 유연성 부족
Java	int[] + ArrayList 로 구분	동적 배열은 내부적으로 Object[]
Python	list 자체가 동적 배열	자동 확장, 매우 유연
JavaScript	Array 는 사실상 해시 기반 리스트	크기 가변, 자료형 자유

 

---

 배열과 다른 자료구조 비교

목적추천 자료구조이유

빠른 인덱스 접근	배열	O(1) 접근
삽입/삭제 잦음	연결 리스트	O(1) 삽입/삭제
양 끝 조작	덱(Deque)	O(1) 양끝 조작
키-값 탐색	해시맵(Map)	평균 O(1) 탐색
정렬 기반 탐색	배열	이분 탐색 가능

---

 배열의 성능을 극대화하는 팁

1. 예상 크기가 있다면 미리 capacity 지정→ 리사이즈 빈도를 줄여 성능 안정화

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

→ 리사이즈 빈도를 줄여 성능 안정화

 

 2.중간 삽입을 최소화하고, 가능하면 배치 처리

• 예: 대량 데이터는 모아서 한 번에 삽입

3.행 우선 순회(Row-major order)

• 다차원 배열 순회 시 캐시 효율 극대화

 

---

정리

정의	연속된 메모리 공간에 동일 타입 데이터를 저장
강점	빠른 접근(O(1)), 단순 구조, 캐시 효율
약점	삽입/삭제 O(n), 리사이즈 오버헤드
적합한 상황	읽기 위주, 인덱스 접근 위주, 크기 예측 가능
부적합한 상황	중간 조작이 잦거나 실시간 시스템

---

 마무리

배열은 가장 기본적이지만 가장 중요한 자료구조입니다.
리스트, 큐, 스택, 힙, 그래프 구조 대부분이 결국 배열을 기반으로 구현됩니다.

배열을 단순히 “값을 여러 개 담는 구조”로 이해하기보다 “연속된 메모리 + 인덱스 접근의 힘”으로 이해하면
모든 자료구조의 설계 원리를 한 단계 깊이 있게 바라볼 수 있습니다.