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

3 minute read

들어가며

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 관리 때문이다.

Tags:

Categories:

Updated: