[궁금시리즈] 4-2. List는 내부적으로 어떻게 동작할까?

C#에서 가장 많이 사용하는 컬렉션을 하나만 꼽으라면 대부분 List를 선택할 것이다.

List<int> numbers = new();

numbers.Add(10);
numbers.Add(20);
numbers.Add(30);

사용법은 매우 간단하다.

하지만 내부에서는 어떤 일이 일어날까?

배열은 크기가 고정되어 있는데, List는 어떻게 계속 데이터를 추가할 수 있을까?

이번 글에서는 List의 내부 구조와 동작 원리를 알아보자.

---

List는 배열(Array)로 만들어져 있다

많은 사람들이 List와 배열을 완전히 다른 자료구조라고 생각한다.

하지만 실제로는 그렇지 않다.

List의 내부에는 배열이 존재한다.

구조를 단순화하면 다음과 같다.

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는 다음과 같은 상황에 적합하다.

• 순서가 중요한 데이터
• 인덱스로 접근이 많은 경우
• 대부분의 작업이 끝에 추가(Add)되는 경우

반대로

• 앞이나 중간에 자주 삽입·삭제한다면 LinkedList가 더 적합할 수 있다.
• 빠른 검색이 중요하다면 Dictionary<TKey, TValue>가 적합하다.

즉, List는 만능 컬렉션이 아니라 배열 기반 컬렉션이라는 특성을 이해하고 사용하는 것이 중요하다.

---

실제 .NET은 어떻게 구현되어 있을까?

실제 List도 내부적으로

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의 내부 구조를 이해하면 어떤 상황에서 적합한지, 언제 다른 컬렉션을 선택해야 하는지도 자연스럽게 판단할 수 있다.

다음 글에서는 **List는 왜 인덱스로 빠르게 접근할 수 있을까?**를 알아보며 배열의 메모리 구조와 시간 복잡도까지 함께 살펴보겠다.

---

핵심 정리

• List는 내부적으로 배열(T[])을 사용한다.
• Add()는 배열의 빈 공간에 데이터를 추가한다.
• 배열이 가득 차면 더 큰 배열을 만들고 기존 데이터를 복사한다.
• Capacity는 저장 가능한 크기, Count는 실제 저장된 개수이다.
• Add()는 대부분 빠르지만, 중간 삽입과 삭제는 요소 이동 때문에 비용이 크다.
• 대량의 데이터를 저장할 예정이라면 초기 Capacity를 지정하면 재할당 비용을 줄일 수 있다.
• foreach 중 컬렉션 수정이 예외를 발생시키는 이유는 내부의 _version 관리 때문이다.