정적 배열(Static Arrays)과 동적 배열(Dynamic Arrays)

데이터 구조에서 배열은 메모리 할당 개념에 따라 두 가지 방식으로 정의될 수 있다.

배열의 유형

기본적으로 배열에는 두 가지 유형이 있다.

정적 배열 : 컴파일 타임에 고정된 크기의 메모리가 할당됨. 이 배열의 크기를 변경하거나 업데이트 할 수 없음 O(1)

동적 배열 : 메모리가 런타임에 할당되지만 크기는 고정되지 않음.  배열의 크기를 변경하거나 업데이트가 가능. O(N)

정적 배열과 동적 배열의 예시

int a[5] = {1, 2, 3, 4, 5}; //Static Integer Array
int *a = new int[5]; //Dynamic Integer Array

정적 배열 : int a[5] = {1, 2, 3, 4, 5};

a라는 배열은 1, 2, 3, 4, 5 의 값으로 선언과 동시에 초기화 된다. 

따라서 배열 a는 스택에 할당되며, 배열의 크기는 선언과 동시에 결정되며 수정할 수 없다.

 

동적 배열 : int *a = new int[5];

a라는 정수에 대한 포인터를 선언하고 크기 5의 정수 배열에 대해 동적 방식으로 메모리를 할당함.

이 배열 a는 힙에 할당되며 필요한 경우 나중에 크기를 수정할 수 있음.

정적 배열 과 동적 배열의 그림 표현

출처 : geeksforgeeks

동적 배열의 리사이징

출처 : geeksforgeeks

동적 배열이 리사이징을 하는 과정

1. 기존에 있던 배열보다 2배 더 큰 배열을 할당

2. 일일이 요소들을 옮겨 초기화함 O(N)

3. 새로운 데이터를 추가 O(1)

4. 기존 배열은 삭제

결과적으로 동적 배열의 사이즈는 늘어남.

일일이 요소들을 옮겨 초기화하기에 시간 복잡도는 O(N)이 된다.

 

동적 배열의 리사이징 크기

그렇다면 왜 필요한 만큼 칸수를 하나씩 늘리는 것이 아니라 왜 2배씩 늘리는 것일까?

데이터를 하나만 추가한다면 한 칸만 늘리는 것이 효율적이겠지만,

만약 그렇지 않다면 데이터를 하나씩 추가할때마다 새로운 배열을 할당하고, 요소들을 옮겨 초기화하는 등의 작업을 계속해서 반복해야함.

즉, 요소를 추가할 때 마다 시간 복잡도가 O(N)의 상황이 발생하게 되기에, 상당한 시간을 소모하게 된다.(비효율적)

새로운 배열을 할당할 때 마다 2배의 크기로 할당(더블링)을 하는 것이다.

 

파이썬에서의 동적 배열

파이썬에서 사용하는 list도 이와 같은 동적 배열이기에 크기를 선언하지 않고 사용할 수 있는 것이다.

위는 cpython의 list관련 c 코드이다.

주석을 잘 살펴보면 The growth pattern is : 0, 4, 8, 16, 24, 32, 40,...

으로 적혀있는 것을 확인할 수 있다.

즉, 리스트가 리사이징 될 때 무조건 더블링 되는 것이 아닌 리스트의 사이즈가 작을때는 더블링이 되지만,

어느정도 리스트의 크기가 커졌을 경우에는 더블링이 아닌 약간의 증가를 통해 메모리를 효율적으로 사용하는 것을 알수있다.

이런식으로 언어의 구조의 따라 동적 배열의 크기가 변경되는 방식이 다르다고 할 수 있다.