[궁금시리즈] 4-7. 컬렉션마다 시간 복잡도가 다른 이유는 무엇일까?
지금까지 다양한 컬렉션을 살펴봤다.
- List
- Dictionary<TKey, TValue>
- HashSet
- Queue
- Stack
- LinkedList
그런데 많은 개발자가 컬렉션을 선택할 때
“검색이 빠른 건 Dictionary” “중복 제거는 HashSet”
정도로만 기억한다. 하지만 왜 빠른지 이해하지 못하면 상황에 맞는 컬렉션을 선택하기 어렵다. 이번 글에서는 각 컬렉션의 내부 구조와 시간 복잡도를 함께 비교하며 어떤 상황에서 어떤 컬렉션을 선택해야 하는지 정리해 본다.
시간 복잡도(Time Complexity)란?
시간 복잡도는
데이터의 개수가 증가할 때 연산 시간이 어떻게 증가하는지를 나타내는 방법이다.
예를 들어
데이터 10개
↓
1ms
데이터 100개
↓
10ms
데이터 1000개
↓
100ms
처럼 데이터가 증가할수록 수행 시간이 증가한다. 시간 복잡도는 이러한 증가 경향을 Big-O 표기법으로 표현한다.
대표적인 시간 복잡도
| 표기 | 의미 |
|---|---|
| O(1) | 데이터 개수와 관계없이 거의 일정 |
| O(log n) | 데이터가 늘어나도 증가 폭이 작음 |
| O(n) | 데이터 개수만큼 증가 |
| O(n²) | 데이터가 많아질수록 급격히 증가 |
컬렉션에서 가장 자주 보게 되는 것은 O(1)과 O(n)이다.
List
내부 구조
[ ][ ][ ][ ]
배열 기반이다. 인덱스 접근
list[100]
배열의 주소를 바로 계산하므로 O(1)이다.
검색
list.Contains(value)
처음부터 끝까지 비교한다.
O(n)
중간 삽입
list.Insert(index, value)
뒤의 데이터를 모두 이동한다.
O(n)
마지막 추가
list.Add(value)
대부분
O(1)
배열이 꽉 찼을 때만 복사가 발생한다.
그래서 평균적으로 O(1) 이다.
Dictionary<TKey, TValue>
내부 구조
Key
↓
Hash
↓
Bucket
Hash를 계산하여 바로 Bucket으로 이동한다.
검색
dictionary[key]
평균적으로 O(1)이다.
추가
Add()
역시 평균 O(1)이다.
Hash 충돌
충돌이 많으면
Bucket
↓
A
↓
B
↓
C
처럼 비교가 늘어난다.
이 경우 최악에는 O(n)까지 증가할 수 있다.
하지만 실제 .NET에서는 Hash 함수와 Bucket 크기를 조정하여 이러한 상황이 드물도록 관리한다.
HashSet
HashSet 역시 Dictionary와 거의 동일하다.
Value
↓
Hash
↓
Bucket
따라서 추가, 검색, 삭제 모두 평균적으로
O(1)
이다.
Queue
Queue는 원형 버퍼(Circular Buffer)를 사용한다.
Head
↓
[ ][ ][ ][ ]
↑
Tail
데이터를 이동하지 않고 Head와 Tail만 변경한다.
따라서
Enqueue()
↓
O(1)
Dequeue()
↓
O(1)
이다.
Stack
Stack도 배열 끝에서만 추가·삭제한다.
Push()
↓
O(1)
Pop()
↓
O(1)
이다.
LinkedList
LinkedList는
Node
↓
Next
↓
Next
로 연결된다.
특정 노드를 알고 있다면
삽입
↓
O(1)
삭제도
O(1)
이다.
노드를 찾아야 한다면
Head
↓
Next
↓
Next
순차적으로 이동해야 한다.
따라서 O(n) 이다.
컬렉션별 시간 복잡도 비교
| 연산 | List | Dictionary | HashSet | Queue | Stack | LinkedList |
| 인덱스 접근 | O(1) | - | - | - | - | - |
| 검색 | O(n) | 평균 O(1) | 평균 O(1) | O(n) | O(n) | O(n) |
| 마지막 추가 | 평균 O(1) | 평균 O(1) | 평균 O(1) | O(1) | O(1) | O(1) |
| 중간 삽입 | O(n) | - | - | - | - | O(1)* |
| 중간 삭제 | O(n) | - | - | - | - | O(1)* |
* 삽입·삭제할 노드를 이미 알고 있는 경우
시간 복잡도만 보고 선택하면 안 되는 이유
많은 개발자가
LinkedList
↓
삽입 O(1)
↓
무조건 빠르다.
라고 생각한다. 하지만
삽입하려는 위치를 찾는 비용은 O(n)이다.
반대로 List는 삽입 자체는 느리지만
CPU Cache 효율이 매우 좋다.
그래서 실제 성능은
List가 더 빠른 경우가 많다.
또 하나 흔한 오해는
Dictionary
↓
O(1)
↓
무조건 가장 빠르다.
라는 생각이다. Dictionary는 Hash 계산을 수행해야 하고, 메모리 사용량도 List보다 많다.
단순히 요소를 순서대로 순회하기만 한다면 오히려 List가 더 효율적이다.
시간 복잡도는 컬렉션 선택의 중요한 기준이지만, 메모리 구조와 실제 사용 패턴까지 함께 고려해야 한다.
실무에서는 어떻게 선택할까?
다음 기준으로 생각하면 된다.
| 목적 | 추천 컬렉션 |
|---|---|
| 순서대로 저장 | List |
| 빠른 검색 | Dictionary<TKey, TValue> |
| 중복 제거 | HashSet |
| 작업 대기열 | Queue |
| Undo / Call Stack | Stack |
| 특정 노드 기준 삽입·삭제 | LinkedList |
자료구조에는 절대적인 정답이 없다. 데이터를 어떻게 사용할 것인지에 따라 가장 적합한 컬렉션이 달라진다.
실제 .NET에서도 컬렉션을 용도에 맞게 사용한다
.NET 라이브러리 내부에서도 상황에 따라 서로 다른 컬렉션을 선택한다.
예를 들어 Dictionary<TKey, TValue>는 빠른 키 검색이 필요한 곳에서 사용되고, HashSet
즉, 컬렉션은 성능 차이만을 위한 도구가 아니라 의도를 코드로 표현하는 수단이기도 하다. 적절한 컬렉션을 선택하면 성능뿐 아니라 코드의 가독성과 유지보수성도 함께 향상된다.
마무리
컬렉션마다 시간 복잡도가 다른 이유는 내부 자료구조가 서로 다르기 때문이다. 배열을 사용하는 List<T>는 인덱스 접근이 빠르고, Hash를 사용하는 Dictionary<TKey, TValue>와 HashSet<T>는 검색이 빠르며, Queue<T>와 Stack<T>는 특정 순서를 보장하도록 설계되어 있다. LinkedList<T>는 노드를 연결하는 방식으로 삽입과 삭제를 최적화한다. 중요한 것은 특정 컬렉션이 항상 더 좋은 것이 아니라, 문제에 맞는 자료구조를 선택하는 것이다. 내부 구조를 이해하고 선택하는 습관은 성능과 코드 품질 모두를 높여 준다. 다음 장에서는 Generic을 기반으로 만들어진 컬렉션들이 실제 메모리를 어떻게 관리하는지를 넘어, 비동기 프로그래밍(Async/Await)으로 주제를 확장해 보겠다.
핵심 정리
- 시간 복잡도는 데이터가 증가할 때 연산 시간이 어떻게 변하는지를 나타낸다.
- List
는 인덱스 접근이 빠르지만 중간 삽입과 삭제는 느리다. - Dictionary<TKey, TValue>와 HashSet
는 평균적으로 O(1)의 검색 성능을 제공한다. - Queue
와 Stack 는 양끝에서만 데이터를 처리하도록 설계되어 대부분의 연산이 O(1)이다. - LinkedList
는 특정 노드를 알고 있을 때 삽입과 삭제가 O(1)이지만, 노드를 찾는 과정은 O(n)이다. - 컬렉션 선택은 시간 복잡도뿐 아니라 메모리 구조와 사용 목적까지 함께 고려해야 한다.