Unity 내일배움캠프 TIL 1104 | List의 동작 원리 | 배열과 List

cheeseonrose·2023년 11월 4일

C TIL Unity 내일배움캠프 스파르타 코딩클럽

Unity 내일배움캠프

목록 보기

71/89

💡 List

🍺 동작 원리

List가 내부적으로 연결 리스트로 구현되어 있어서 가변적인 크기를 갖는다고 생각했는데 아니었다!!
List의 동작 원리를 이해하기 위해 코드를 분석해보자
먼저 멤버 변수들을 살펴보자.
- 기본 용량은 4이다.
- 내부적으로 T[] 배열을 갖는다.

생성자에서는 빈 배열을 할당해준다.

List도 초기 선언 시 크기를 지정해줄 수 있다.
- 적당한 크기를 지정함으로써 List에 원소를 삽입/삭제할 때 효율을 증가시키는 것도 최적화의 방법 중 하나이다.
- 또한 미리 크기를 지정하면 새로운 배열을 생성할 일이 줄어들기 때문에 가비지 컬렉션 발생 확률을 낮출 수 있다.

Add 메서드에서는 현재 배열의 크기가 충분하다면 배열 사이즈를 1 증가시키고, 배열의 마지막에 아이템을 추가한다.
만약 배열이 꽉 찼다면 배열 크기를 다시 설정한다.

Grow 메서드를 통해 배열 크기를 1 증가시킨 뒤, Add 메서드로부터 넘겨 받은 아이템을 배열의 끝에 추가한다.

Grow 메서드에서는 현재 배열의 크기가 0이라면 초기에 설정해줬던 기본 배열 크기로 사이즈를 조정한다.
만약 빈 배열이 아니라면 현재 배열의 사이즈 * 2만큼 배열 크기를 증가시킨다.

Capacity 프로퍼티에서 용량 값에 따라 내부 배열을 배열을 설정한다.
만약 현재 배열의 용량보다 크기를 늘려야 한다면 새로운 배열을 생성하여 기존 배열의 값을 새 배열로 복사하는 동작을 한다.
- 따라서 우리는 List.Add()를 사용할 때 시간 복잡도가 O(1)이 아닌 O(n)이 되는 것을 알 수 있다.

🍻 배열과 List

List가 내부적으로 연결 리스트로 구현된다고 알고 있을 때는 당연히 배열보다 데이터 접근이 느릴 것이라고 생각했다.
하지만 List도 내부적으로 배열로 구현된다면 데이터 접근 시간에 차이가 있을까??

궁금한 건 해결해야 하니까 실험을 해보자
크기가 백만인 배열과 리스트를 각각 선언한 뒤, 해당 배열과 리스트를 순회하며 값을 가져와 sum에 더하는 코드를 작성했다.

public static void TestFunc()
{
	int[] arr = new int[1000000];
    List<int> list = new List<int>(1000000);
  
    for (int i = 0; i < arr.Length; i++)
    {
    	arr[i] = i;
        list.Add(i);
    }
  
    long sum = 0;
  
    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < arr.Length; i++) sum += arr[i];
    sw.Stop();
  
    long arrTime = sw.ElapsedMilliseconds;
    sum = 0;
  
    sw.Reset();
    sw.Start();
    for (int i = 0; i < list.Count; i++) sum += list[i];
    sw.Stop();
  
    long listTime = sw.ElapsedMilliseconds;
  
    Console.WriteLine($"Array Time : {(float)arrTime/1000}\tList Time : {(float)listTime /1000}");
    Console.WriteLine($"Diff : {(float)(listTime - arrTime)/1000}");
}