음악 플레이리스트에 Array와 List 중 어떤 걸 사용할까?

라는 질문을 면접 때 받았습니다. 부끄럽게도 답하지 못했습니다. 둘 중 하나를 고를 수 있었겠지만 근거가 없으니 답할 수 없었습니다. 이대로 CS를 내버려두면 앞으로의 면접도 자신있게 나서지 못할 것 같다는 생각이 들었습니다. 모른다고, 시간이 없었다고 핑계 대지 말고 자신있게, 솔직하게 답하기 위해 오늘도 정리를 시작합니다.

 

Array(배열, 순차 리스트)

질문에 대한 답을 내리려면 자료구조의 대한 이해가 바탕이 되어야 합니다. Array는 우리가 자주 사용하는 Swift의 Array와 동일합니다. 순서가 있는 컬렉션이죠.

Array가 순서를 가질 수 있는 이유는, 실제 메모리 상에서도 연속적으로 저장되어 있기 때문입니다.(논리적 저장 순서 == 물리적 저장 순서) 이 덕분에 순서는 인덱스(Index)로 표현되고, 인덱스를 알고 있다면 데이터에 대한 접근은 O(1)의 시간복잡도로 가능합니다.

 

데이터 삽입 어떨까요? 두톨과 세톨 사이 데이터를 추가하는 예시 그림을 살펴보겠습니다.

인덱스 3에 데이터를 삽입하는 순간, 기존의 세톨과 네톨의 인덱스는 +1 됩니다. 중간에 인덱스를 삽입하는 경우 뒤의 인덱스에 대한 모든 업데이트가 필요하기 때문에 O(N)의 시간복잡도를 가지게 됩니다. 0번째 인덱스에 데이터를 삽입하는 경우가 최악의 시나리오라고 볼 수 있겠네요.

 

반대로 말하면 위와 같이 마지막에 데이터를 삽입하는 경우 O(1)의 시간복잡도만으로 실행 가능합니다. 다른 인덱스를 업데이트 할 필요가 없기 때문입니다.

 

데이터의 삭제 또한 삽입과 동일합니다. 삽입은 인덱스를 밀어내는 과정이었다면, 삭제는 인덱스를 당겨오는 과정으로 생각할 수 있습니다.(마지막 데이터 삭제도 마찬가지겠죠?)

 

List(연결 리스트)

사실 위에서 살펴본 Array도 List에 포함된다고 합니다. 그럼 Array와 List의 차이점을 물었을 때의 List는 무엇을 뜻하는 것일까요? Array의 가장 큰 특징 중 하나는 메모리에 연속적으로 저장되어 빠르게 접근 가능하다는 것입니다. 이 때문에 Array는 순차 리스트라고 부르기도 합니다.

 

우리가 흔히 말하는 List는 LinkedList, 즉 연결 리스트를 뜻합니다. 메모리에 연속적으로 저장되어 있지는 않지만, Node를 이용해 연결함으로써 하나의 컬렉션을 구성하게 됩니다.

위 이미지를 살펴보면 가장 첫 번째 Node는 실제 데이터 '영톨'과 다음 노드의 메모리 주소 '0x2345'를 가지고 있습니다. 이를 통해 다음 노드를 참조하는 방식으로 원소를 탐색해야하기 때문에 원소에 대한 접근은 O(N)의 시간복잡도를 가지고 있습니다.

 

반면 데이터의 삽입은 Array와 비교해 상대적으로 빠르게 실행 가능합니다.

1. 삽입 할 위치의 기존 Node가 가지고 있는 다음 메모리 주소와 함께 데이터를 삽입하고, 2. 기존 Node의 메모리 주소를 새롭게 삽입된 Node의 메모리 주소로 업데이트만 실행하면 되기에 O(1)의 시간복잡도를 가지고 있습니다.(물론 어느 위치에 삽입해야할지 알고 있어야 합니다!)

 

삭제도 동일하게 O(1)의 시간복잡도로 실행 가능합니다. 삭제와 메모리 주소를 업데이트만 해주면 되기 때문이죠.

 

정리해보기

	Array(순차 리스트)	List(연결 리스트)
데이터 접근	O(1) → 상대적으로 빠름 🐰	O(N) → 상대적으로 느림 🐢
데이터 삽입	O(N), 단 끝에 삽입 할 경우 O(1) → 상대적으로 느림 🐢	O(1) → 상대적으로 빠름 🐰
데이터 삭제	O(N), 단 끝에 삽입 할 경우 O(1) → 상대적으로 느림 🐢	O(1) → 상대적으로 빠름 🐰
메모리 사용	연속된 메모리 공간 → 상대적으로 효율적 👍	Node와 포인터(추가 메모리 필요) → 상대적으로 비효율적 👎
크기 조절	기본적으로 정적 크기 (하지만 Swift에서는 기본적으로 동적 배열 및 COW를 이용해 성능 관리)	동적 크기

 

그래서 다시 돌아와 '음악 플레이리스트에 Array와 List 중 어떤 걸 사용할까?'의 질문에 어떤 답을 내리면 좋을까요? 제가 자주 듣는 플레이리스트의 특성을 정리해봤습니다.

• 10~20곡 사이 정도로 구성됨.
• 첫 곡 부터 시작해 마지막 곡까지 듣거나, 중간에 듣고 싶은 노래 부터 듣게 됨.
• 가끔씩 새로운 곡을 플레이리스트에 추가해놓음.(마지막에 들어감)

위와 같은 특성을 고려했을 때, 데이터의 삽입과 삭제는 크게 중요해지지 않을 것 같습니다. 중간에 삽입하거나 순서를 변경하는 일이 많지 않고, 만약 필요한 상황이 오더라도 곡의 총 개수가 크지 않기 때문에 시간복잡도의 차이가 미미할 것이라 판단했습니다.

 

중간에 듣고 싶은 상황(데이터 접근)이 더 빈번하게 발생할 것, 또 메모리의 효율을 생각했을 때 Array를 사용하는 것이 맥락에 잘 맞을 것 같습니다.

 

간단히 두 자료구조의 개념과 사용 맥락을 살펴봤습니다. 자료구조를 공부한다는 것은, 단순 이론을 학습하는 것을 넘어 실제 맥락에 적용할 수 있는 시야를 습득하는 과정인 것 같습니다.

 

Ref.

[자료구조] Array(배열) vs List(리스트)