[자료구조] Dynamic Array(동적 배열) 란?

 

 

Array의 고정된 배열 size 의 단점을 보완하기 위해 나온 자료구조

Array 란?

 

Array의 경우 배열의 크기가 고정 되어 선언시 배열의 크기 보다 많은 데이터의 갯수를 저장할 수 없다.

int[4] a = new int[]{1,2,3,4} // ok
int[4] a = new int[]{1,2,3,4,5} // error

 

이에 반해 Dynamic Array는 데이터의 저장 공간이 부족 하면 알아서 resizing를 하기 때문에 데이터의 저장이 자유롭다.

 

Dynamic Array가 resizing 를 하는 방법

1. 기존의 선언되었던 배열보다 큰 배열을 만든다. (보통 2배 size 할당하는 doubling 사용)

2. 배열의 값을 옮긴다.

3. 기존 배열을 삭제한다.

 

시간복잡도

데이터 추가시 O(1)

 

굳이 세부적으로 따지자면

기본적으로 데이터 추가시 O(1) 인데

마지막 인덱스에 추가시에만 resizing으로 인해 O(n)의 시간 복잡도를 가진다.

하지만 전체적으로 봤을때 resizing은 가끔 일어나기 때문에 O(1)으로 보면 된다.

 

나머지 시간복잡도는 Array와 동일

 

 

결론

장점

Dynamic Array를 사용하면 size를 고민 할 필요가 없다.

 

단점

resize시 시간이 오래걸린다.

resize시 넉넉한 메모리공간 할당으로 인한 메모리 낭비가 있다.