장점과 단점
장점은 '조회'와 '추가'에 대한 시간 복잡도가 O(1)이라는 것 입니다. 따라서, 잦은 조회나 추가 작업이 예상될 경우 해당 자료구조를 사용하는 것이 유리합니다. 다만, 추가의 경우 마지막 인덱스에 추가하는 경우에만 이와 같은 장점을 가지고 있음을 유의해야 합니다.
단점은 고정된 크기를 가지는 특성으로 인해 '메모리 낭비'와 '추가적인 오버헤드'가 발생할 수 있다는 점입니다.
왜, 그럴까?
Array는 연관된 Data를 '메모리상에 연속적'이며 '미리 할당된 크기'만큼 저장하는 자료구조입니다. 이를 바탕으로 "왜 저런 장단점이 존재할까?"에 대해 생각해 보도록 하겠습니다.
장점
'메모리상에 연속적'이라는 특징은 처음 인덱스에 해당하는 위치만 알 수 있다면 다음 인덱스를 offset을 통해 쉽게 구할 수 있음을 의미합니다. 이로 인해, '조회'와 '마지막 인덱스 추가, 삭제'와 같은 경우 O(1)의 시간 복잡도를 가지는 우수한 성능을 보여줍니다.
이제, 그림을 통해 자세히 살펴 보도록 해보겠습니다.
위 그림은 Data들이 메모리 상에 연속적으로 저장되어 있으며 미리 할당한 크기만큼 저장된 것을 표현하고 있습니다.
이해를 위해 3번 인덱스에 저장된 값을 가져와야 하는 상황이라고 가정해보겠습니다.
위 그림과 같이 0번 인덱스의 주소를 알고 있다면, 오프셋을 더하여 3번 인덱스의 위치를 찾아 저장된 값을 확인할 수 있습니다. 또한, 이를 이용하여 마지막 인덱스의 주소를 찾아 '삽입'을 수행할 수 있겠죠?
단점
'미리 할당한 크기'라는 특징으로 인해 할당한 크기를 모두 사용하지 못할 경우 '메모리 낭비', 예상과 달리 더 큰 크기가 필요한 경우 '추가적인 오버헤드'가 발생합니다.
아래 그림은 크기를 7로 할당했으나, 이를 전부 사용하지 않는 경우를 표현한 것 입니다.
이처럼 사용하지 않는 메모리 공간이 존재하고, 앞으로도 사용할 예정이 없다면 이는 메모리 낭비로 이어질 수 있습니다.
또한, 아래 그림처럼 미리 할당한 크기 이상의 데이터를 보관해야 하는 경우도 발생할 수 있습니다.
이 경우엔 새로운 Array를 할당받아 기존에 있는 데이터를 옮긴 후
기존에 사용하고 있던 Array에 할당된 메모리 공간을 해제하는 과정이 필요합니다.
이로 인해, '새로운 Array 할당', '기존 Array에서의 데이터 이동', '기존 Array에 할당된 메모리 해제' 등의 오버헤드가 발생할 수 있습니다.
정리
위 내용을 다시 한 번 정리하면 다음과 같습니다.
- Array는 Data를 '메모리상에 연속적으로 저장(연속성)'하며 '미리 할당한 크기(불변성)'를 가진다.
- '연속적'이라는 특징은 빠른 조회와 빠른 삽입(마지막 인덱스)이라는 장점을 만들어준다.
- '불변성'이라는 특징은 예상과 다른 상황으로 인해 '메모리 낭비'와 '추가적인 오버헤드'가 발생할 수 있다.
예상 질문
Array는 어떤 자료구조인가요?
데이터를 메모리상에 연속적으로 저장하며, 미리 할당된 크기를 가지는 자료구조입니다.
Array의 장단점은 무엇인가요?
장점은 '조회'와 '마지막 인덱스에 대한 빠른 추가 및 삭제'에 대해 우수한 성능을 가지고 있습니다. 단점은 크기가 불변하여 '메모리 공간 낭비'와 '추가적인 오버헤드'를 초래할 수 있다는 점입니다.
미리 예상한 것보다 더 많은 크기의 Data를 저장해야할 필요가 있다면, 어떻게 해결할 수 있을까요?
기존 Array보다 크기가 큰 Array를 할당한 후, 데이터를 복사합니다. 이후, 이전에 사용한 Array는 삭제합니다. 이렇게 동적으로 배열의 크기를 조절하는 자료구조를 'Dynamic Array'라고 부르기도 합니다.
만약, 크기를 예측하기 쉽지 않다면 Linked List를 사용하여 데이터 추가시 메모리 공간을 할당받는 방식으로 사용할 수있습니다.
