[배열] 동적 배열 삭제 연산

이번 포스팅에서는 동적 배열에서 특정 위치에 있는 데이터를 지우는 삭제 연산에 대해서 배워 보겠습니다.

 

삭제 연산 동작

 

바로 예시를 볼게요. 이렇게 2, 3, 5, 7, 11이 있는 동적 배열에서 인덱스 1에 있는 3을 지우고 싶다고 할게요. 한 단계씩 봅시다.

1. 인덱스 1 뒤에 있는 데이터를 모두 한 칸씩 앞으로 밀어서 저장합니다.
   1. 인덱스 1에 인덱스 2에 있던 5를 저장합니다
   2. 인덱스 2에 인덱스 3에 있던 7을 저장합니다
   3. 인덱스 3에 인덱스 4에 있던 11을 저장합니다
2. 동적 배열은 배열의 크기와 개발자가 사용하는 인덱스들의 범위를 따로 관리합니다. 데이터를 삭제했으니까 동적 배열에서 접근할 수 있는 인덱스 범위도 1을 줄여 줍니다.

동적 배열에 남은 데이터를 확인해보면 2, 5, 7, 11입니다. 인덱스 1에 있는 데이터 3이 잘 삭제됐죠?

 

요약하자면, 삭제 연산은 그냥 삭제하고 싶은 데이터 뒤에 있는 모든 데이터 요소들을 한 칸씩 앞으로 밀어서 저장하면 됩니다.

 

삭제 연산 시간 복잡도

 

삭제 연산의 시간 복잡도를 알아봅시다.

 

전 레슨들에서는 데이터를 아무 위치에나 더해 주는 삽입(insert) 연산과 맨 끝에 더해주는 추가(append) 연산을 나눠서 생각했었는데요. 삭제 연산도 아무 위치의 데이터를 삭제할 때와 맨 뒤 데이터를 삭제할 때, 두 경우를 나눠서 생각할 수 있습니다.

 

맨 앞 데이터를 지울 때 (최악의 경우)

 

삭제 연산이 가장 오래 걸리는 경우는 가장 앞 인덱스에 있는 데이터를 지우는 경우입니다.

 

가장 앞 데이터를 삭제할 때는 인덱스 1부터 끝까지 모든 요소들을 한 칸씩 앞으로 밀어서 저장해야 됩니다. 그러니까 삭제하기 전 배열 안에 총 n 개의 데이터가 남아 있으면, 총 n−1개의 요소들을 하나씩 앞 칸으로 밀어서 저장해야 되는 거죠. 이 횟수가 n에 비례하기 때문에 O(n)이 걸린다고 할 수 있죠. 왜 가장 앞 인덱스를 지우는 게 최악의 경우인지 알겠죠?

 

종합해 보면 삭제 연산은 총 O(n)이 걸린다고 할 수 있습니다. 꽤 오래 걸리는 거죠.

 

맨 뒤 데이터를 지울 때

 

일단 아무 위치에 있는 데이터를 삭제할 때는 최악의 경우 O(n)이 걸린다고 했잖아요? 이번엔 맨 뒤 데이터를 삭제하는 데 얼마나 걸리는지 생각해 볼게요.

 

맨 뒤 데이터를 삭제할 때는 아무 요소도 안 밀고 저장해도 되고, 그냥 동적 배열의 사용 공간을 한 인덱스 줄이면 됩니다.

이건 배열에 데이터 요소가 몇 개가 있는지에 상관이 없이 일정한 시간에 할 수 있습니다. O(1)이라고 할 수 있는 거죠.

 

정리

 

정리해 보겠습니다.

 

동적 배열의 아무 위치에 데이터를 삭제할 때는 원하는 위치 뒤에 있는 데이터를 옮겨 저장해야 됩니다. 그래서 최악의 경우 O(n)이 걸립니다.

 

하지만 가장 뒤에 있는 데이터를 삭제할 때는 다른 데이터를 옮겨 저장할 필요가 없습니다. 따라서 O(1)이 걸립니다.