선형 자료구조 - 배열

자료구조는 크게 메모리 공간 기반의 Contiguous 방식과 포인터 기반의 link 방식으로 나뉜다.
배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다.
(연결 방식의 가장 기본이 되는 자료형은 연결 리스트이다.)
추상 자료형 ADT의 실제 구현 대부분은 배열 또는 연결리스트를 기반으로 한다.
예를 들면 스택은 연결 리스트로 구현하고, 큐는 배열로 구현하는 식이다.

배열이란 고정된 크기만큼의 연속된 메모리의 할당이지만 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다. 그렇다면 미리 크기를 지정하지 않고 자동으로 조정할 수 있다면 좋지 않을까? 이러한 고민을 해결하고자 크기를 지정하지 않고 자동으로 resizing하는 배열인 동적 배열이 등장했다. 자바의 ArrayList C++의 std::vector, 파이썬의 List가 대표적인 예이다.

동적 배열의 원리는 간단하다. 미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 차면 늘리고 복사하는 식이다. 대개 Doubling으로 2배씩 늘려주게 되는데 모든 언어가 그런 것은 아니다.

CPython의 내부 구현으로 파이썬의 더블링 구조를 살펴보면 초반에는 2배씩 늘려 가지만 전체적으로 약 1.125배로 늘려간다. 기존의 데이터를 복사하는 작업이 필요하므로 O(n)의 비용이 발생하지만 분할 상환 분석에 따른 입력시간은 여전히 O(1)이다.