[궁금시리즈] 4-6. LinkedList는 언제 사용하는 것이 좋을까?
앞에서 List
[10][20][30][40]
여기에
15
를 두 번째 위치에 삽입하면 어떻게 될까? 결과는
[10][15][20][30][40]
이 되어야 한다.
하지만 배열은 연속된 메모리를 사용하기 때문에 20, 30, 40을 모두 한 칸씩 뒤로 이동해야 한다. 즉, 중간 삽입과 삭제가 많아질수록 List<T>는 비효율적이다. 이 문제를 해결하기 위해 만들어진 자료구조가 LinkedList이다.
LinkedList는 무엇일까?
LinkedList는
데이터를 연속된 메모리가 아니라 노드(Node)로 연결해서 저장하는 자료구조이다.
예를 들어
10
↓
20
↓
30
↓
40
처럼 저장하는 것이 아니라 실제로는
┌────┐ ┌────┐ ┌────┐
│10 │──▶ │20 │──▶ │30 │──▶ ...
└────┘ └────┘ └────┘
각 노드가 다음 노드의 위치를 알고 있다.
Node란 무엇일까?
LinkedList에서 하나의 데이터를 Node라고 한다. Node는
class Node<T>
{
public T Value;
public Node<T> Next;
}
와 비슷한 구조를 가진다. 즉, 데이터 하나와 다음 노드의 주소를 함께 저장한다.
왜 삽입이 빠를까?
다음 상태를 보자.
10 → 20 → 30
여기에 15를 넣는다면 배열처럼 20, 30을 이동하지 않는다. 대신 포인터만 바꾼다.
10 → 15 → 20 → 30
실제로 바뀌는 것은
10.Next
↓
20
↓
15
뿐이다. 즉, 데이터 이동이 발생하지 않는다.
삭제도 마찬가지이다
다음 상태에서
10 → 20 → 30 → 40
20을 삭제하면 배열처럼 30, 40을 앞으로 복사하지 않는다. 그냥
10.Next
↓
30
으로 변경하면 끝이다.
그렇다면 LinkedList가 List보다 좋은 걸까?
그렇지 않다.
이번에는 30을 찾는다고 생각해 보자.
List는
list[2]
한 번이면 된다.
하지만 LinkedList는
10
↓
20
↓
30
순서대로 이동해야 한다. 즉, 인덱스로 바로 접근할 수 없다.
실제 메모리는 어떻게 생겼을까?
많은 사람들이 LinkedList도 메모리에
10
20
30
40
순서대로 저장될 것이라고 생각한다. 하지만 실제로는
메모리
100번지
↓
30
----------------
200번지
↓
10
----------------
500번지
↓
40
----------------
700번지
↓
20
처럼 여기저기에 흩어져 있을 수도 있다.
노드는 Next가 가리키는 주소를 따라가며 연결된다. 즉, LinkedList는 연속된 메모리를 사용할 필요가 없다.
그래서 CPU Cache에도 영향이 있다
배열은 메모리에 연속적으로 저장된다.
[10][20][30][40]
CPU는 한 번 메모리를 읽을 때 주변 데이터도 함께 가져오는 특성이 있다. 그래서
10
↓
20
↓
30
을 매우 빠르게 읽을 수 있다.
반면 LinkedList는
10
↓
700번지
↓
30
↓
1200번지
↓
20
처럼 메모리 여기저기를 이동해야 한다.
이 때문에 CPU Cache 효율이 떨어진다. 실제로는 단순 탐색이라면 LinkedList보다 List가 더 빠른 경우가 많다.
.NET의 LinkedList는 조금 다르다
실제 .NET의 LinkedList
class LinkedListNode<T>
{
public T Value;
public LinkedListNode<T> Next;
public LinkedListNode<T> Previous;
}
와 비슷한 구조를 가진다.
그래서 앞으로도 이동할 수 있고, 뒤로도 이동할 수 있다. 이 덕분에 현재 노드 기준으로 앞뒤 삽입과 삭제를 매우 효율적으로 수행할 수 있다.
실무에서는 언제 사용할까?
LinkedList는 다음과 같은 상황에 적합하다.
- 특정 노드를 이미 알고 있는 상태에서
- 중간 삽입과 삭제가 매우 자주 발생하는 경우
예를 들어
- LRU Cache
- 작업 스케줄러
- Undo/Redo 히스토리 관리
- 일부 게임 엔진의 업데이트 리스트
등에서 사용된다.
하지만
일반적인 데이터 목록이라면
List
실무에서 자주 하는 오해
많은 개발자가
“삽입과 삭제가 O(1)이니까 LinkedList가 더 빠르겠네.”
라고 생각한다. 하지만 중요한 조건이 있다. 삽입하거나 삭제할 위치를 이미 알고 있을 때만 O(1) 이다. 예를 들어
10 → 20 → 30 → 40
에서 30을 삭제하려면 먼저 30을 찾아야 한다.
찾는 과정은
10
↓
20
↓
30
처럼 순차적으로 이동해야 한다. 즉, 노드를 찾는 비용은 O(n)이다. 그래서 대부분의 애플리케이션에서는
삽입과 삭제 비용보다 탐색 비용이 더 많이 발생한다. 이 때문에 실제 실무에서는 LinkedList보다 List가 훨씬 자주 사용된다.
List와 LinkedList는 어떻게 선택할까?
| 상황 | 적합한 컬렉션 |
| 인덱스로 자주 접근한다 | List |
| 순차 탐색이 많다 | List |
| 대부분 끝에 추가한다 | List |
| 특정 노드를 기준으로 삽입·삭제가 많다 | LinkedList |
| 앞뒤 양방향 이동이 필요하다 | LinkedList |
즉, LinkedList<T>는 List<T>를 대체하는 컬렉션이 아니라 특정 문제를 해결하기 위한 자료구조이다.
마무리
LinkedList
핵심 정리
- LinkedList
는 노드(Node)를 연결하여 데이터를 저장한다. - 배열처럼 데이터를 이동하지 않아 특정 노드 기준 삽입·삭제는 O(1)이다.
- 인덱스로 바로 접근할 수 없으며 탐색은 O(n)이다.
- .NET의 LinkedList
는 이중 연결 리스트(Doubly Linked List)이다. - CPU Cache 효율은 일반적으로 List
가 더 좋다. - 대부분의 실무에서는 List
가 더 많이 사용되며, LinkedList 는 특수한 상황에서 선택하는 자료구조이다.