Linked List vs. Array

본 글은 GeeksforGeeks의 Linked List vs Array을 번역한 글입니다.

배열(Array)

배열과 연결 리스트는 동일한 타입의 선형 데이터를 저장하는데 사용되지만, 각각 장단점을 가지고 있습니다. 설명은 연결 리스트의 장점에 맞추어 작성하였습니다.

1. 배열은 고정된(fixed) 크기를 가지고 있다 : 배열은 저장할 수 있는 상한선(upper limit)이 있다는 것을 알아야 합니다. 또한, 일반적으로 할당된 메모리는 사용한 양과 관계없이 상한선과 동일하며, 실제 사용면에서는 거의 상한선에 도달하지 않습니다.

2. 배열은 새로운 원소를 삽입하는 비용이 비싸다 : 새로운 원소를 추가하기 위해 공간을 만들어야 하고, 원소가 존재한다면 이동시키기 위해 공간을 새로 만들어야 합니다.

예를 들어, id 배열을 정렬된 상태로 유지시키고 싶다고 가정해 봅시다.

id[] = [1000, 1010, 1050, 2000, 2040, ...]

그리고 새로운 원소 1005를 삽입하고 싶다면, 우리는 정렬된 상태를 유지하기 위해 1000 뒤의 모든 원소들을 이동시켜야 합니다(1000은 제외). 삭제 또한 특별한 기술을 사용하기 전까지는 비쌉니다. 예를 들어, id 배열에서 1010을 삭제하려면 1010 뒤의 모든 원소를 이동시켜야 합니다.

연결 리스트(Linked list)

반면에, 연결 리스트는 배열과 다르게 아래와 같은 장점을 제공합니다.

1. 동적 크기(Dynamic size)

2. 쉬운 삽입/삭제(Ease of insertion/deletion)

하지만 연결 리스트는 다음과 같은 단점이 있습니다.

1. 임의 접근(Random access)가 불가능하다 : 원소에 접근하기 위해 첫 노드부터 연속적으로 탐색해야 합니다. 따라서, 연결 리스트로 이진 탐색(Binary search)을 할 수 없습니다.

2. 리스트의 각 원소는 포인터를 가지고 있기 때문에 추가적인 메모리(Extra memory)가 필요하다

3. 배열은 좀 더 나은 공간적 캐싱(cache locality)을 가지고 있고, 이는 성능에 가장 큰 차이를 만들 수 있다