[궁금시리즈] 4-2. List는 내부적으로 어떻게 동작할까?
들어가며
C#에서 가장 많이 사용하는 컬렉션을 하나만 꼽으라면 대부분 List<T>를 선택할 것이다.
List<int> numbers = new();
numbers.Add(10);
numbers.Add(20);
numbers.Add(30);
사용법은 매우 간단하다.
하지만 내부에서는 어떤 일이 일어날까?
배열은 크기가 고정되어 있는데, List<T>는 어떻게 계속 데이터를 추가할 수 있을까?
이번 글에서는 List<T>의 내부 구조와 동작 원리를 확인한다.
List는 배열(Array)로 만들어져 있다
많은 사람들이 List와 배열을 완전히 다른 자료구조라고 생각한다.
하지만 실제로는 그렇지 않다.
List<T>의 내부에는 배열이 존재한다.
구조를 단순화하면 다음과 같다.
class List<T>
{
private T[] _items;
private int _count;
}
여기서
- _items는 실제 데이터를 저장하는 배열
- _count는 현재 저장된 데이터 개수
를 의미한다.
즉, List는 배열을 더 편리하게 사용할 수 있도록 감싼 클래스(Wrapper)라고 볼 수 있다.
Add()를 호출하면 어떻게 될까?
다음 코드를 보자.
List<int> numbers = new();
numbers.Add(10);
numbers.Add(20);
numbers.Add(30);
내부적으로는 다음과 같은 일이 발생한다.
_items
┌────┬────┬────┬────┐
│ │ │ │ │
└────┴────┴────┴────┘
첫 번째 추가
┌────┬────┬────┬────┐
│ 10 │ │ │ │
└────┴────┴────┴────┘
_count = 1
두 번째
┌────┬────┬────┬────┐
│10 │20 │ │ │
└────┴────┴────┴────┘
_count = 2
세 번째도 같은 방식이다.
즉, 배열의 다음 빈 공간에 데이터를 저장하고 _count만 증가시킨다.
배열이 꽉 차면?
가장 중요한 부분이다. 다음 상태를 보자.
┌────┬────┬────┬────┐
│10 │20 │30 │40 │
└────┴────┴────┴────┘
여기서
numbers.Add(50);
를 호출하면 더 이상 저장할 공간이 없다.
배열은 크기를 늘릴 수 없으므로 새로운 배열을 만든다.
기존
[10][20][30][40]
↓
새 배열 생성
[ ][ ][ ][ ][ ][ ][ ][ ]
그리고 기존 데이터를 모두 복사한다.
[10][20][30][40][ ][ ][ ][ ]
마지막으로
[10][20][30][40][50][ ][ ][ ]
를 저장한다.
왜 두 배로 늘릴까?
많은 사람들이 궁금해하는 부분이다. 왜
4
↓
5
칸만 늘리지 않을까?
만약 Add할 때마다 배열을 하나씩 늘린다면
1
↓
2
↓
3
↓
4
↓
5
매번
- 새 배열 생성
- 데이터 복사
가 반복된다.
데이터가 10만 개라면 복사 비용이 엄청나게 증가한다.
그래서 대부분의 List는
4
↓
8
↓
16
↓
32
↓
64
처럼
용량(Capacity)을 두 배씩 증가시킨다.
덕분에 배열 복사는 자주 발생하지 않는다.
Count와 Capacity는 다르다
많은 개발자가 이 둘을 혼동한다.
예를 들어
List<int> list = new();
처음 상태는
Count = 0
Capacity = 4
이다.
여기서
list.Add(10);
를 하면
Count = 1
Capacity = 4
가 된다.
즉,
- Count는 실제 저장된 개수
- Capacity는 저장 가능한 최대 개수
이다.
Capacity를 미리 지정할 수도 있다
예를 들어
1만 개의 데이터를 저장할 것이 확실하다면
List<Player> players = new(10000);
처럼 생성할 수 있다.
그러면 중간에
배열 생성
↓
복사
↓
재할당
이 반복되지 않는다.
대량의 데이터를 다룰 때는 성능 향상에 도움이 될 수 있다.
중간 삽입은 왜 느릴까?
다음 리스트를 보자.
[10][20][30][40]
여기에
15
를 두 번째 위치에 넣는다면
[10][15][20][30][40]
가 되어야 한다.
하지만 배열은 연속된 메모리 공간을 사용하므로 20, 30, 40을 모두 한 칸씩 뒤로 이동해야 한다.
20 →
30 →
40 →
즉, 중간 삽입과 삭제는 데이터 이동이 필요하기 때문에 비용이 크다.
반면 맨 뒤에 추가하는 Add()는 대부분 빈 공간에 저장만 하면 되므로 훨씬 빠르다.
실무에서는 언제 List가 적합할까?
List<T>는 다음과 같은 상황에 적합하다.
- 순서가 중요한 데이터
- 인덱스로 접근이 많은 경우
- 대부분의 작업이 끝에 추가(Add)되는 경우
반대로
- 앞이나 중간에 자주 삽입·삭제한다면 LinkedList<T>가 더 적합할 수 있다.
- 빠른 검색이 중요하다면 Dictionary<TKey, TValue>가 적합하다.
즉, List는 만능 컬렉션이 아니라 배열 기반 컬렉션이라는 특성을 이해하고 사용하는 것이 중요하다.
실제 .NET은 어떻게 구현되어 있을까?
실제 List<T>도 내부적으로
private T[] _items;
private int _size;
private int _version;
와 같은 필드를 가지고 있다.
- _items : 실제 데이터를 저장하는 배열
- _size : 현재 저장된 요소 개수
- _version : 컬렉션이 수정되었는지 추적하는 값
특히 _version은 foreach와 관련이 있다.
foreach (var item in list)
{
list.Add(100);
}
이 코드는 실행 중에
Collection was modified; enumeration operation may not execute.
예외가 발생한다.
이는 foreach가 순회 중 컬렉션이 변경되는 것을 _version으로 감지하기 때문이다.
이 부분은 foreach와 Enumerator를 다룰 때 다시 자세히 살펴보겠다.
마무리
List<T>는 새로운 자료구조가 아니라 배열을 기반으로 동작하는 동적 배열(Dynamic Array)이다.
배열의 빠른 인덱스 접근이라는 장점을 유지하면서, 필요할 때 내부 배열의 크기를 늘려 개발자가 직접 메모리를 관리하지 않아도 되도록 설계되었다.
다만 중간 삽입과 삭제에서는 요소를 이동해야 하므로 비용이 발생한다. 따라서 List<T>의 내부 구조를 이해하면 어떤 상황에서 적합한지, 언제 다른 컬렉션을 선택해야 하는지도 자연스럽게 판단할 수 있다.
다음 글에서는 List<T>는 왜 인덱스로 빠르게 접근할 수 있을까?를 알아보며 배열의 메모리 구조와 시간 복잡도까지 함께 살펴보겠다.
핵심 정리
- List<T>는 내부적으로 배열(T[])을 사용한다.
- Add()는 배열의 빈 공간에 데이터를 추가한다.
- 배열이 가득 차면 더 큰 배열을 만들고 기존 데이터를 복사한다.
- Capacity는 저장 가능한 크기, Count는 실제 저장된 개수이다.
- Add()는 대부분 빠르지만, 중간 삽입과 삭제는 요소 이동 때문에 비용이 크다.
- 대량의 데이터를 저장할 예정이라면 초기 Capacity를 지정하면 재할당 비용을 줄일 수 있다.
- foreach 중 컬렉션 수정이 예외를 발생시키는 이유는 내부의 _version 관리 때문이다.