1. List<T>
C#을 하면서 가장 많이 사용하는 클래스라고 생각된다.
List라고한다면 Array List와 Linked List가 떠오르는데 정답은 Array List이다.
Remarks
The List class is the generic equivalent of the ArrayList class. It implements the IList generic interface by using an array whose size is dynamically increased as required.
You can add items to a List by using the Add or AddRange methods.
The List class uses both an equality comparer and an ordering comparer.
ArrayList와 다른점은 ArrayList는 Object를 저장하여 어떤 자료형이라도 저장 할 수 있지만 박싱과 언박싱이라는 큰 성능상의 문제가 있다. 이것을 해결한 것이 템플릿을 이용한 List이다.
처음부터 자료형을 정하기 때문에 ArryList와 비교해 유연하지 못하지만, 박싱과 언박싱을 피할수 있다. 이 제네릭 클래스 List의 강력한 기능 중 하나가 Random Access이다.
Random Access란?
데이터가 저장되어있는 메모리에 특정 인덱스로 접근 하는 것을 뜻한다. 대표적으로 Array가 있다.
Sequential access란?
데이터에 접근할 시 Root인덱스부터 순차적으로 검색하여 데이터에 접근 하는것을 뜻한다. 대표적으로 Linked list가 있다.
그럼 대표적인 오퍼레이션을 살펴보자.
1. Add()
작업속도는 O(1)
특정 상황에따라 추가적인 작업을 한다.
기본적으로 데이터 저장공간 Array이므로 저장공간에 한계가 있다. 이 저장공간이 가득찰때마다 2배씩 늘린 저장공간을 다시생성해 copy하게된다. 이 경우엔 O(n)이 소요된다. 저장공간을 늘리는 작업은 코스트가 꽤 높지만 이 알고리즘은 꽤 효율적으로 작동한다고 한다.
2. Remove()
작업속도는 O(n)
특정 자료가 삭제될시 배열에 빈공간이 남게된다. 물론 이것을 그냥 방치하면 여러가지 논리적 오류가 발생하기 쉽게된다. 그러므로 삭제된 데이터의 뒷부분을 모두 한칸씩 앞으로 당겨오는 작업이 필요로 한다.
3. Search
- [] : 작업속도는 O(1)
위에서 설명한 랜덤 엑세스가 가능하므로 특정 인덱스의 데이터를 손쉽게 접근할수 있다.
- IndexOf() : 하지만 인덱스가 아닌 데이터의 내용으로 검색할 시 O(n)이 필요로 하게된다.
4. Clear()
작업속도는 O(n)
List를 순회하며 데이터를 삭제한다. 이 메소드로는 List의 용량까지 초기화 되지는 않는다.
2. Dictionary<TKey, TValue>
해시테이블로 구현되어있지만 키 충돌을 허용하지 않는다.
이 해쉬테이블은 List로
1. Add()
일반적인 경우엔 O(1)이지만 Dictionary도 마찬가지로 해시 테이블의 용량을 늘리는 작업을 할 시 O(n)이 걸린다.
2. Remove()
작업속도는 O(1)에 가깝다.
단지 해시테이블에 있는 값을 찾아가 데이터를 삭제하면 되기 때문에 매우 빠르게 작동한다.
3. Search
- [] 및 ContainsKey(TKey)
작업속도는 O(1)에 가깝다.
사실은 이 Dictionary를 구성하고 있는 해시 알고리즘에 영향을 받는다.
- ContainsValue(TValue)
작업속도는 O(n)이다.
Dictionary를 순회하여 찾고자 하는 데이터와 비교하게 된다.
4. Clear
작업속도는 O(n)이다.
Dictionary를 순회하며 모든 데이터를 삭제하게된다.
출처 : https://docs.microsoft.com/en-us/dotnet/api/System.Collections.Generic.List-1?view=netframework-4.8