배열
배열은 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별
자료구조는 크게 메모리 공간 기반의 연속방식Contiguous과 포인터 기반의 연결방식Link으로 나뉜다.
배열은 이중에서 연속 방식의 가장 기본이 되는 자료형이다.
배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기가 고정되어 있으며, 한번 생성한 배열은 크기를 변경하는 것이 불가능하다. 어느 위치에나 O(1)에 조회가 가능하다는 장점이 있다.
고정된 크기만큼의 연속된 메모리 할당이지만 실제 데이터에서는 전체 크기를 가늠하기 힘들때가 많다. 너무 작은 영역을 할당하여 모자라거나, 너무 많은 영역을 할당하여 낭비될 때도 있다. 이러한 점을 해결하고자 크기를 지정하지 않고 자동으로 리사이징하는 배열인 동적 배열이 등장했다.
파이썬에서는 리스트가 동적 배열 자료형이다. 자바에서는 ArrayList, C++에서는 std::vector가 대표적인 동적 배열 자료형이다. 대부분의 동적 프로그래밍 언어들은 정적 배열 자체가 없다. 파이썬에서도 정적 배열은 따로 없고 동적 배열인 리스트만 제공한다.
동적배열은 미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사하는 방식이다. 대개는 더블링Doubling이라 하여 2배씩 늘려주는데, 모든 언어가 항상 그런 것은 아니며 각 언어마다 늘려가는 비율은 상이하다.
CPython의 내부 구현을 살펴보면 0, 4, 8, 16, 25, 35,... 순으로 재할당하도록 정의되어 있다. 이 재할당 비율을 그로스 팩터Growth Factor, "성장 인자" 라고 한다. 파이썬의 그로스 팩터는 초반에는 2배씩 늘려가지만, 전체적으로는 약 1.125배로, 다른 언어에 비해서 다소 조금만 늘려가는 형태로 구현되어 있다.
동적 배열은 정적 배열과 달리 크기를 지정할 필요가 없어 매우 편리하게 활용할 수 있으며, 조회 또한 기존의 배열과 동일하게 O(1)에 가능하다.
