[자료구조] Dynamic Array

Dynamic Array란?

Array랑 다르게 저장공간이 가득 차게 되면 resize를 하여
유동적으로 size를 조절하여 데이터를 저장하는 자료구조

 

그럼 resize는 어떻게 하는건데요??

예를들어 사이즈가 10인 배열이 있는데 11개의 데이터를 넣으려고 하면 들어가지 않는다.

이때 resize가 실행되는데 사이즈가10개인 배열보다 더 큰 배열을 선언하고 원래 데이터들을 새로 생성된 데이터에 옮긴 후 원래 배열을 지운다. 

resize를 하는 방법은 여러가지가 있는데 대표적으론 doubling(기본 Array size의 2배를 할당)이 있다. (O(n))

 

 

시간복잡도

resize 할땐 O(n)

resize는 가끔 발생하므로 O(1)로 생각

그 외엔 Array랑 같음