[CS / Array vs Linked List] ep01. Array는 어떤 자료구조인가요?

🤔 면접 질문

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

 

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

 

 

 

💡 면접 tip

: Array에 관한 질문을 할 때에는 매우 높은 확률로 Linked List에 대한 질문도 같이 나오게 된다. 따라서, Array의 다양한 특징 중에서 Linked List와 비교가 되는 특성들을 위주로 대답을 하게 되면 편하게 풀어나갈 수 있다. Array와 Linked List의 가장 큰 차이점은 메모리에 저장되는 방식과 이에 따른 Operation의 연산 속도(Time Complexity = 시간 복잡도)이다. 이를 유념하여 공부해가면 좋은 답변을 할 수 있을 것이다.

 

 

 

1️⃣ Array의 특징

• 고정된 저장 공간(Fixed-Size)
• 순차적인 데이터 저장(order)

 

- Array의 장점은 lookup과 append가 빠르다는 것이다. 따라서 조회를 자주 해야하는 작업에서는 Array 자료구조를 많이 사용한다.

 

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

 

 

 

2️⃣ 시간 복잡도

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

 

 

 

3️⃣ 심화 면접 예상질문

 

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

 

A2. 기존의 Size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당합니다. 모든 데이터를 옮겼다면 기존 Array는 메모리에서 삭제하면 됩니다. 이런식으로 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic Array라고 합니다.

 

또 다른 방법으로는, size를 예측하기 쉽지 않다면 Array 대신 Linked List를 사용함으로써 데이터가 추가 될 때마다 메모리공간을 할당받는 사용하면 됩니다.