배열의 삭제 시간복잡도

안녕하세요 현강님.

삭제를 할 때와 삽입을 할 때 모두 shift를 해야만 하는 이유가 있어요.

배열은 연속적이고 순차적으로 메모리에 저장되어야 한다는 정의 때문이에요.

왜 굳이 연속적이고 순차적으로 저장하냐라고 물으신다면, random access의 장점을 이용하기 위해 그렇게 정의를 한 겁니다.

물론 삭제할 때 굳이 땡기지 말고 빈자리(공석)으로 남기면 안되나? 라고 물으신게 맞으시죠??!

삭제 후에 빈자리가 생기면 굳이 땡기지(shift)말고 그냥 놔두면, 그곳에 있는 데이터를 잘 못 접근했을 때 생기는 문제등을 해결하기 위해 "이곳은 빈 곳입니다" 라는 라벨을 걸어둬야 할 거에요.

결국 여러가지 효율적인 문제때문에도 그렇고, 배열의 정의때문에도 삽입 삭제를 할 때는 연속적이고 순차적인 성질을 유지하기 위해 shift를 해줘야 합니다.

혹시 질문에 대한 답이 됐을까요~? 더 궁금한점이 있으면 편하게 질문주세요!