연결 리스트

배열에서는 중간에 새로운 값을 추가하기 위해 뒤에 있는 원소들을 모두 한 칸씩 밀어야 했습니다. 그렇다면 기존 원소들을 옮기지 않고 새로운 값을 추가할 수는 없을까요?

값들을 연속된 공간에 놓는 대신 각 값이 다음 값을 가리키도록 연결하여 순서를 표현할 수 있는 자료구조가 있습니다. 이러한 구조의 자료구조를 연결 리스트(linked list) 라고 부릅니다.

연결 리스트란

연결 리스트는 노드(node) 를 연결해 데이터를 순서대로 저장하는 선형 자료구조입니다. 가장 기본적인 형태에서 각 노드는 다음의 두 가지 정보를 가집니다.

• 값(value): 노드에 저장할 데이터
• 다음 노드의 참조(next): 다음 순서에 있는 노드를 가리키는 정보

예를 들어 10, 20, 30을 저장한 연결 리스트는 다음과 같이 표현할 수 있습니다.

head
 ↓
[10 | next] → [20 | next] → [30 | null]

첫 번째 노드는 시작이라는 의미에서 head라는 참조를 이용해 가리킵니다. head에서 시작해 각 노드의 next를 따라가면 순서대로 모든 값을 확인할 수 있습니다. 마지막 노드의 next는 다음 노드가 없다는 의미로 null을 가집니다.

JavaScript 객체로 노드 세 개의 관계를 표현하면 다음과 같습니다.

const third = { value: 30, next: null };
const second = { value: 20, next: third };
const first = { value: 10, next: second };

const head = first;

first.next에는 값 20이 아니라 second 객체의 참조가 들어 있습니다. 따라서 다음 노드의 값을 읽으려면 head.next.value처럼 참조를 따라가야 합니다.

원하는 위치에 접근하는 방법

배열에서는 인덱스를 알고 있다면 해당 위치에 바로 접근할 수 있습니다. 하지만 연결 리스트에서는 특정 노드의 위치를 바로 계산할 수 없습니다.

첫 번째 노드        두 번째 노드        세 번째 노드
head          →   head.next      →   head.next.next
10                20                 30

예를들어 세 번째 노드의 값을 읽으려면 첫 번째 노드에서 다음 노드로 두 번 이동해야 합니다.

head.value;           // 10
head.next.value;      // 20
head.next.next.value; // 30

원하는 위치가 뒤에 있을수록 더 많은 연결을 따라가야 합니다. 원소가 n개일 때 마지막 위치까지 접근하는 데는 O(n) 이 걸립니다. 특정 값을 찾는 탐색도 값을 하나씩 비교해야 하므로 최악의 경우 O(n) 입니다.

중간에 노드를 삽입하는 과정

다시 10 → 20 → 30으로 연결된 리스트를 생각해봅시다. 여기에 값 15를 가진 노드를 10과 20 사이에 넣으려고 합니다.

배열에서는 20과 30을 뒤로 옮겨야 하지만 연결 리스트에서는 새 노드를 만들고 연결을 바꾸면 됩니다.

삽입 전
10 → 20 → 30 → null

1. 새 노드가 기존의 다음 노드를 가리키게 합니다.
15 → 20

2. 앞 노드가 새 노드를 가리키게 합니다.
10 → 15 → 20 → 30 → null

앞에서 만든 객체를 이용하면 다음과 같이 표현할 수 있습니다. previous는 삽입할 자리 바로 앞의 노드라고 가정합니다.

const previous = head;
const newNode = { value: 15, next: previous.next };

previous.next = newNode;

새 노드가 먼저 기존의 다음 노드인 20을 가리키게 한 뒤 10의 next를 새 노드로 바꿉니다.

리스트가 더 많은 노드를 가지고 있어도 이 작업에 필요한 변경은 그대로 입니다. 따라서 삽입할 자리 바로 앞의 노드를 이미 알고 있다면 삽입은 O(1)입니다.

하지만 삽입할 자리 앞의 노드를 알지 못하고 “5번째 위치에 값을 추가해라”와 같은 정보만 주어진 경우에는 삽입을 위해 그 자리까지 이동하는 작업이 필요합니다. 따라서 이때는 탐색 비용이 더해져 전체 삽입이 최악의 경우 O(n)이 됩니다.

중간에 노드를 삭제하는 과정

방금 삽입한 15를 다시 삭제해봅시다.

삭제 전
10 → 15 → 20 → 30 → null

삭제 후
10 ─────→ 20 → 30 → null

10의 다음 노드가 15를 건너뛰고 20을 가리키도록 바꾸면 됩니다.

const target = previous.next;

previous.next = target.next;

여기서도 중요한 조건은 삭제할 노드 바로 앞의 노드를 알고 있어야 한다는 점입니다.

노드를 찾는 과정까지 필요하다면 삭제도 최악의 경우 O(n)입니다. 따라서 연결 리스트의 삽입과 삭제를 설명할 때는 위치를 찾는 비용과 연결을 바꾸는 비용을 나누어 생각해야 합니다.

단일 연결 리스트와 이중 연결 리스트

지금까지 살펴본 것처럼 각 노드가 다음 노드를 가리키는 구조를 단일 연결 리스트(singly linked list) 라고 합니다.

head → [10] → [20] → [30] → null

