3단계: "elderberries"를 왼쪽으로 옮긴다.

▲ 그림 1-19

그림에서 보듯이 전체 삭제 연산에 3단계가 필요했다. 첫 번째 단계가 실제 삭제이고 나머지 두 단계는 빈 공간을 메꾸는 데이터 이동이다.

삽입과 비슷하게 원소 삭제에서 최악의 시나리오는 배열의 첫 번째 원소를 삭제하는 것이다. 이렇게 되면 인덱스 0이 비게 되고, 남아 있는 모든 원소를 왼쪽으로 이동시켜 빈 공간을 채워야 한다.

원소 5개를 포함하는 배열이면 1단계는 첫 번째 원소의 삭제에, 4단계는 남아 있는 원소 4개를 이동하는 데 쓰인다. 원소가 500개인 배열이면 1단계는 첫 번째 원소의 삭제에, 499단계는 남은 데이터를 이동하는 데 쓰인다. 따라서 원소 N개를 포함하는 배열에서 삭제에 필요한 최대 단계 수는 N단계라고 할 수 있다.

축하한다! 첫 번째 자료 구조의 시간 복잡도를 모두 분석했다. 자료 구조의 효율성을 분석하는 법을 배웠으니 이제 서로 다른 자료 구조가 어떻게 서로 다른 효율성을 내는지 볼 차례다. 사용자가 만든 코드에서 올바른 자료 구조의 선택이 소프트웨어의 성능에 중대한 영향을 끼칠 수 있으므로 이는 대단히 중요하다.

다음으로 다룰 자료 구조인 집합은 언뜻 봐서는 배열과 비슷하다. 하지만 배열과 집합에서 수행하는 연산의 효율성이 서로 다름을 곧 보이겠다.