Dynamic Array는 어떤 자료구조 인가?
Dynamic Array는 Array의 특징중 fixed - size의 한계를 보완하고자 고안된 자료구조 이다.
Array의 자료구조는 할당시 선언한 size보다 많은개수의 data를 추가하면 저장할수 없으나,
Array의 단점을 보완한 Dynamic Array는 저장공간이 가득 차게되면,
resize를 통해 유동적으로 size를 조절하여 데이터를 저장하는방식이다.
( 이로써 미리 size를 고민할 필요가 없다는 장점이 있다 )
resize를 하는 방법은 여러가지가 있는데,
대표적으로 Array의 size의 2배 size를 할당하는 doubling이 있다.
doubling - 데이터를 추가 app 하다가 메모리를 초과하게 되면 기존 배열의 size보다
두배 큰 배열을 선언하고 데이터를 일일이 옮기는 (n개의 데이터를 일일이 옮기는 O(n)의 방법이다.)
Linked List와 비교했을때 Dynamic Array의 장점은?
1. 데이터 접근과 할당이 O(1)로 굉장히 빠르다.
2. Dynamic Array의 맨뒤에 데이터를 추가하는것과 삭제하는것이 상대적으로 빠르다. (O(1)
Linked List와 비교했을때 Dynamic Array의 단점은?
1. Dynamic Array의 맨끝이 아닌곳에 data를 insert or remove 할때 느린편이다. ( O(n)
느린이유는 메모리상에 데이터들이 연속적으로 저장되어 있기때문에, 추가 및 삭제 시 뒤에 있는 data를
모두 한칸씩 이동시켜야 하기때문이다.
2. resize 해야할때, 예상치 못하게 현저히 낮은 performance가 발생한다.
3. resize에 시간이 많이 걸리므로. 필요한것 이상 memory 공간을 할당받는다. 따라서 사용하지 않고 있는
낭비되는 메모리 공간이 발생한다.