구조는 단순하지만 이동 방향이 한쪽으로 제한되어 있습니다. 이를 보완하기 위해 이전 노드의 참조인 prev를 함께 저장하는 구조를 생각할 수 있고 이러한 자료구조를 이중 연결 리스트(doubly linked list) 라고 부릅니다.

       head          tail
        ↓             ↓
null ← [10] ⇄ [20] ⇄ [30] → null

이중 연결 리스트에서는 next로 다음 노드에, prev로 이전 노드에 접근할 수 있습니다. 20을 삭제하려면 앞 노드인 10의 next와 뒤 노드인 30의 prev가 서로를 가리키도록 바꾸면 됩니다.

따라서 이중 연결 리스트에서는 삭제할 노드의 참조를 알고 있다면 앞 노드를 다시 찾지 않고 O(1)에 삭제할 수 있습니다. 대신 노드마다 참조를 하나 더 저장해야 하며 삽입과 삭제 시 양쪽 연결을 모두 관리해야 합니다.

head와 tail의 역할

head와 함께 마지막 노드를 가리키는 tail을 관리하면 리스트 끝에도 바로 접근할 수 있습니다.

head          tail
 ↓             ↓
[10] → [20] → [30] → null

단일 연결 리스트에서도 tail이 있다면 마지막 노드를 찾는 순회 없이 새 노드를 끝에 연결할 수 있습니다. 추가한 노드를 새로운 tail로 지정하면 끝 삽입은 O(1)입니다.

그렇다면 끝 삭제도 어떨까요? 마지막 노드를 삭제한 뒤에는 그 앞 노드가 새로운 tail이 되어야 합니다. 하지만 단일 연결 리스트의 tail에는 이전 노드로 가는 참조가 없습니다. 결국 head부터 마지막의 바로 앞 노드까지 찾아가야 하므로 끝 삭제는 O(n)입니다.

이중 연결 리스트에서는 tail.prev로 이전 노드에 접근할 수 있어 끝 삭제도 O(1)에 처리할 수 있습니다.

연결 리스트의 시간 복잡도

연산	단일 연결 리스트	이중 연결 리스트	조건과 이유
인덱스로 접근	O(n)	O(n)	해당 위치까지 연결을 따라가야 한다.
값으로 탐색	O(n)	O(n)	원하는 값이 나올 때까지 확인해야 한다.
전체 순회	O(n)	O(n)	모든 노드를 한 번씩 방문한다.
맨 앞 삽입/삭제	O(1)	O(1)	첫 노드 주변의 연결과 head를 바꾼다.
맨 뒤 삽입	O(1)	O(1)	tail로 마지막 노드에 바로 접근한다.
맨 뒤 삭제	O(n)	O(1)	단일 연결 리스트는 이전 노드를 찾아야 한다.
알고 있는 노드 바로 뒤에 삽입	O(1)	O(1)	해당 위치의 연결만 바꾼다.
알고 있는 노드 삭제	O(n)	O(1)	단일 연결 리스트는 앞 노드도 알고 있다면 O(1)이다.

tail을 관리하지 않는다면 끝 삽입에도 마지막 노드를 찾는 O(n)의 순회가 필요합니다.

배열과 비교하면

배열은 연속된 공간에 값을 저장하고 연결 리스트는 노드 사이의 연결로 순서를 표현합니다. 그래서 배열에서는 중간에 값을 추가하거나 삭제할 때 뒤 원소들을 이동해야 하지만 연결 리스트에서는 필요한 노드의 연결을 바꾸기만 하면 됩니다.

하지만 노드마다 연결 정보를 저장해야 하고 원하는 위치까지 차례로 이동해야 합니다. 배열처럼 인덱스를 이용해 임의의 위치에 자주 접근하는 작업에는 불리합니다.

비교 기준	배열	연결 리스트
순서를 표현하는 방식	연속된 저장 공간의 위치	노드 사이의 연결
인덱스 접근	위치를 계산해 바로 접근한다. O(1)	해당 위치까지 연결을 따라간다. 최악 O(n)
중간 삽입,삭제	순서를 유지하기 위해 뒤 원소들을 이동한다.	필요한 노드를 찾은 뒤 연결을 바꾼다.
연결 정보	원소마다 이웃 원소의 참조를 저장할 필요가 없다.	각 노드에 다음 노드 또는 이전, 다음 노드의 참조를 저장한다.

앞에서 값을 꺼내고 뒤에 값을 넣는 작업 대기열은 연결 리스트를 활용할 수 있는 예입니다. head에서 삭제하고 tail 뒤에 삽입하면 매번 전체 리스트를 순회할 필요가 없습니다.

반대로 “100번째 값을 읽기”처럼 위치를 지정해 접근하거나, 삭제할 값을 매번 처음부터 찾아야 한다면 연결 리스트의 장점이 줄어듭니다. 삽입과 삭제가 자주 일어난다는 사실만으로 선택하기보다 작업할 노드를 어떻게 찾는지까지 함께 살펴보는 것이 좋습니다.

정리

연결 리스트는 각 노드가 다음 노드를 가리키는 방식으로 순서를 표현합니다. 그래서 노드를 삽입하거나 삭제할 때 뒤에 있는 원소들을 옮기지 않고 연결을 바꿀 수 있습니다.

하지만 원하는 노드에 도달하는 과정은 별도의 처리가 필요합니다. 연결 변경에 필요한 노드를 이미 알고 있다면 O(1)에 처리할 수 있지만 위치나 값으로 노드를 찾아야 한다면 최악의 경우 O(n)이 걸립니다.