이번에는 동적 배열의 삽입과 삭제 연산 중 배열의 중간에 데이터를 삽입하거나 삭제하는 연산을 알아보겠습니다.

새로운 요소를 배열의 맨 처음에 삽입해야 한다고 가정해 보겠습니다. 이때 동적 배열에서는 데이터를 맨 처음에 삽입하고자 이미 있는 요소들을 모두 한 번씩 뒤로 옮깁니다. 그 후 배열의 맨 처음에 새로운 요소를 삽입합니다. 데이터 개수가 n이라면 모두 n번 복사해야 하므로 O(n)입니다.

그림으로 살펴보겠습니다.

▲ 그림 3-9 동적 배열의 삽입과 삭제 3