메모리에 데이터를 저장하는 영역은 세 군데인데, 그중 스택과 힙 영역이 있습니다. 스택은 실제 스택 프레임(파이썬의 스택 프레임과 개념은 같지만 실제 할당되는 공간은 다름)이 쌓이는 메모리 공간이고, 힙은 변수의 생성 시기와 소멸 시기를 프로그래머가 결정할 수 있는 메모리가 동적으로 할당되는 영역입니다. 배열을 공부하는 데 왜 뜬금없이 메모리 이야기를 꺼내는지 의아하겠지만, 동적 배열 개념을 이해하려면 스택과 힙 차이를 알아야 합니다.

스택 프레임을 할당하려면 미리 할당될 스택 프레임의 크기를 알고 있어야 합니다. 그래서 스택 영역에 배열을 만들기 위해서는 반드시 고정된 크기로 만들어야 했습니다. 프로그램에 사용할 데이터 크기를 명확하게 알고 있다면 다행이지만, 크기가 가변적으로 변할 수 있는 상황이라면 스택에 고정 크기를 가지는 배열을 만들어 쓰기에 어려움이 많습니다.

이에 반해 힙 영역은 프로그래머가 원하는 만큼 크기를 할당받을 수 있기에 일단 필요한 만큼 할당받아 데이터를 저장하다가, 많은 메모리가 필요한 순간이 오면 더 큰 공간을 확보하여 이전 배열 요소를 모두 복사한 후 새로운 데이터를 삽입할 수 있습니다. 동적 배열이란 힙 영역에 저장되는 배열을 의미합니다. 이에 여러 가지 유용한 연산을 추가해서 오늘날의 동적 배열이 완성되었습니다. C++의 vector, 자바의 ArrayList, 파이썬의 리스트가 동적 배열입니다. 그럼 동적 배열의 ADT를 작성해 볼까요?