Dynamic Array란?

배경

※ Static Array의 한계점을 보안하기 위해..

 

Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다 많은 데이터를 저장할 수 없다. (Static Array의 한계점)

이를 보안하기 위해 저장공간이 가득 차게되면 resize하여 유동적으로 array의 size를 조절할 수 있는 자료구조가 나왔다.

이를 Dynamic Array라 한다. 

 

 

Resize란?

1. 데이터를 계속 추가하다가 기존에 할당된 메모리를 초과하였다.
2. size를 늘린 배열을 선언한다.
3. 그곳으로 모든 데이터를 옮긴다.
4. 늘어난 크기의 size를 가진 배열이 된다. 이로써 새로운 데이터를 저장할 수 있게 된다. 

-> 데이터를 추가하다가 한계가 도달하는 시점에 더 큰 배열을 선언하여 모든 데이터를 그곳으로 옮긴다. 

따라서, size를 미리 고민할 필요가 없다는 장점이 있다. 

 

 

Doubling (Resizing 방식 중 하나)

- Resizing을 하는 방법은 여러가지가 있는데, 기본적으로 Doubling 방식(기존 array size의 2배 size를 할당하는 방식) 이 있다. 

- 데이터를 마지막 인덱스에 추가하는 O(1), size를 넘어설 때는 size를 두배 늘리고 데이터를 일일히 옮기는 과정 O(n) 발생한다. 

 

※ 시간복잡도는 O(1)? O(n)? 

- 가끔 발생하는 O(n)의 resize하는 시간을, 자주 발생하는 O(1)의 작업들이 분담해서 나눠 가짐으로써 전체적으로 O(1)의 시간이 걸린다고 생각하면 된다.

- 분할상환 시간복잡도(Amortized time complexity)를 사용하여 amortized O(1) 이라고 한다. 

 

 

---

 

장/단점

 

Static Array와 비교했을 때,

- 이를 보안해주는 자료구조로써 size를 고민하지 않고 유동적으로 조절할 수 있다.

 

Linked List와 비교했을 때,

- 데이터 접근이 빠르다.

- 맨 뒤에 데이터를 추가/삭제하는 것이 빠르다.

 

등의 장점이 있지만 

 

Linked List와 비교했을 때,

- 중간 데이터를 추가/삭제시 뒤에 있는 데이터들을 모두 shift해야하는 비용이 든다.

- resize할 때, 예상치 못하게 현저히 낮은 performance가 발생한다.

- resize에 시간이 만힝 걸리므로 필요한 것 이상 메모리 공간을 할당받게 될 수도 있어 메모리공간 낭비가 발생한다.

 

등의 단점이 있으므로 상황에 맞게 자료구조를 고려하여 선택해야한다.