[C#] 컬렉션

Table of Contents

컬렉션이란? #

C#에서 지원하는 자료구조 클래스이다. C++의 컨테이너와 비슷하다.
컬렉션은 제네릭(Generic) 과 논제네릭(Non-Generic) 으로 나뉜다.
- 논제네릭은 object 형식을 사용해서 데이터를 관리하기 때문에 박싱과 언박싱이 잦아 성능 문제가 있어서 제네릭 컬렉션을 사용한다.

특징	Generic	Non-Generic
인덱스	List<T>	Array, ArrayList
키 - 값 쌍	Dictionary<TKey,TValue>	Hashtable
FIFO	Queue<T>	Queue
LIFO	Stack<T>	Stack
순서대로 엑세스	LinkedList<T>
정렬된 컬렉션	SortedList<TKey,TValue>	SortedList
수학함수용 집합	HashSet<T>

불변성과 가변성 #

불변성(Invariance)
- 변경할 수 없는. 인스턴스가 생성된 후 값을 변경할 수 없는 타입이다.
- 예: string
가변성(Variance)
- 변경할 수 있는. 인스턴스가 생성된 후 값이 변경될 수 있는 타입이다.
- 예: StringBuilder

여기서는 제네릭의 가변성을 살펴본다.
- 가변성은 암묵적으로 레퍼런스를 변환할 수 있는 능력이므로, Value Type에는 사용할 수 없고, Reference Type에만 적용된다.
- 타입 T 파라미터를 <out T>로 사용하면 공변성이 되고, <in T>로 사용하면 반공변성이 되며, in이나 out 없이 <T>로 사용하면 불변성이 된다.
- 공변성을 지원하는 타입
  - IEnumerable<out T>, IEnumerator<out T>, IQueryable<out T>, Func<out T> 등
- 반공변성을 지원하는 타입
  - IComparer<in T>, IComparable<in T>, IEqualityComparer<in T>, Action<in T> 등

속성	특징	파라미터
불변성	동일 타입만 할당 가능	`<T>`
가변성 - 공변성(Covariance)	상위 타입 할당 가능	`<out T>`
가변성 - 반공변성(Contravariance)	하위 타입 할당 가능	`<in T>`

class Animal
{
    public int Age { get; set; }
    public void Move() { }
}
class Dog : Animal
{
    public void Bark() { }
}
class K9 : Dog
{
    public void FindDrug() { }
}
 
// 제네릭 인터페이스: Covariance 
interface ICreate<out T>
{
    T Create();
}

class DogFactory : ICreate<Dog>
{
    public Dog Create()
    {
        return new Dog();
    }
}

// 제네릭 인터페이스: Contravariance
interface ITest<in T>
{
    void Run(T t);
}

class AnimalTest : ITest<Animal>
{
    public void Run(Animal t)
    {
        t.Move();
    }
}

class Main
{
    public void Run()
    {
        ICreate<Animal> creator = (ICreate<Dog>)new DogFactory();
        Animal ani = creator.Create();
        ani.Move();

        ITest<Dog> d = (ITest<Animal>)new AnimalTest();
        d.Run(new Dog());
        d.Run(new K9());
    }
}

class AnimalComparer : IComparer<Animal>
{
    int IComparer<Animal>.Compare(Animal a, Animal b)
    {
        if (a == null) return b == null ? 0 : -1;
        return b == null ? 1 : a.Age.CompareTo(b.Age);
    }
}

class Main
{
    public void Run()
    {
        // covariance 
        IEnumerable<Animal> animals = new List<Dog>() { new Dog() };
        animals.GetEnumerator().Current.Move();
 
        // contravariance 
        IComparer<Dog> dogComparer = new AnimalComparer();
        Dog dogA = new Dog { Age = 10 };
        Dog dogB = new Dog { Age = 10 };
        int result = dogComparer.Compare(dogA, dogB);
    }
}

List<T> #

내부적으로는 배열을 사용한다. 현재 크기의 2배로 늘리면서 재할당한다.
메모리가 순차적으로 할당이 된다. 그래서 불연속적인 메모리 할당 보다는 순차 접근이 빠르다. (캐시에 참조 지역성의 원리에 따라서 저장이 함께 되므로)
대신 인덱스로 접근하기 때문에 임의 접근은 빠르다.
중간에 삽입, 삭제가 효율적이지 않다. 원소들을 한칸씩 옮겨야 하기 때문이다. 그 과정에서 사본을 생성해야 하는 일도 발생한다.

메서드	기능
`Add(T)`	개체를 끝부분에 추가한다.
`AddRang(IEnumerable\<T\>)`	개체들을 끝부분에 추가한다.
`Insert(Int32, T)`	개체를 지정된 인덱스에 추가한다.
`Remove(T)`	처음 발견되는 해당 개체를 삭제한다.
`RemoveAll(Predicate\<T\>)`	해당 조건을 만족하는 개체들을 모두 삭제한다.
`Clear()`	개체들을 모두 제거한다.
`Contains(T)`	개체를 포함하고 있는지 확인한다.
`IndexOf(T)`	개체의 인덱스를 반환한다. 없으면 -1을 반환한다.
`Sort()`	개체들을 오름차순 혹은 내림차순으로 정렬한다.
`Reverse()`	개체들을 현재 상대의 반대로 만든다.

List<int> l = new List<int> { 1, 3, 2 };
        
l.Reverse(); // 2 3 1

l.Add(3); // 2 3 1 3

l.AddRange(new List<int> {6, 7, 8}); // 2 3 1 3 6 7 8

l.Remove(1); // 2 3 3 6 7 8

l.RemoveAll(x => x == 3); // 2 6 7 8 

bool res = l.Contains(9); // true

int idx = l.IndexOf(7); // 2

LinkedList<T> #

이중 연결리스트로 구현되어 있다.
포인터만 변경하면 되므로 중간 삽입, 삭제가 시간복잡도 1만에 이루어진다.
임의접근이 안 되기 때문에 처음부터 순차적으로 살펴봐야 한다.

메서드	기능
`AddFirst(T)`	개체를 리스트의 맨 앞에 추가한다.
`AddLast(T)`	개체를 리스트의 맨 뒤에 추가한다.
`AddBefore(LinkedListNode\<T\>, LinkedListNode\<T\>)`	개체를 해당 인덱스 위치 앞에 추가한다.
`AddAfter(LinkedListNode\<T\>, LinkedListNode\<T\>)`	개체를 해당 인덱스 위치 다음에 추가한다.
`Remove(T)`	처음 발견되는 해당 개체를 삭제한다.
`RemoveFirst()`	맨 앞의 개체를 제거한다.
`RemoveLast()`	맨 뒤의 개체를 제거한다.
`Clear()`	개체들을 모두 제거한다.
`Contains(T)`	개체를 포함하고 있는지 확인한다.

int[] input = new[] { 1 };
LinkedList<int> ll = new LinkedList<int> (input);

ll.AddFirst(0); // 0, 1

ll.AddLast(4); // 0, 1, 4

ll.AddAfter(ll.Find(1), new LinkedListNode<int>(3)); // 0, 1, 3, 4

ll.AddBefore(ll.Find(3), new LinkedListNode<int>(2)); // 0, 1, 2, 3, 4

ll.Remove(3);  // 0, 1, 2, 4

ll.RemoveFirst(); // 1, 2, 4

ll.RemoveLast(); // 1, 2

bool res = ll.Contains(1); // true

LinkedListNode<int> node = ll.First;
for (int i = 0; i < ll.Count; i++)
{
    Console.Write(node.Value + " "); // 1, 2
    node = node.Next;
}

Dictionary<TKey, TValue> #

인덱스 번호가 아닌, 키를 사용해서 값을 얻는다.

메서드	기능
`Add(TKey, TValue)`	개체를 추가한다.
`Remove(TKey)`	지정된 키를 가진 개체를 삭제한다.
`Remove(TKey, TValue)`	지정된 키를 가진 개체를 삭제하고, 두번째 필드에 값을 저장한다.
`Clear()`	개체들을 모두 제거한다.
`ContainsKey(TKey)`	키를 포함하고 있는지 확인한다.
`ContainsValue(TValue)`	값을 포함하고 있는지 확인한다.
`Reverse()`	개체들을 현재 상대의 반대로 만든다.

Dictionary<int, string> d = new Dictionary<int, string> { { 1, "First" }, { 2, "Second" }, { 3, "Third"} };
        
d.Add(4, "Forth"); // First, Second, Third, Forth

d.Remove(1); // Second, Third, Forth

d.Remove(2, out var deletedThis); // Third, Forth  |  deletedThis = Second

d[4] = "Fifth"; // Third, Fifth

bool resKey = d.ContainsKey(1); // false

bool resVal = d.ContainsValue("Fifth"); // true

컬렉션이란? #

불변성과 가변성 #

List<T> #

LinkedList<T> #

Dictionary<TKey, TValue> #

References #