---
title: "LinkedList 는 손을 잡고 선 줄이다"
description: "칸이 붙어 있지 않고 각자 다음 사람의 위치를 들고 있습니다. 끼워 넣기는 싸지고 번호로 찾기는 비싸집니다."
author: "유니얼"
pubDate: 2026-09-08
category: "programming/csharp/collections"
tags: ["C#", "자료구조"]
canonical: https://blog.unialgames.com/posts/csharp-linked-list/
---
지금까지 본 자료구조는 속이 전부 배열이었습니다.
`List` 도, `Dictionary` 도, `HashSet` 도 결국 칸이 한 줄로 붙어 있는 배열 위에 얹혀 있습니다.
칸이 붙어 있으면 좋은 점과 나쁜 점이 같이 옵니다.
- 좋은 점: 몇 번째 칸이든 곱셈과 덧셈 한 번으로 찾아갑니다.
- 나쁜 점: 중간에 하나 끼워 넣으면 **뒤가 전부 한 칸씩 밀립니다.**
밀리는 이유는 붙어 있어야 하기 때문입니다. 자리를 비워 두면 계산이 어긋납니다.
> **붙어 있는 것을 포기하면 밀 일도 없어집니다.**
## 각자 다음 사람의 위치를 들고 있다
줄을 서는데 자리를 정해 두지 않고 **손만 잡고 있다**고 해 봅시다.
어디에 서 있든 상관없습니다. 내 다음이 누구인지만 알면 줄이 됩니다.
붙어 있음을 포기하고 화살표를 얻은 것.
칸 하나를 **노드**라고 부릅니다. 노드는 값 하나와 다음 노드의 주소를 들고 있습니다.
C# 의 `LinkedList` 는 앞 노드의 주소도 같이 들고 있어서 양쪽으로 갈 수 있습니다.
## LinkedList 는 이렇게 생겼다
```csharp
using System.Collections.Generic;
LinkedList list = new LinkedList();
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` 를 한 번 더 붙입니다.
노드를 손에 쥐고 있어야 그 자리에서 끼우고 뺄 수 있기 때문입니다.
## 끼워 넣기는 손만 바꿔 잡으면 된다
```csharp
LinkedListNode node = list.First;
list.AddAfter(node, 99);
```
앞 노드가 가리키는 곳을 새 노드로 바꾸고, 새 노드가 원래 다음을 가리키게 합니다.
**주소 두어 개만 고쳐 쓰면 끝입니다.** 뒤에 몇 개가 있든 상관없습니다.
순서가 중요합니다. **새 노드가 먼저 다음을 가리키게** 하고, 그다음 앞 노드를 바꿉니다.
반대로 하면 원래 다음을 가리키던 주소가 사라져서 뒤쪽을 통째로 잃습니다.
`List` 에서 같은 일을 하면 뒤가 전부 밀립니다. 만 개가 있으면 만 번 옮깁니다.
| | List | LinkedList |
| --- | --- | --- |
| 번호로 꺼내기 | 바로 | 처음부터 세어 간다 |
| 맨 뒤에 넣기 | 대체로 싸다 | 싸다 |
| 중간에 끼우기 | 뒤가 전부 밀린다 | 노드를 알면 주소만 고친다 |
| 중간에서 빼기 | 뒤가 전부 당겨진다 | 노드를 알면 주소만 고친다 |
| 메모리 | 값만 | 값 + 주소 두 개 |
**"노드를 알면"** 이라는 조건이 중요합니다.
`n` 번째에 끼우고 싶은데 노드를 안 들고 있으면, 그 노드를 찾으려고
처음부터 `n` 번 걸어가야 합니다. 그러면 싼 게 아닙니다.
**고친 주소는 안 늘고 걸음만 늡니다.** 두 숫자가 따로 논다는 게 핵심입니다.
## 그런데 대부분 List 가 이깁니다
이론상 `LinkedList` 가 유리해 보이는 상황에서도 실제로는 `List` 가 빠른 경우가 많습니다.
이유가 두 가지입니다.
**노드마다 주소를 더 들고 있습니다.** 값이 `int` 하나(4바이트)여도
앞뒤 주소를 들면 노드 하나가 그 몇 배가 됩니다. 담는 개수가 같아도 메모리를 훨씬 씁니다.
**흩어져 있습니다.** 앞에서 격자를 열 방향으로 훑으면 느려질 수 있다고 했습니다.
CPU 는 값 하나를 읽을 때 그 주변을 한 덩어리로 가져다 둡니다.
배열은 다음 값이 이미 그 덩어리 안에 있습니다. `LinkedList` 는 다음 노드가 어디 있을지 모릅니다.
그래서 한 칸 갈 때마다 새로 읽어 와야 할 수 있습니다.
"뒤가 밀린다"는 것은 나빠 보이고 "주소만 고친다"는 것은 좋아 보이는데,
붙어 있는 값을 통째로 옮기는 일은 CPU 가 아주 잘하는 일입니다.
반면 흩어진 주소를 따라 뛰는 일은 잘 못하는 일입니다.
**그래서 기본은 `List` 입니다.** `LinkedList` 는 노드를 이미 손에 쥐고 있고
중간에서 넣고 빼는 일이 아주 많을 때에만 이야기가 됩니다.
이걸 알아 두는 이유는 `LinkedList` 를 쓰기 위해서가 아닙니다.
**자료구조를 고르는 판단이 "이론상 몇 번 비교하나" 하나로 끝나지 않는다**는 것이 요점입니다.
값이 메모리에 어떻게 놓여 있는지가 같이 걸립니다.
## 정리
- `LinkedList` 는 칸이 붙어 있지 않습니다. 노드마다 다음(과 앞) 노드의 주소를 들고 있습니다.
- 대괄호로 못 꺼냅니다. 번호로 찾으려면 처음부터 세어 가야 합니다.
- 노드를 손에 쥐고 있으면 중간에 끼우고 빼는 것이 주소 몇 개 고치는 일로 끝납니다.
- 노드를 모르면 그 노드를 찾는 데 이미 비용이 듭니다.
- 노드마다 주소를 더 들고, 흩어져 있어서 CPU 에 불리합니다.
- 기본은 `List` 입니다. `LinkedList` 는 조건이 맞을 때만 이야기가 됩니다.
자료구조를 고르는 기준은 결국 하나로 모입니다.
**무엇을 자주 하는가** 입니다. 번호로 꺼내는 일이 잦으면 붙어 있는 쪽,
내용으로 찾는 일이 잦으면 해시를 쓰는 쪽, 꺼내는 순서에 규칙이 있으면 그 규칙을
강제하는 쪽입니다. 담는 방법이 여러 가지인 이유가 이것입니다.