[자료구조] Array

Array란?

연관된 데이터들을 모아서 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조

Array의 특징은 위에서 설명했듯이

- 고정된 저장 공간

- 순차적인 데이터 저장

 

그럼 미리 예상한 것보다 더 많은 수의 데이터를 저장하느라 Array의 크기를 넘어스면 어떻게 해결하냐?

방법1.(Dynamic Array)
기존의  크기보다 더 큰 Array를 선언하여 데이터를 옮기고 기존 Array는 메모리에서 삭제하면 됩니다. 이렇게 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic Array라고 합니다.

 

방법2.(Linked List)

애초에 크기를 예측하기 쉽지 않다면 Array 대신 Linked List를 사용하면 됩니다.

 

 

Array의 장점은 조회와 마지막 인덱스에 추가, 삭제가 빠르다는 것입니다. 그래서 조회를 많이 하는 경우에 Array를 사용하면 좋습니다.

 

이어서 Array의 단점은 위에서 보셨듯이 크기를 미리 정해야 하기 때문에 메모리 낭비나 추가적인 메모리가 필요할 수 있습니다.

 

 

Array의 시간 복잡도

- 조회: O(1)

- 마지막 인덱스에 추가: O(1)

- 마지막 인덱스에 삭제: O(1)

- 삽입: O(n)

- 삭제: O(n)

- 탐색: O(n)