[선형 자료구조] 1. Array

데이터 요소가 순차적으로 배열되는 자료구조를 선형(Linear) 자료구조라고 한다. 선형 자료구조는 단일 레벨로 구성된다. 배열, 스택, 큐, 연결 리스트 등이 모두 선형 자료구조에 속한다.

배열

C 언어를 기준으로 배열을 설명해보면, 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 크기가 고정되어 있기 때문에 한번 생성하면 크기를 변경하는것이 불가능하다. 예를 들어 정수형 요소 3개로 이뤄진 배열을 생성하면 다음 그림처럼 물리 메모리에 배열 요소 값들이 순서대로 배치된다.

int arr[3] = { 3, 6, 9 };

물리 메모리에 순서대로 배치된 배열

최신 시스템(32비트 이상)과 컴파일러 기준으로 int를 4바이트로 사용한다. 따라서 가리키는 주소는 1바이트마다 1씩 증가한다. 여기서는 int형 배열을 선언했기 때문에 각 엘리멘트는 4바이트, 따라서 배열 주소도 4씩 증가한다.

배열은 어느 위치에서나 O(1)에 조회가 가능하기 때문에 메모리 주소값을 손쉽게 계산할 수 있다. 이렇게 고정된 크기만큼 연속된 메모리 할당을 하는 경우 실제 데이터에서 전체 크기를 가늠하기 힘들 때 메모리가 심하게 낭비되는 경우가 종종 발생한다. 따라서 이런 고민을 해결하기 위해 크기를 지정하지 않고 자동으로 리사이징하는 동적 배열이 등장했다. 대부분 프로그래밍 언어는 동적 배열을 지원하며, 자바에서는 ArrayList, C++에서는 std:vector가 대표적이다. 파이썬에서는 정적 배열을 따로 제공하지 않으며 동적 배열인 리스트만 제공한다.

동적 배열

동적 배열의 원리는 초기값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 채워지면 늘려주고 복사하는 식이다. 대개는 더블링(Doubling)이라 하여 2배씩 늘려주는데, 각 언어마다 비율은 다를 수 있다. CPython의 내부 구현을 살펴보면 다음과 같다.

//cpython/Objects/listobject.c
// The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
new_allocated = (size_t)newsize + ( newsize >> 3 ) + newsize < 9? 3: 6);

파이썬의 경우 초반에는 2배씩 늘려가지만, 전체적으로는 약 1.125배로 조금씩만 늘려가는 형태로 구현되어 있다. 최악의 경우 새로운 메모리 공간에 배열을 다시 할당하고 기존 데이터를 복사하는 작업이 필요하므로 O(n) 비용이 발생하지만, 자주 있는 일이 아니기 때문에 분할 상황 분석^[각주:1]에 따른 입력 시간은 여전히 O(1)이다.

1. 특정 상황에서는 좋지 않은 성능을 내지만, 나머지 상황에서는 좋은 성능을 낼 때 모든 연산을 고려해 성능을 분석하는 것 [본문으로]