[Data Structure] Linked List

Linked list(연결리스트)

 

연결리스트의 모든 요소는 node로 이루어져있으며 각 노드는 그 다음 노드에 대한 주소값을 참조하고,

선형적인 자료구조로 메모리에 연속적으로 위치해있지 않다.

 

 

node = data field + 다음 node에 대한 reference값

 

 

배열과 유사하지만, 배열은 다음과 같은 한계가 있다.

 

- js를 제외한 대부분의 언어에서, 배열의 크기는 고정되어있다 : 우리는 배열의 요소의 최대 개수를 반드시 알아야한다.

 

- 요소를 삽입할 때 새로운 요소를 위한 공간을 만들기 위해 존재하는 모든 요소가 이동해야 한다. 그래서 요소 삽입에 비용이 많이 든다

 

연결리스트의 장점

- dynamic size → 프로그램이 진행되는 동안 크기가 커지거나 작아질 수 있다.

 

- 자료 삽입, 삭제가 용이하다.

 

연결리스트의 단점

- 임의의 접근이 불가능하다. 우리는 반드시 첫 번째 노드부터 순차적으로 접근해야 한다.

(linkedlist의 기본적인 구현으로는 효율적으로 이진탐색을 할 수 없다.)

 

- 각각의 요소에 대해 pointer를 위한 추가적인 메모리 공간이 필요하다.

 

- 연결리스트는 연속적으로 위치해있지않기 때문에 참조의 인접성이 없다.

 

- 연결리스트의 주된 장점은 임의적인 개수의 값을 위해 꼭 필요한 메모리만 사용하면서 값을 포함시킬 수 있다는 것이다.

 

 

(자바스크립트를 제외한 대부분의 다른 언어들에서는 배열을 선언할 때 그 크기를 지정해주어야한다.)

 

 

연결리스트는 코드가 실행되는 동안 그 크기가 내부 요소의 삽입과 삭제에 따라서 변할 수 있다.

 

 

연결리스트의 시간복잡도

 

- 탐색 : 배열의 경우 인덱스로 해당 값에 대한 주소가 할당이 되어있기 때문에 O(1)의 시간 복잡도를 가진다.

 

반면 연결리스트의 경우 값을 탐색하려면 첫 번째 노드(head)부터 하나하나 찾아가야하기 때문에 시간복잡도는 O(N)(N은 연결리스트 내의 노드의 수)이다. 

 

만약 찾으려는 값이 첫 번째 노드에 있다면 한 번의 동작으로 요소를 찾을 수 있겠지만 최악의 경우 찾으려는 값이 연결리스트 내에 존재하지 않는다면 노드의 개수만큼 코드가 실행되어야 한다.

 

- 삽입/삭제 : 배열의 경우 삽입/삭제의 시간복잡도는 O(N)이다. 배열에 요소를 삽입하려 할 때 최악의 경우 배열의 맨 앞에 요소를 삽입하려하면 나머지 요소들이 모두 한 인덱스만큼 뒤로 옮겨져야하기 때문이다.

 

반면에 연결리스트의 경우에는 삽입 또는 삭제하려는 위치를 알고있는 경우 한 번의 동작만으로 요소가 삽입/삭제될 수 있기 때문에 시간복잡도는 O(1)이다.

 

* 한 번의 동작이란 다음과 같다.

- 데이터 추가

1. 인자로 받은 값을 이용해 새로운 노드를 생성한다.

2. 새로운 노드의 포인터가 삽입할 위치의 노드를 참조하도록 지정한다.

3. 삽입할 위치 전에 있던 노드의 포인터가 새로운 노드를 참조하도록 지정한다.

 

- 데이터 삭제

1. 삭제할 노드 전에 있던 노드의 포인터가 삭제할 노드 뒤에 있는 노드를 참조하도록 지정한다.

2. 삭제할 노드의 포인터를 null로 지정한다.

 

 

연결리스트의 삽입과 삭제시 시간복잡도는 경우에 따라 두 가지로 나뉜다.

 

1. 삽입 또는 삭제할 위치를 아는 경우

이 경우 위와 같은 방법으로 시간복잡도는 O(1)이다.

 

2. 삽입 또는 삭제할 위치를 모르는 경우

이 경우 삽입 또는 삭제할 위치를 탐색하는 과정이 필요하므로 시간복잡도는 O(N)이 된다.

 

---

 

내가 의문이 들었던 부분은 시간복잡도에서 O(1)이 뜻하는 바는 input에 관계없이 항상 일정한(constant)결과값이 도출되는 경우를 말하는 것인데 위와 같은 경우는 어떠한 상황에서는 시간복잡도가 O(N)이 되는것이므로 일정하다고 할 수 없는 게 아닌가 하는 생각이 들었다.

 

➡️ Edit: Big-O 표기법에서 시간복잡도는 최악의 상황을 기준으로 계산한다. 지금 내가 말하는 '어떠한 상황'이라는 것은 최악의 상황을 말하는 것이 아니라 '삽입 또는 삭제할 위치를 모르는 경우'를 말하는 것이다.

 

하지만 위와 같은 경우가 있다고 하여 연결리스트의 삽입과 삭제의 시간복잡도는 O(N)이다 라고 말하기는 어렵다. 삽입 또는 삭제할 위치를 모르기 때문에 탐색의 과정이 필요하다고는 하지만 순수하게 삽입과 삭제만 고려했을 때 시간복잡도는 O(1)이라고 할 수 있기 때문이다. 

 

그리고 약간 논점을 벗어난 이야기일 수 있지만 자료구조의 시간복잡도에 대해서 어떤 특별한 상황을 가정하여 이때의 시간복잡도는 X니까 이것의 시간복잡도는 X다!하고 딱 떨어지게 정의하는 것에 초점을 맞추기보다는 현재 정의되어있는 시간복잡도를 기본적으로 인지하되 어떤 상황에서 어떤 자료구조가 적합할지에 대한 고민에 초점을 맞추는 것이 중요할 것 같다.

 

이를테면 배열의 경우 탐색 또는 조회가 빈번하게 일어나는 로직을 구현할 때 좀 더 효율적으로 동작할 수 있을 것이고 자료의 삽입과 삭제가 빈번하게 일어나는 경우라면 연결리스트, 그중에서도 이중 연결리스트(Doubly linked list)가 적합할 것이다. 

 

 

단일 연결리스트와 이중연결리스트에 대해 간단히 살펴보면 이 둘을 구분짓는 가장 큰 차이는 노드를 이루는 요소의 개수이다.

 

단일 연결리스트는 우리가 흔히 말하는 연결리스트이다. 즉 하나의 노드는 값과 다음 노드에 대한 참조값으로 이루어져있다.

 

이중 연결리스트는 하나의 노드가 값과 이전 값에 대한 참조값, 다음 값에 대한 참조값으로 총 세 개의 요소로 이루어져있다.

 

그래서 메모리를 조금 더 많이 사용하긴 하지만 양쪽 방향 모두에서 접근할 수 있기 때문에 자료의 탐색과 삽입, 삭제 등에 더욱 효율적으로 동작한다.

 

 

 

-