동적 배열은 필요한 원소 수에 맞추어 내부 배열의 용량을 조절하는 자료구조이다. 논리적인 길이와 확보한 용량이 다를 수 있다.
원리
용량이 부족하면 더 큰 공간을 확보하고 기존 원소를 옮긴다. 용량을 일정 비율로 늘리는 구현에서는 끝에 추가하는 연산의 분할상환 비용이 O(1)이 된다.
예시
용량 4인 배열에 다섯 번째 원소를 넣을 때 용량을 8로 늘릴 수 있다. 다음 세 번의 추가는 다시 할당하지 않아도 된다. 이 배수는 설명용이며 구현별 정책은 다르다.
주의할 점
한 번의 확장에는 O(n) 복사가 생길 수 있다. 분할상환 O(1)은 모든 호출의 지연이 일정하다는 뜻이 아니다. 중간 삽입에는 여전히 원소 이동 비용이 든다.