C# List<T> Insert vs Add

사진 출처: Alison

보통 C# 프로그래밍을 할 때, List<T> 자료구조를 사용하는 경우가 있는데, 이 자료구조는 Add와 Insert라고 하는 두 가지 메서드로 자료구조에 원소를 추가하는 기능을 제공하고 있습니다. 그런데, 두 가지 메서드가 어떤 차이가 있을까? 하는 생각은 해보지 않으셨는지요. 물론 이런 생각이 머릿속에서 바로 직관적으로 해답을 찾고 해결해내실 수도 있겠지만, 그렇지 못한 분들도 계실 듯 하여 글을 조금 적어볼까 합니다.

우선, List<T> 자료구조는 배열을 기반으로 하는 리스트 구조입니다. 이 말은 무슨 말이냐 하면, 엄밀히 말하자면 내부 자료구조는 리스트가 아니라 배열입니다. 배열이긴 하지만, 우리는 리스트를 사용하듯이 사용할 수 있는 클래스라는 것이죠. 원소가 추가될 때마다 배열의 맨 마지막 자리에 원소가 추가되다가, 배열의 크기를 넘어서면 2배로 배열 크기를 늘려서 재할당하는 그런 식인 것입니다. 

이러한 내부의 진실을 알게 되면 조금 더 접근이 쉬운데, 일단은 우리의 화두인 Add, Insert 메서드의 사용 사례부터 봅시다.

List<Object> list = new List<Object>();

list.Add(value);

list.Insert(i, value);

Add, Insert의 사용법을 보면 눈치를 챘을 수도 있는데, 

- Add는 단순히 List<T> 자료구조의 내부에 있는 배열에 맨 마지막 자리에 원소를 추가하는 방식입니다. 

- Insert는 특정 위치에 원소를 추가하는 방식이구요. 따라서, Insert의 경우 i번째가 배열의 맨 마지막 자리가 아니라면 삽입할 위치 뒤에 있는 모든 원소가 뒤로 밀려나야 합니다. 따라서, O(n)의 시간이 걸리게 됩니다.

- 반면, Add는 그냥 단순히 맨 마지막에 원소를 집어넣는 것이라고 했지요? 따라서 O(1)의 시간이 걸립니다.

결론은, 특별한 위치에 원소를 집어넣어야 되는 상황이 발생하지 않는 한, 무조건 Add를 사용하라는 것입니다. 

(단순 원소 추가 기능을 필요로 할 때)