[CS / Array vs Linked List] ep04. Array와 Linked list를 비교해서 설명해주세요.

🤔 면접 질문

Q1. Array와 Linked list를 비교해서 설명해주세요.

 

A1.  Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조입니다. 반면 Linked list는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지합니다.

 

그래서 각 operation의 시간 복잡도의 차이가 있습니다. 데이터 조회는 Array의 경우 O(1), Linked list는 O(n)의 시간 복잡도를 갖습니다. 삽입/삭제의 경우 Array는 O(n), Linked list는 O(1)의 시간 복잡도를 갖습니다.

 

 

 

💡 면접🐕🍯 tip

:  Array와 Linked list의 주된 차이점들은 메모리 구조에 기인한다. Array는 메모리상에서 연속적으로 데이터를 저장하고, Linked list는 그 반대이다. 메모리 구조의 차이로 인해 operation 구현 방법이 다르고 시간 복잡도도 다르다. 또한 메모리 활용에서도 차이가 있다. 유념해야 할 점은 상황에 따라 메모리를 효율적으로 사용할 수 있는 자료구조도 달라진다.

 

 

 

1️⃣ 조회(Lookup)

 

Array는 메모리상에서 연속적으로 데이터를 저장했기 때문에, 저장된 데이터에 즉시 접근(random access O(1))할 수 있다. 반면, Linked list는 메모리 상에서 불연속적으로 데이터를 저장하기 때문에 순차접근(Sequential Access)만 가능하다. 즉, 특정 index의 데이터를 조회하기 위해 O(n)의 시간이 걸리게 된다.

 

 

2️⃣ 삽입/삭제(insert / delete)

 

Array의 경우 맨 마지막 원소를 추가/삭제하면 시간 복잡도가 O(1)이다. 하지만 맨 마지막 원소가 아닌 중간에 있는 원소를 삽입/삭제하면 해당 원소보다 큰 인덱스의 원소들을 한 칸씩 shift 해줘야 하는 비용(cost)이 발생한다. 따라서 이 경우에는 시간 복잡도가 O(n)이 된다.

 

Linked list는 어느 원소를 추가/삭제 하더라도 node에서 다음 주소를 가르키는 부분만 다른 주소 값으로 변경하면 되기 때문에, 시간 복잡도는 O(1)이 된다.

 

 

 

3️⃣ Memory 관점

Array의 주된 장점은 데이터 접근과 append가 빠르다는 것이다. 하지만 메모리 낭비라는 단점이 있다. 배열은 선언시에 fixed size를 설정하여 메모리 할당을 한다. 즉, 데이터가 저장되어 있지 않더라도 공간을 차지하고 있기 때문에 메모리 낭비가 발생한다.

 

반면 Linked list는 runtime중에도 size를 유동적으로 변경할 수 있다. 그래서 initial size를 고민할 필요가 없고, 필요한 만큼 memory allocation을 하여 메모리 낭비가 없다.

 

 

 

3️⃣ 심화 면접 질문

Q1. 어느 상황에 Linked list를 쓰는 게 Array보다 더 나을까요?

 

A1.  답변

1) O(1)으로 삽입/삭제를 자주 해야 할 때
2) 얼마만큼의 데이터가 들어올 지 예측 못할 때
3) 조회 작업을 별로 수행하지 않을 때

 

 

Q2. 반대로 어떤 상황에서 Array를 쓰는게 Linked list보다 나을까요?

 

A2.  답변

• 조회 작업을 자주 해야될 때
• Array를 선언할 당시에 데이터의 갯수를 미리 알고 있을때
• 데이터를 반복문을 통해서 빠르게 순회할 때
• 메모리를 적게 쓰는게 중요한 상황일 때.
• Linked list보단 Array가 메모리를 적게 차지하기 때문에 미리 들어올 데이터의 양만 일고 있다면 Array를 통해 효율적인 메모리 관리가 가능하다.

 

 

Q3. Array와 Linked list의 memory allocation은 언제 일어나며, 메모리의 어느 영역을 할당받나요?

 

A3. Array는 compile단계에서 memory allocation이 일어납니다. 이를 Static Memory allocation이라고 하고, 이는 Stack memory 영역에 할당됩니다.

 

Linked list의 경우 runtime 단계에서 새로운 Node가 추가될 때마다 memory allocation이 일어나고, 이를 Dynamic Memory Allocation이라 부릅니다. 그리고 이는 Heap 메모리 영역에 할당됩니다.