배열, 동적 배열

 자료구조는 크게 메모리 공간 기반의 연속(Contiguous)방식과 포인터 기반의 연결(Link)방식으로 나뉜다.

배열은 이 중 연속방식의 가장 기본이 되는 자료형이다. 연결 방식의 가장 기본이 되는 자료형은 연결 리스트이다.

배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할방받는 작업을 수행하는 자료형이다.

 

배열의 예시를 그림으로 살펴보자.

 

 

C언어를 기준으로 int arr[4] = {4, 7, 29, 0}; 라는 예시를 들면, 위 그림과 같다. 32비트 이상의 시스템에서는 int를 4바이트로 사용한다. 배열은 어느 위치나 O(1)에 조회가 가능하다는 장점이 있다.

 

동적배열

 배열이란 고정된 크기만큼의 연속된 메모리 할당한다. 그러나 실제 크기를 가늠하기 어려운 상황에 따라 동적으로 메모리를 지정해야 하는 순간도 있다. resizing이 가능한 배열, 동적 배열이 있다. 자바에서는 ArrayList가 대표적인 동적 배열 자료형이다. 미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면, 늘려주고 모두 복사하는 식이다. 대개는 더블링(Doubling)이라 하여 대략 2배씩 늘려주는데, 모든 언어가 꼭 2배씩 늘려주는것은 아니다. 자바의 동적 배열인 ArrayList는 초깃값이 10인 배열을 설정하고 값으로 공간이 가득 차면 더블링으로 늘려준다. 그로스 팩터(Growth Factor, 성장 인자) 비율로 재할당 하며 대략 1.5배 이다. 즉 배열이 가득 차면 1.5배 더 큰 메모리 영역을 할당하고 다시 데이터를 모두 복사하는 식으로 늘린다.