1️⃣

Array는 어떤 자료구조 인가요?

[핵심 답변]

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

[면접 TIP]

Array에 관한 질문을 할 때에는 매우 높은 확률로 Linked List에 대한 질문도 나오게 됩니다. 따라서 Array의 다양한 특징 중에서 Linked List와 비교가 되는 특성들을 위주로 대답을 하게 되면 편하게 풀어나갈 수 있습니다! Array와 Linked List의 가장 큰 차이점은 메모리에 저장되는 방식과 이에 따른 operation의 연산 속도(time complexity) 입니다. 이를 유념해서 공부해 가시면 좋은 답변을 하실 수 있습니다.

Array의 특징

•

고정된 저장 공간(fixed-size)

•

순차적인 데이터 저장(order)

Array의 장점은 lookup과 append가 빠르다는 것입니다. 따라서 조회를 자주 해야되는 작업에서는 Array 자료구조를 많이 씁니다.

Array의 단점은 fixed-size 특성상 선언시에 Array의 크기를 미리 정해야 된다는 것입니다. 이는 메모리 낭비나 추가적인 overhead가 발생할 수 있습니다.

시간복잡도

	Array
access	$O(1)$
append	$O(1)$
마지막 원소delete	$O(1)$
insertion	$O(n)$
deletion	$O(n)$
search	$O(n)$

[꼬꼬무 문답]

Q) 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐습니다. 이 때, 어떻게 해결할 수 있을까요?