Array(배열) VS LinkedList(연결 리스트)

List(리스트)는 동일한 자료형으로 된 원소들의 모임으로 linear list(선형 리스트)와 linked list(연결 리스트)로 나뉩니다.

linear list의 종류로는 배열, 스택, 큐, 순환 큐 등이 있습니다.

 

이번 포스팅에서는 배열과 연결 리스트의 차이에 대해 설명합니다.

 

Array(배열)

Array(배열)은 가장 많이 사용되는 자료구조 중의 하나로 자료형이 동일한 원소들의 유한집합으로 정의됩니다.

array에 속한 각 원소들은 메모리에 연속적으로 저장되어 논리적 저장 순서와 물리적 저장 순서가 일치합니다.

따라서 고유의 index를 통하여 random access가 가능합니다.

따라서 찾고자 하는 index의 값을 알고 있으면 O(1)에 해당 원소로 접근이 가능합니다.

 

하지만 삭제 혹은 삽입의 경우, time complexity의 worst case가 O(n)이 됩니다.

예를 들어, Array의 원소 중 특정 원소를 삭제하면 배열의 연속적인 특징이 깨지게 됩니다.

연속적인 특징을 지키기 위하여 삭제한 원소의 인덱스보다 큰 인덱스를 가지는 원소들을 모두 shift 해야합니다.

따라서 time complexity가 O(n)이 됩니다.

 

Linked List(연결 리스트)

Linked list는 삭제와 삽입 측면에서 array의 time complexity 단점을 보완합니다.

linked list에 포함되는 각 원소들은 프로그램 실행 중에 동적으로 생성되거나 삭제됩니다.

원소들은 link를 통해 연결되어 있기 때문에 논리적으로는 선형적이지만 물리적으로는 분산되어있습니다.

따라서, 삭제와 삽입의 경우 특정 link만 수정하면 되기 때문에 time complexity가 O(1)이 됩니다.

 

하지만 linked list는 random access를 하고자 하면 time complexcity의 worst case가 O(n)이 됩니다.

원하는 위치에 접근하기 위하여 첫번째 원소부터 모두 확인해야하기 때문입니다.

 

결국, linked list는 search, insert, delete에 대해 모두 O(n)의 time complexity를 가집니다.

(insert, delete를 위해선 search가 전제되어야 하므로)

 

이렇다고 해서 linked list가 쓸모 없는 자료구조는 아닙니다.

linked list는 tree에서 사용되었을 때 유용성이 드러나기 때문입니다.