자료구조 _ Array와 Dynamic Array

Array는 무엇인가요?

Array는 데이터를 메모리상에 연속적으로, 미리 할당된 크기만큼 저장하는 자료구조 입니다.

Array의 특징

- 고정적 저장 공간이 필요합니다.

- 메모리에 연속적으로 저장합니다.

 

시간복잡도

- 램덤액세스(즉시 접근 가능 - 순차(X)) 방식이기 때문에 조회는 O(1)입니다.

- 마지막 삽입, 삭제도 O(1)입니다.

- 다만 일반 삽입, 삭제는 O(n)입니다.

장단점
- Array의 장점은 조회가 빠르다는 것입니다.

- Array의 단점은 고정된 저장 공간을 필요로 하기 때문에 Array의 크기를 미리 정해야 한다는 것입니다.

- 때문에 메모리 낭비나 추가적인 오버헤드가 발생할 수 있습니다.
*오버헤드 : Array 크기를 변경하면서 데이터 이동에 따라 발생하는 리소스

데이터가 Array 사이즈를 넘어선다면 해결 방법은?

기존 Array보다 큰 새로운 Array를 선언하여 데이터를 옮기거나, 사이즈를 예측하기 어렵다면 Array 대신 Linked List를 사용하여 데이터가 추가될 때마다 메모리를 할당받을 수도 있습니다.

 

 

Dynamic Array는 무엇인가요?

Array의 경우 사이즈가 고정이기 때문에 더 많은 데이터가 추가되면 저장할 수 없습니다.
Dynamic Array는 저장공간이 가득 차면 자동으로 리사이즈하여 유동적으로 Array의 사이즈를 조절할 수 있는 자료구조입니다. (파이썬의 리스트는 Dynamic Array입니다.)

 

 

리사이즈

- 리사이즈 방법으로는 Array 사이즈를 2배 늘리는 더블링이 있습니다.

- 더블링은 사이즈를 두 배 올리고 데이터를 일일이 옮기는 방법입니다.

- 새로운 배열에 데이터를 옮기는 경우의 시간 복잡도는 O(n)입니다. (간헐적)

 

 

장단점

- Array와 동일하나 Dynamic Array는 사이즈를 미리 고민할 필요가 없다는 장점이 있습니다.

- 자동으로 리사이즈를 할 때 필요 이상의 메모리를 할당받기 때문에 메모리가 낭비될 수 있습니다.