C# 자료 구조

① C#의 대표 자료 구조

• Array : 配列
• List : リスト
  • LinkedList
• Dictionary : 連想配列
• HashSet : ハッシュセット 중복을 허용하지 않는다.
• SortedSet : 중복 허용하지 않으며, 정렬된 순서로 요소 저장
• Tuple
• Queue
  • PriorityQueue
• Stack

---

② 동작에 따른 분류 - 삽입, 삭제, 검색, 정렬, 길이

삽입(挿入: そうにゅう, 追加:  ついか)

• 맨 뒤에 추가: List.Add() , HashSet.Add(), SortedSet.Add() void 반환

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

HashSet<int> set = new HashSet<int>();
set.Add(1);
set.Add(2);
set.Add(3);

SortedSet<int> idol = new SortedSet<int>();
idol.Add("kiki");
idol.Add("twice");

• 指定の位置への要素の追加 : List.Insert() void 반환

List<int> list = new List<int> {1,2,3,4};
list.Insert(2, 5);		// {1,2,5,3,4}

---

삭제(削除, さくじょ)

• 특정 인덱스 삭제: 先頭の要素の削除 List.RemoveAt() void 반환

List<int> list = new List<int>{1,2,3,4,5};
list.RemoveAt(0);	// {2,3,4,5}

• 특정 값 삭제: List.Remove(값), Dictionary.Remove(Key), SortedSet.Remove(값) void 반환

Dictionary<int, string> dic = new Dictionary<int, string>
{
    {1, "Alice"},
    {2, "Bruce"},
    {3, "Michel"}
};

dic.Remove(3); 	

//{
//	{1, "Alice"},
//	{2, "Bruce"}
//}

SortedSet<string> idol = new SortedSet<string>{"kiki", "heartstohearts"};

idol.Remove("kiki");

---

검색(検索, けんさく)

• 指定要素の検索 : List.Contains(), HashSet.Contains() true/false 반환
  • 검색 속도 : List 보다 HashSet이 빠름

List<int> list = new List<int>{1,2,3,4,5};
if(list.Contains(3)){
     Console.WriteLine("YES"); 
}
// YES

HashSet<int> set = new HashSet<int>{1,2,3,4,5};
if(set.Contains(3)){
     Console.WriteLine("YES"); 
}
// YES

• Dictionary key값으로 접근하기

Dictionary<int, string> dic = new Dictionary<int, string>();
dic[1] = "Alice";
dic[2] = "Bruce";
dic[3] = "Michel";

Console.WriteLine(dic[2]);	// Bruce
Consoel.WriteLine(dic[4]); 	// Error

• 요소의 위치 출력 : List<T>.IndexOf(idx) int 반환

---

정렬(整列, せいれつ)

• 오름차순 昇順に並べる : List.Sort() void 반환

List<int> list = new List<int>{5,2,3,1,4};
list.Sort(); 	// {1,2,3,4,5}

 

• 내림차순 降順 

// 가장 단순 but 비효율
List<int> list = new List<int>{1,2,3,4,5};
list.Sort();
list.Reverse();

// IComparable의 CompareTo 사용
list.Sort((a,b) => b.CompareTo(a));

// LINQ 사용
list = list.OrderByDescending((n => n)).ToList();

---

길이(長さ, ながさ)

• List<T>.Count, HashSet<T>.Count, Array.Length

---

③ 자료구조에 따른 분류

• Array vs List
• List vs HashSet vs SortedSet 
• Queue vs Stack
• Dictionary vs Tuple
• Priority Queue
• Linked List

---

Array vs List

	Array(array)	List(list)
길이 구하기 (1차원)	int arrayLength = array.Length;	int listLength = list.Count;
길이 구하기 (2차원)	int rowLength = array.GetLength(0);	int rowLength = list[0].Count;
Clear	길이 그대로, 값들만 0으로 초기화 Array.Clear(array, 0, array.Length);	길이 0으로! list.Clear();
Fill	Array.Fill(array, 10);	list.Foreach(x => x = 10);
Copy	Array.Copy(array, copyArray, array.Length);	List<int> copyList = new List<int>(list);
Remove	배열 길이 자체를 자를 순 없고, 새 배열 생성 array = array.Where(val => val != 3).ToArray();	list.Remove(3); list.RemoveAt(0);
Contains	bool contains = Array.Exist(array, x => x == 3);	bool contains = list.Contains(3);
IndexOf	int indexInArray = Array.IndexOf(array, 3);	int indexInList = list.IndexOf(3);
Sort	Array.Sort(array);	list.Sort();
Reverse	Array.Reverse(array);	list.Reverse();

---

List vs HashSet vs SortedSet

List	HashSet	SortedSet
중복 O, 정렬 기능 O	중복 허용 X, 정렬 기능 X	중복 허용 X, 정렬 된 채 저장
	검색, 삽입, 삭제 O(1)	검색, 삽입, 삭제 O(log n)
	빠른 검색, 중복 제거에 적합	항상 정렬된 상태로 유지해야 할 때 사용
	HashTable	이진 검색 트리

 

	List	HashSet	SortedSet
삽입	Add(값) Insert(인덱스, 값)	Add(값)	Add(값)
삭제	Remove(값) RemoveAt(인덱스) Clear()	Remove(값) Clear()	Remove(값) Clear()
검색	Contains(값), IndexOf(인덱스)	Contains(값)	Contains(값)
정렬	Sort(), Reverse()	필요시 LINQ사용 var sortedSet = hashSet.OrderBy(x=>x )	자동 정렬, Reverse()
길이	Count	Count	Count

---

Queue vs Stack

	Queue	Stack
삽입	Enqueue(값)	Push(값)
삭제	Dequeue(), Clear()	Pop(), Clear()
검색	Contains(값)	Contains(값)
정렬	정렬 X, LINQ사용해 새로운 리스트 반환	정렬 X, LINQ사용해 새로운 리스트 반환
길이	Count	Count

---

Dictionary vs Tuple

Dictionary	Tuple
Dictionary<Key, Value>	여러 개의 값을 하나의 객체로 묶는 자료형 Tuple<T1, T2, ... >
dic.Key dic.Value	tuple.Item1 tuple.Item2

 

	Dictionary	Tuple
삽입	dic[키] = 값
삭제	dic.Remove(키)
검색	dic.ContainsKey(키) dic.ContainsValue(값)
정렬	정렬 X, LINQ사용해 새로운 리스트 반환
길이	Count

 

---

Linked List<T>

원소를 저장할 때 그 다음 원소가 있는 위치를 함께 저장하는 것.

연결리스트로 구성되어 있다면 녹색 사람만 외우면, 나머지 순서를 다 알 수 있다.

---

Linked List<T>의 성질

• k 번째 원소를 확인/변경하기 위해 O(k)가 필요하다.
• 임의의 위치에 원소를 추가/ 제거하기 위해서는 O(1)이 필요하다.
• 원소들이 메모리 상에 연속해 있지 않아 Cache hit rate가 낮지만 할당이 다소 쉽다.

k 번째를 탐색하려면 차례로 탐색해야 하니까.

---

연결리스트의 종류

• 단일 연결 리스트 (Singly Linked List)
• 이중 연결 리스트 (Double Linked List)
• 원형 연결 리스트(Circular Linked List)

---

PriorityQueue<T>

pop할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

• 원소의 추가가 O(log N)
• 우선순위가 가장 높은 원소의 확인이 O(1)
• 우선순위가 가장 높은 원소의 제거가 O(log N)