동적 배열은 데이터의 삽입·삭제에 따라 크기를 동적으로 조절할 수 있는 일차원 자료구조이며, 연속된 메모리 공간에 요소를 저장한다. 일반적인 정적 배열과 달리 프로그램 실행 중에 필요에 따라 메모리를 재할당하여 크기가 증가하거나 감소한다.
정의
동적 배열(또는 가변 배열)은 연속된 메모리 블록에 데이터를 저장하면서, 삽입·삭제 연산이 발생할 경우 내부적으로 버퍼 크기(reserve capacity) 를 재조정한다. 이 과정에서 기존 요소를 새로운 메모리 위치로 복사하고, 이전 메모리는 해제한다.
구조 및 동작 원리
| 구성 요소 | 설명 |
|---|---|
| 버퍼 (capacity) | 현재 할당된 메모리 블록의 전체 크기(요소 수). |
| 크기 (size) | 실제로 저장된 요소의 수. |
| 포인터 (data) | 첫 번째 요소를 가리키는 메모리 주소. |
| 재할당 정책 | 보통 2배 증가(exponential growth) 혹은 일정 비율 증가 방식이 사용되며, 이는 삽입 연산의 평균 시간 복잡도를 O(1) 로 유지한다. |
주요 연산 및 시간 복잡도
| 연산 | 평균 시간 복잡도 | 최악 시간 복잡도 | 비고 |
|---|---|---|---|
| 요소 접근 (인덱스 연산) | O(1) | O(1) | 연속 메모리 특성 |
| 뒤쪽 삽입 (push_back) | O(1) (amortized) | O(n) (재할당 시) | 재할당이 일어나면 전체 복사 |
| 중간 삽입·삭제 | O(n) | O(n) | 요소 이동 필요 |
| 버퍼 크기 조회 | O(1) | O(1) | |
| 버퍼 예약 (reserve) | O(n) (재할당 시) | O(n) | 미리 용량을 확보 |
구현 사례
- C++:
std::vector<T> - Java:
java.util.ArrayList<E> - C#:
System.Collections.Generic.List<T> - Python: 내부적으로
list가 동적 배열 방식으로 구현됨.
각 구현은 언어마다 메모리 관리와 재할당 정책이 다소 차이나지만, 기본 원리는 동일하다.
장점
- 인덱스 기반 O(1) 접근이 가능하여 검색·읽기 연산이 빠름.
- 연속 메모리이므로 캐시 친화적이며, 메모리 사용 효율이 높다.
- 앰ORTIZED O(1) 삽입(뒤쪽) 성능을 제공한다.
단점
- 중간 삽입·삭제 시 O(n) 의 비용이 발생한다.
- 재할당 시 전체 복사가 필요해 일시적인 성능 저하와 메모리 파편화 위험이 있다.
- 예측 불가능한 메모리 사용량(버퍼 과잉 할당) 때문에 메모리 제한이 엄격한 환경에 부적합할 수 있다.
사용 예시 (C++)
#include <vector>
#include <iostream>
int main() {
std::vector<int> v; // 빈 동적 배열 생성
v.reserve(10); // 미리 10개의 용량 확보
for (int i = 0; i < 15; ++i) // 자동 재할당 발생
v.push_back(i); // 뒤쪽 삽입
std::cout << "size = " << v.size()
<< ", capacity = " << v.capacity() << '
';
std::cout << "v[5] = " << v[5] << '
';
}
관련 개념
- 정적 배열 – 크기가 고정된 배열, 메모리 재할당이 불가능.
- 링크드 리스트 – 삽입·삭제가 O(1)이나 인덱스 접근이 O(n).
- 해시 테이블 – 키-값 매핑을 제공, 내부적으로 동적 배열을 사용하기도 함.
- 스택·큐 – 특정 접근 방식에 최적화된 추상 자료구조, 구현에 동적 배열을 활용할 수 있다.
참고문헌
1. C++ Standard Library, std::vector – ISO/IEC 14882.
2. Joshua Bloch, Effective Java, 3rd ed., Addison‑Wesley, 2018.
3. Guido van Rossum, Python Documentation – list objects, Python Software Foundation, 2023.
4. Robert Sedgewick, Kevin Wayne, Algorithms, 4th ed., Addison‑Wesley, 2011.
이 문서는 위키백과 스타일을 참고하여 작성되었으며, 최신 자료구조 교과서 및 공식 언어 문서를 기반으로 한다.