1. 개요
메모에 데이터를 저장하는 영역은 크게 스택과 힙으로 구분할 수 있다. 스택 영역은 일반적으로 고정된 크기를 가지나, 힙 영역은 프로그래머가 원하는 만큼 크기를 할당받을 수 있다. 따라서 동적 배열(dynamic array)는 힙을 이용하여 배열의 크기를 컴파일 타임이 아닌 런타임에 변경할 수 있는 배열을 의미한다.
2. 데이터의 삽입과 삭제 (insert and delete)
동적 배열에 데이터를 삽입하거나 삭제하는 연산은 두 가지 경우로 나눠 생각할 수 있다.
- 데이터를 배열의 마지막에 추가하거나 삭제하는 경우
- 데이터를 배열의 중간에 추가하거나 삭제하는 경우
2.1 데이터를 배열의 마지막에 추가하거나 삭제하는 경우
배열이 확보한 메모리 공간을 capacity라 하고, 배열에 채워진 데이터 크기를 size라고 한다. size보다 capacity가 크다면 아직 배열에 데이터를 저장할 공간이 남아있다는 의미이다. 이때 배열의 마지막 요소 다음에 추가하는 연산의 시간 복잡도는 O(1)이다. 삭제 연산도 동일한 시간 복잡도를 가진다.
하지만 배열이 가득 차 있다면 시간 복잡도가 달라진다. 배열이 가득 차 있는 상황 속에서 새로운 요소를 추가하는 경우, 이미 배열이 가득 차 있기 때문에 새로 충분한 공간을 확보하고 기존 배열의 요소를 모두 복사한 후 새로운 데이터를 추가해야하므로 이때의 시간 복잡도는 O(n)이 된다.
2.2 데이터를 배열의 중간에 추가하거나 삭제하는 경우
데이터를 배열의 중간에 추가하거나 연산의 시간 복잡도는 O(n)이다. 배열에서 삽입하고자 하는 자리 이후에 존재하는 요소들을 한 번씩 뒤로 옮겨야하기 때문이다. 만약, 0번째 인덱스에 새로운 요소를 추가하는 경우에는 기존 배열의 요소들을 모두 한 칸씩 뒤로 옮겨야하는 것이다. 따라서 최악의 경우를 고려해야 하므로 시간 복잡도는 O(n)이 된다.
