LinkedList 는 손을 잡고 선 줄이다

지금까지 본 자료구조는 속이 전부 배열이었습니다. List 도, Dictionary 도, HashSet 도 결국 칸이 한 줄로 붙어 있는 배열 위에 얹혀 있습니다.

칸이 붙어 있으면 좋은 점과 나쁜 점이 같이 옵니다.

• 좋은 점: 몇 번째 칸이든 곱셈과 덧셈 한 번으로 찾아갑니다.
• 나쁜 점: 중간에 하나 끼워 넣으면 뒤가 전부 한 칸씩 밀립니다.

밀리는 이유는 붙어 있어야 하기 때문입니다. 자리를 비워 두면 계산이 어긋납니다.

붙어 있는 것을 포기하면 밀 일도 없어집니다.

각자 다음 사람의 위치를 들고 있다

줄을 서는데 자리를 정해 두지 않고 손만 잡고 있다고 해 봅시다. 어디에 서 있든 상관없습니다. 내 다음이 누구인지만 알면 줄이 됩니다.

칸 하나를 노드라고 부릅니다. 노드는 값 하나와 다음 노드의 주소를 들고 있습니다. C# 의 LinkedList 는 앞 노드의 주소도 같이 들고 있어서 양쪽으로 갈 수 있습니다.

LinkedList 는 이렇게 생겼다

using System.Collections.Generic;

LinkedList<int> list = new LinkedList<int>();

list.AddLast(1);
list.AddLast(2);
list.AddLast(3);

Console.WriteLine(list.First.Value);    // 1
Console.WriteLine(list.Last.Value);     // 3

대괄호로 꺼내는 방법이 없습니다. list[1] 이 안 됩니다. 번호로 찾는 것이 싸지 않으니 아예 열어 두지 않았습니다.

• AddFirst / AddLast 앞이나 뒤에 붙이기
• AddBefore / AddAfter 어떤 노드의 앞이나 뒤에 끼우기
• Remove 빼기
• First / Last 양 끝 노드

First 가 값이 아니라 노드를 돌려주는 것을 봐 두세요. 값을 꺼내려면 .Value 를 한 번 더 붙입니다. 노드를 손에 쥐고 있어야 그 자리에서 끼우고 뺄 수 있기 때문입니다.

끼워 넣기는 손만 바꿔 잡으면 된다

LinkedListNode<int> node = list.First;

list.AddAfter(node, 99);

앞 노드가 가리키는 곳을 새 노드로 바꾸고, 새 노드가 원래 다음을 가리키게 합니다. 주소 두어 개만 고쳐 쓰면 끝입니다. 뒤에 몇 개가 있든 상관없습니다.

순서가 중요합니다. 새 노드가 먼저 다음을 가리키게 하고, 그다음 앞 노드를 바꿉니다. 반대로 하면 원래 다음을 가리키던 주소가 사라져서 뒤쪽을 통째로 잃습니다.

List 에서 같은 일을 하면 뒤가 전부 밀립니다. 만 개가 있으면 만 번 옮깁니다.

“노드를 알면” 이라는 조건이 중요합니다. n 번째에 끼우고 싶은데 노드를 안 들고 있으면, 그 노드를 찾으려고 처음부터 n 번 걸어가야 합니다. 그러면 싼 게 아닙니다.

고친 주소는 안 늘고 걸음만 늡니다. 두 숫자가 따로 논다는 게 핵심입니다.

그런데 대부분 List 가 이깁니다

이론상 LinkedList 가 유리해 보이는 상황에서도 실제로는 List 가 빠른 경우가 많습니다. 이유가 두 가지입니다.

노드마다 주소를 더 들고 있습니다. 값이 int 하나(4바이트)여도 앞뒤 주소를 들면 노드 하나가 그 몇 배가 됩니다. 담는 개수가 같아도 메모리를 훨씬 씁니다.

흩어져 있습니다. 앞에서 격자를 열 방향으로 훑으면 느려질 수 있다고 했습니다. CPU 는 값 하나를 읽을 때 그 주변을 한 덩어리로 가져다 둡니다. 배열은 다음 값이 이미 그 덩어리 안에 있습니다. LinkedList 는 다음 노드가 어디 있을지 모릅니다. 그래서 한 칸 갈 때마다 새로 읽어 와야 할 수 있습니다.

“뒤가 밀린다”는 것은 나빠 보이고 “주소만 고친다”는 것은 좋아 보이는데, 붙어 있는 값을 통째로 옮기는 일은 CPU 가 아주 잘하는 일입니다. 반면 흩어진 주소를 따라 뛰는 일은 잘 못하는 일입니다.

그래서 기본은 List 입니다. LinkedList 는 노드를 이미 손에 쥐고 있고 중간에서 넣고 빼는 일이 아주 많을 때에만 이야기가 됩니다.

이걸 알아 두는 이유는 LinkedList 를 쓰기 위해서가 아닙니다. 자료구조를 고르는 판단이 “이론상 몇 번 비교하나” 하나로 끝나지 않는다는 것이 요점입니다. 값이 메모리에 어떻게 놓여 있는지가 같이 걸립니다.

정리

• LinkedList 는 칸이 붙어 있지 않습니다. 노드마다 다음(과 앞) 노드의 주소를 들고 있습니다.
• 대괄호로 못 꺼냅니다. 번호로 찾으려면 처음부터 세어 가야 합니다.
• 노드를 손에 쥐고 있으면 중간에 끼우고 빼는 것이 주소 몇 개 고치는 일로 끝납니다.
• 노드를 모르면 그 노드를 찾는 데 이미 비용이 듭니다.
• 노드마다 주소를 더 들고, 흩어져 있어서 CPU 에 불리합니다.
• 기본은 List 입니다. LinkedList 는 조건이 맞을 때만 이야기가 됩니다.

자료구조를 고르는 기준은 결국 하나로 모입니다. 무엇을 자주 하는가 입니다. 번호로 꺼내는 일이 잦으면 붙어 있는 쪽, 내용으로 찾는 일이 잦으면 해시를 쓰는 쪽, 꺼내는 순서에 규칙이 있으면 그 규칙을 강제하는 쪽입니다. 담는 방법이 여러 가지인 이유가 이것입니다.