[자료구조] Dynamic Array

오늘은 Dynamic Array에 대해 알아보겠습니다.

 

Dynamic Array란?

(Static) Array의 확장을 못한다는 단점을 극복하기 위해 나온 자료구조입니다.

즉, 메모리의 크기가 동적으로 변할 수 있는 Array라는 거죠

 

Array와 비슷하기 때문에 Dynamic Array에 대한 기초적인 설명은 생략하겠습니다.

Array를 잘 모르신다면 아래 글을 먼저 읽고 오셔도 좋을 것 같습니다.

 

https://changbroblog.tistory.com/142

[자료구조] Array

 

Dynamic Array는 어떻게 메모리를 동적으로 증가시키지?

결론을 말하면 Dynamic Array는 보통 본인(Array)이 생성된 크기를 넘어서면
본인의 크기의 2배인 배열을 생성하고 그 배열에 데이터들을 옮기고 원래 배열을 삭제합니다.

 

쉽게 차근차근 설명해 보겠습니다.

 

일단 Int형이고 크기가 3인 Dynamic Array인 arr을 생성했다고 생각해 봅시다.

 

arr.add(1);
arr.add(2);
arr.add(3);
arr.add(4); // ??? 크기가 3인데 어떻게 이게 들어가지?

 

위 코드를 보시면 기존 Array의 크기보다 큰 4개의 데이터를 넣고 있습니다.

아래 그림으로 어떻게 메모리를 동적으로 증가시키는지 설명드리겠습니다.

이해가 되시나요?

 

위 그림처럼 차례대로

1. 크기가 2배인 배열을 생성한다.

2. 기존 데이터를 새로 만든 배열에 옮긴다.

3. 기존 배열은 삭제하고 추가하려고 했던 데이터를 추가한다.

 

이런 식으로 진행되게 됩니다.

 

Array의 단점을 보완한 Dynamic Array 잘 이해되셨길 바랍니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.