Array의 경우 size가 고정되어 있기 때문에 선언시 설정한 size보다 많은 갯수의 data가 추가되면 저장 할 수 없습니다. 이에 반해 Dynamic Array는 저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조 입니다.
Dynamic Array는 size를 자동적으로 resizing하는 Array입니다. 기존에 고정된 size를 가진 static Array의 한계를 보완하고자 고안되었습니다. Dynamic Array는 data를 계속 추가하다가 기존에 할당된 memory를 초과하게 되면, size를 늘린 배열을 선언하고 그곳으로 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 배열이 됩니다. 이를 resize라고 합니다. 이로서 새로운 data를 저장할 수 있게되며 Dynamic Array는 size를 미리 고안할 필요가 없다는 장점이 있습니다.
resizing을 하는 방법은 여러가지가 있는데, 대표적으로 기존 Array size의 2배 size를 할당하는 Doubling이 있습니다.
Doubling
resize의 대표적인 방법으로 Doubling이 있습니다. 데이터를 추가하다가 메모리를 초과하게 되면 기존 배열의 size보다 두 배 큰 배열을 선언하고 데이터를 일일이 옮기는(O(n)) 방법입니다.
노젓는 개발자