위키득계정 ↗
기술

동적 배열

동적 배열기술
영문명
Dynamic array
크기
현재 저장한 원소 수
용량
확보한 저장 칸 수
대표 특성
인덱스 접근과 용량 확장
동적 배열은 원소 수의 변화에 맞춰 내부 저장 공간을 다시 확보할 수 있는 배열 기반 자료 구조이다. 실제 원소 수와 확보된 용량을 구별하며 필요할 때 더 큰 배열로 옮기는 방식 등이 쓰인다.

크기와 용량

용량이 8이고 원소가 5개라면 세 칸은 향후 추가를 위한 여유 공간이다. 원소를 하나 더 넣어 크기가 6이 되어도 용량이 반드시 바뀌는 것은 아니다. 크기와 용량을 같은 값으로 가정하지 않는다.

공간이 부족하면

내부 배열이 가득 차면 더 큰 저장 공간을 확보하고 기존 원소를 옮길 수 있다. 이때 한 번의 뒤 추가가 많은 복사 작업을 동반한다. 모든 추가가 같은 실제 비용을 갖는 것은 아니다.

기하급수적인 확장

용량을 일정 비율로 늘리면 추가만 이어지는 연산열의 복사 비용을 효율적으로 제한할 수 있다. 두 배 확장이 대표 예다. 반면 매번 일정한 칸 수만 늘리면 긴 추가 연산열에서 복사가 자주 반복될 수 있다.

중간 삽입과 구별한다

일반적인 연속 저장 동적 배열에서 중간에 원소를 넣거나 지우면 뒤 원소들을 이동시켜야 할 수 있다. 뒤 추가의 분할 상환 O(1)이라는 성질을 모든 위치의 삽입·삭제에 그대로 적용해서는 안 된다.

관련 문서

배열 / 연결 리스트 / 분할 상환 분석 / 시간 복잡도 / 공간 복잡도 / 자료 구조