그림 3-9를 보면, 배열의 맨 앞에 6을 삽입하고자 기존 모든 요소를 뒤로 한 번씩 옮긴 후 6을 맨 앞에 삽입하고 있습니다. 삭제도 이와 같습니다. 맨 앞의 6을 삭제하려면 뒤에 있는 1부터 5까지 모든 요소를 한 번씩 앞으로 옮겨야 합니다. 그래서 빅오는 O(n)입니다. 동적 배열의 삽입과 삭제라고 하면 최악의 경우를 고려해야 하므로 O(n)이라고 말합니다.
Tip 동적 배열은 언제 사용하나요?
동적 배열은 모든 언어에서 사용하는 가장 기본적인 자료 구조입니다. 여러 데이터를 한곳에 저장할 때 가장 먼저 고려합니다. 파이썬의 리스트도 동적 배열입니다. 자바에는 ArrayList가 있고 C++에는 vector가 있지요.
지금까지 동적 배열을 알아보았습니다. 대부분의 언어가 동적 배열을 지원하기 때문에 이런 작동 원리를 모르더라도 사용할 수는 있을 것입니다. 하지만 작동 원리를 공부하면 앞으로 파이썬 코드를 작성하면서 리스트의 append()와 insert() 메서드 중 무엇을 사용할지 고민하는 상황에서 분명한 근거를 대고 메서드를 선택하여 사용할 수 있을 것입니다.