[자료구조] Array 와 Linked List의 비교 (feat.JS로 Linked List 구현)

cs에 대해 처음 공부하면서, 가장 많이 접한 것들 중 하나는 배열이다.

array를 정의해보면 다음과 같다.

Array

가장 기본적인 자료구조로, 논리적 저장 순서와 물리적 저장 순서가 일치한다.

그렇기 때문에 index로 해당 element에 접근할 수 있다. 

찾고자 하는 element의 index를 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 

 

array에서 맨 앞이나 맨 끝이 아닌 중간에 원소를 삽입, 혹은 삭제하는 과정을 생각해보자.

원초적인 방법은 자리를 만들어서 더하는 과정이다.

 

1. 해당 원소에 접근하여 O(1)로 작업 완료, 2. 더하거나 빼는 작업O(n)으로 구분된다.

접근하는 과정이 필요한 이유는, index를 알아야 하기 때문에 삽입할 자리를 만들기 위해서

기존 index를 뒤로 밀어야 한다. 

[1,2,,4,5] 에 가운데 2번 인덱스에 3을 넣으려면 4,5를 오른쪽으로 1칸씩 밀어야 한다는 것이다.

 

그렇기에 Array 자료구조에서 삭제 기능에 대한 시간복잡도 중 최악은 O(n)으로 구분된다.

 

이전에 이진탐색(O(log n))에 대해 포스팅하며 비교했었다. 

쉽게 정리해서 최악인 이유는, O(n)은 모든 경우의 수를 다 카운트하는 것이기 때문이다. 

 

이러한 문제점을 해결하기 위한 자료구조는 Linked List 가 있겠다. 

 

Linked List

linked list의 특징은 배열(array)과는 달리 모든 원소를 다 알고 있지 않고,

각 원소들이 바로 뒤의 원소가 무엇인지만 기억하고 있다. 

 

배열은 칸이 바로 옆에 붙어서 나열되어 있고, 자신의 위치, 그리고 값이 저장되어 있다면,

linked list는 칸마다 고정적인 위치가 아니라 동적인 위치로, 포인터로 연결되어 있다.

그렇기 때문에 연결된 서로의 앞뒤만 알고 있는 것이다.

 

Linked List는 배열과 달리 메모리상에 index에 의한 물리적 배치를 하는 것이 아니라

위 사진과 같이 node를 생성 후 해당 node의 pointer에 의해 다음 node를 연결한다. 

이를 통해 Linked List는 데이터 삽입/삭제시 배열처럼 index를 조정하는 등의

데이터의 구조를 재정렬하지 않아도 된다.

 

 

동일하게 삽입과 삭제를 생각해보자.

 

linked list에서의 삽입은 삽입할 노드를 삽입할 위치의 이전 노드를 다음 노드와 연결한다.

삭제도 마찬가지로 삭제하고 싶은 노드에 연결되어있는 앞 뒤의 노드를 서로 이어주면 된다.

 

배열은 삽입하거나 삭제하려면 해당 원소를 위해 다른 무언가가 옮겨지는 작업이 필요한데,

linked list는 메모리에 분산되어 있기 때문에 node가 고정 되어있고, 생성하기만 하고 

포인터의 연결을 바꿔주면 되기 때문에 node를 움직일 필요가 없다. 

그렇기 때문에 array와는 달리 삽입이나 삭제를 위해 무언가를 움직이는 과정이 생략된다.

 

포인터만 바꾸기 때문에 데이터 이동이 필요하지 않다.

따라서 데이터 삽입 및 삭제의 시간 복잡도는 O(1)로 매우 빠르다.

하지만 위치가 고정되어 있지 않기 때문에 탐색을 위해서는 항상 첫번째 노드부터 비교해야한다는 단점이 있다. 그래서 데이터 접근 시간은 결국 O(n)다.

 

 

그래서 기억하고 있는 값을 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있지만,

특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

 

 

Array, Linked list의 비교

그래서 array 와 linked list는 반대되는 성격이라고 볼 수 있겠다.

array가 index를 검색하는데 O(1)만에 할 수 있다면, linked list는 O(n)이 걸리고,

 

array가 원소를 삽입하는데 다른 원소를 옆으로 옮기면서 O(n)이 걸린다면

linked list는 옮기지 않고 알고있는 값의 바로 옆 위치로 삽입하기 때문에 O(1)이 걸린다.

 

 

 

 

JS에서는 linked list를 지원하지 않기 때문에 다음 포스팅은 js에서 linked list를 구현하는 과정을 담아보겠다.