Array란 무엇인가?

🤓오늘의 공부 주제: Array🤓

Q. Array란 무엇인가?

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

Linked List와의 가장 큰 차이점은 메모리에 저장되는 방식과 이에 따른 operation 연산 속도.

Array의 특징

고정된 저장 공간, 순차적인 데이터 저장

<시간 복잡도>

조회(look up): O(1) - random access

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

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

삽입: O(n)

삭제: O(n)

탐색: O(n)

💡요약💡
장점: Array는 look up과 append 가 빠르다. 따라서 조회를 자주 해야하는 작업에서는 Array 자료 구조를 많이 쓴다.

단점: 고정된 저장공간 특성상 선언시에 미리 크기를 정해야한다. 이로 인해 메모리 낭비나 추가적인 오버헤드가 발생할 수 있다.

Q. 미리 예상한 것보다 많은 수의 데이터를 저장하느라 Array 사이즈를 넘어서게 됐습니다. 이때 어떻게 해결할 수 있나요?

A. 기존의 사이즈보다 더 큰 Array를 선언해서 데이터를 옮겨 할당합니다. 모든 데이터를 옮겼다면 기존의Array는 메모리에서 삭제하면 됩니다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic Array라고 합니다. 또 다른 방법으로는 사이즈를 예측하기 쉽지 않다면 Array대신 Linked List를 사용함으로써 데이터가 추가될 때마다 메모리 공간을 할당받는 방식을 사용하면 됩니다.

출처 : 인프런 - 기출로 대비하는 개발자 전공면접 [CS 완전정복]