📈 배열?

값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.

자료구조에 대하여

자료구조는 크게 메모리 공간 기반의 연속(contiguous)방식과 포인터 기반의 연결(Link, 이전에 다루었던 linked list가 대표적인 예)방식으로 나뉜다.

😶 배열의 구조

배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형으로 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다.

배열은 처음 선언했을 때부터 크기가 고정되어 있으며 한번 생성한 배열은 크기를 변경하는 것이 불가능하다. 다음과 같은 배열이 있을 때 물리 메모리에 배열의 요소가 어떻게 배치되는지 알아보자

요소에 대한 접근

각 요소가 4바이트라고 가정했을 때, 배열 num의 요소가 물리 메모리에 다음과 같이 배치된다.

메모리에 대한 접근은 1바이트씩 이루어지는데 각 요소의 주소 또한 4바이트씩 증가한다.
배열은 각 주소가 4바이트씩 일정하게 달라지기 때문에 어느 위치에서나 O(1)에 접근이 가능하다는 장점이 있다. num[0]의 주소가 0x00이라고 했을 때, 4번째 값에 접근하고 싶으면 현재 주소에서 12만큼 증가한 0x0C로 접근을 하면 된다. 이러한 과정은 데이터의 개수가 몇 개로 늘어나도 똑같으며 즉시 주소를 계산할 수 있는 것 또한 마찬가지이다.

동적 배열

앞서 배열은 고정된 크기의 연속된 메모리 할당이라고 설명한 바 있다. 그런데 실제 데이터에서는 그 데이터의 크기를 알기가 어렵다. 어떤 경우에는 배열에 너무 작은 공간을 할당해서 크기가 모자랄 수도 있고, 어떤 경우에는 배열에 너무 큰 공간을 할당해서 메모리의 낭비가 될 수도 있다.

이러한 문제를 해결하기 위해서 동적 배열이라는 개념이 등장했으며 현재 우리가 사용하는 배열은 99% 동적 배열이라고 생각하면 된다.

원리

동적배열은 미리 초깃값을 작게 잡아 배열을 생성한 다음에 데이터가 추가되어 메모리가 꽉 차면 늘려준 다음 모두 복사하는 방식이다. 각 언어마다 이 메모리를 늘리는 비율이 상이한데, 이러한 구조적인 차이로 인해 속도에 차이가 생길 수 있다.