[C#] 자료구조와 컬렉션

 

---

자료구조(Data Structure)

자료구조란?

자료구조는 컴퓨터 과학에서 데이터를 효율적으로 관리하기 위해 사용되는 다양한 방식과 체계입니다. 데이터의 조직, 관리, 저장 형식을 정의하며, 이를 통해 데이터에 빠르고 효율적으로 접근하고 조작할 수 있도록 합니다. 적절한 자료구조의 선택은 프로그램의 성능에 직접적인 영향을 미치므로 매우 중요합니다.

 

 

자료구조의 중요성

1. 효율적인 데이터 관리: 자료구조는 데이터를 체계적으로 저장하여 관리의 복잡성을 줄이고, 데이터를 빠르게 검색, 삽입, 삭제할 수 있게 해줍니다.

2. 성능 향상: 적절한 자료구조를 사용하면 프로그램의 성능이 크게 향상됩니다. 예를 들어, 배열과 링크드 리스트의 선택은 데이터 접근 속도와 메모리 사용량에 큰 차이를 가져올 수 있습니다.

3. 코드의 가독성 및 유지보수성: 잘 정의된 자료구조는 코드를 더 명확하고 이해하기 쉽게 만들어 유지보수를 용이하게 합니다.

4. 메모리 효율성: 자료구조는 메모리 사용을 최적화하여 프로그램이 제한된 리소스 내에서 원할하게 동작할 수 있도록 합니다.

 

 

 

---

컬렉션(Collections)

컬렉션이란?

C#에서 컬렉션은 객체의 모음을 관리하는 데 사용되는 데이터 구조를 의미합니다. 컬렉션은 데이터를 저장, 관리 및 조작하기 위한 메서드와 속성을 제공하여, 다양한 형태의 데이터를 효율적으로 처리할 수 있게 합니다.
C#의 컬렉션은 주로 System.Collections, System.Collections.Generic, System.Collections.Concurrent, System.Collections.Specialized 네임스페이스에 정의되어 있습니다.

 

주요 컬렉션의 분류

1. 비제네릭 컬렉션 (Non-Generic Collections)

2. 제네릭 컬렉션 (Generic Collections)

3. 동기화된 컬렉션 (Concurrent Collections)

4. 전문화된 컬렉션 (Specialized Collections)

 

 

 

성능상의 이유로 C#에서는 Generic Collections을 주로 사용합니다.

C#에서 제네릭 콜렉션(Generic Collections)을 사용하는 주된 이유는 성능 향상과 타입 안정성을 제공 1. 타입 안정성(Type Safety) 문제점(비제네릭 콜렉션): 비제네릭 콜렉션(예: ArrayList)은 'object 타입으로 데이터를 저장하기에 모든 데이터 타입을 저장할 수 있다는 장점이 있지만, 데이터 타입의 불일치로 인해 런타임 오류가 발생할 가능성이 있습니다. 예를 들어, 잘못된 타입의 데이터를 저장하거나, class형 데이터를 object 타입으로 저장, 이후 저장된 데이터를 int형 변수에 저장하려 할 경우 오류가 발생합니다. 해결책(제네릭 콜렉션): 제네릭 콜렉션을 컴파일 타임에 데이터 타입을 명시합니다. 이는 데이터 타입의 불일치를 방지하고, 코드의 안정성을 높여줍니다. 예를 들어, List<int>는 int타입만 저장할 수 있으며, 잘못된 타입의 데이터를 저장하려 하면 컴파일 오류가 발생합니다. 2. 성능 향상(Performance Improvement) 문제점(비제네릭 콜렉션): 비제네릭 콜렉션을 사용할 때는 데이터가 object 타입으로 저장되고, 이를 실제 타입으로 변환하기 위해 박싱(Boxing)과 언박싱(Unboxing)이 발생할 수 있습니다. 박싱과 언박싱은 추가적인 메모리 할당과 CPU 오버헤드를 발생시켜 성능 저하를 초래합니다. 해결책(제네릭 콜렉션): 제네릭 콜렉션을 사용하면 박싱과 언박싱이 필요 없습니다. 이는 데이터가 박싱을 통해 object타입으로 변환되는 것이 아닌 실제 타입으로 저장되고 처리되기 때문입니다. 따라서, 메모리와 CPU사용이 최적화되어 성능이 향상됩니다. [예제] List<int> num = new List<int>(); //컴파일 타임에 int형 타입 명시 num.Add(1); //박싱이 필요없음 int number = num[0]; //언박싱이 필요없음 3. 코드 재사용성(Code Reusability): 제네릭 콜렉션은 다양한 타입에 대해 재사용할 수 있는 코드를 작성할 수 있게 합니다. 이는 코드 중복을 줄이고, 유지보수를 용이하게 만들 수 있습니다. [예제] public void PrintItems<T>(List<T> items) {     foreach(T item in items)     {         Console,WriteLine(item);     } } List<int> intList = new List<int> {1, 2, 3}; List<string> stringList = new List<string> {"a", "b"}; //모든 타입에 대해 재사용 가능 PrintItems(intList); PrintItems(stringList);  4. 추가 설명 제네릭(Generic): 제네릭은 클래스, 구조체, 인터페이스, 메서드 등에서 데이터 타입을 일반화하여 사용할 수 있도록 하는 C#의 기능입니다. 박싱(Boxing): 값 타임(Value Type, 예:int, float, struct)의 데이터를 힙(Heap)메모리에 할당하고, 참조 타입(Reference  Type, 예: object)으로 변환하는 과정입니다. 박싱된 객체는 힙에 저장되며, 참조는 스택에 저장됩니다. 값 타입을 객체처럼 다룰 수 있어 object타입의 컬렉션 등에 저장할 수 있지만, 힙 메모리에 할당하고 데이터를 복사하는 과정에서 성능 오버헤드가 발생합니다. 언박싱(Unboxing):  참조 타입(Reference Type)으로 저장된 값을 값 타입(Value Type)으로 변환하는 과정입니다. 언박싱은 박싱의 반대 과정입니다. 참조 타입의 데이터가 값 타입으로 변환되며, 원래 데이터 타입으로 캐스팅 된 후 힙에 저장된 객체의 값을 스택에 복사합니다. 장점으로는 객체로 저장된 값을 원래의 값 타입으로 복원할 수 있지만, 단점으로는 값 타입으로 변환할 때 타입 캐스팅이 필요하며, 이 과정에서 성능 오버헤드가 발생할 수 있습니다. 또한 잘못된 타입으로 캐스팅하면 "InvalidCastException"오류가 발생할 수 있습니다.

 

 

 

 

---

제네릭 컬렉션의 종류

C#에서 제네릭 컬렉션은 'System.Collections.Generic' 네임스페이스에 포함되어 있으며, 데이터 타입을 매개변수화하여 강력한 타입 검사와 성능 최적화를 제공합니다. 주요 제네릭 컬렉션과 그 특성, 시간 복잡도는 다음과 같습니다. 각 제네릭 컬렉션의 자세한 내용은 따로 글을 적도록 하겠습니다.

 

 

1. List<T>

설명:

• 크기가 가변적인 배열로, 요소를 순차적으로 저장합니다.
• 내부적으로 배열을 사용하여 구현됩니다.
• 현재 용량이 새 요소를 추가할 수 없을 정도로 부족해질 경우, 리스트는 내부 배열의 크기를 현재 용량의 두 배씩 늘리게 됩니다.

 

시간 복잡도:

• 접근: O(1)
• 탐색: O(n)
• 삽입 / 삭제 (끝): O(1)
• 삽입 / 삭제 (중간): O(n)

 

예제:

List<int> list = new List<int>(); //int형 List 인스턴스 생성
list.Add(1); //삽입
int value = list[0]; //접근
list.Remove(0); //삭제

 

 

2. Dictionary<TKey, TValue>

설명:

• 키와 값의 쌍으로 이루어진 해시 테이블 기반의 컬렉션입니다.
• 빠른 검색을 위해 해시 함수를 사용합니다.
• 키는 중복될수 없지만 값은 중복될 수 있습니다.

 

시간 복잡도:

• 접근, 탐색, 삽입, 삭제(해시 함수가 이상적이라는 가정): O(1)

 

예제:

Dictionary<string, int> dictionary = new Dictionary<string, int>(); // 인스턴스 생성
dictionary["one"] = 1; // 삽입
dictionary["two"] = 2;
int value = dictionary["one"]; // 접근
dictionary.Remove("two"); // 삭제

 

 

3. Queue<T>

설명:

• FIFO(First In First Out) 구조로, 먼저 들어온 요소가 먼저 나가는 자료구조 입니다.
• 주로 데이터의 순차적 처리를 위해 사용됩니다.

 

시간 복잡도:

• 접근: O(n)
• 접근(Peek, 맨 앞의 요소 접근): O(1)
• 탐색: O(n)
• 삽입: O(1)
• 삭제: O(1)

 

예제:

Queue<int> queue = new Queue<int>(); // 인스턴스 생성
queue.Enqueue(1); // 삽입
queue.Enqueue(2);
int num = queue.Peek(); //맨 앞의 요소 반환
int value = queue.Dequeue(); // 삭제

 

 

4. Stack<T>

설명:

• LIFO(Last In First Out)  구조로, 나중에 들어온 요소가 먼저 나갑니다.
• 주로 함수 호출 스택, 역순 문자열 처리 등에 사용됩니다.

 

시간 복잡도:

• 접근: O(n)
• 접근(Peek, 마지막에 들어온 요소 접근): O(1)
• 탐색: O(n)
• 삽입: O(1)
• 삭제: O(1)

 

예제:

Stack<int> stack = new Stack<int>(); // 인스턴스 생성
stack.Push(1); // 삽입
stack.Push(2);
int value = stack.Pop(); // 삭제

 

 

5. HashSet<T>

설명:

• 유일한 요소들만 저장하는 집합입니다.
• 중복 요소를 허용하지 않습니다.
• 내부적으로 해시 테이블을 사용하여 구현합니다.
• 인덱스나 키를 통한 직접 접근을 지원하지 않으며, 요소가 저장된 순서가 없기 때문에, 특정 요소를 인덱스로 접근하는 개념이 없습니다.

 

시간 복잡도:

• 접근: N/A
• 탐색: O(1)
• 삽입: O(1)
• 삭제: O(1)

 

예제:

HashSet<int> hashSet = new HashSet<int>(); // 인스턴스 생성
hashSet.Add(1); // 삽입
hashSet.Add(2);
bool contains = hashSet.Contains(1); // 탐색
hashSet.Remove(2); // 삭제

 

 

6. LinkedList<T>

설명:

• 노드들이 포인터로 연결된 리스트입니다.
• 요소의 삽입과 삭제가 용이합니다.

 

시간 복잡도:

• 접근: O(n)
• 탐색: O(n)
• 삽입 / 삭제 (노드를 알고 있는 경우): O(1)
• 삽입 / 삭제 (탐색 포함): O(n)

 

예제:

LinkedList<int> linkedList = new LinkedList<int>(); // 인스턴스 생성
linkedList.AddLast(1); // 삽입
linkedList.AddLast(2); // 삽입
int firstValue = linkedList.First.Value; //맨 앞 요소 접근
linkedList.Remove(1); // 삭제

 

 

7. SortedList<TKey, TValue>

설명:

• Array와 Hashtable의 조합으로 키와 값의 쌍을 키에 따라 정렬된 상태로 저장하는 컬렉션입니다.
• 내부적으로 배열을 사용하여 정렬을 유지합니다.
• 키는 중복될 수 없으며 값은 중복될 수 있습니다.

 

시간 복잡도:

• 접근: O(log n)
• 탐색: O(log n)
• 삽입: O(n)
• 삭제: O(n)

 

예제:

SortedList<string, int> sortedList = new SortedList<string, int>(); // 인스턴스 생성
sortedList.Add("one", 1); // 삽입
sortedList.Add("two", 2);
int value = sortedList["one"]; // 접근
sortedList.Remove("two"); // 삭제

 

 

8. SortedDictionary<TKey, TValue>

설명:

• 키와 값의 쌍을 키에 따라 정렬된 상태로 저장하는 컬렉션입니다.
• 키는 중복될 수 없으며 값은 중복될 수 있습니다.
• 내부적으로 이진 탐색 트리(BST)를 사용하여 구현됩니다.

 

시간 복잡도:

• 접근: O(log n)
• 탐색: O(log n)
• 삽입: O(log n)
• 삭제: O(log n)

 

예제:

SortedDictionart<string, int> sortedDictionary = new SortedDictionary<string, int>();
sortedDictionary.Add("one", 1); // 삽입
sortedDictionary.Add("two", 2);
int value = sortedDictionary["one"] // 접근
sortedDictionary.Remove("two"); // 삭제

 

 

 

 

---

 

 

지금까지 자료구조와 컬렉션에 대해 간단하게 알아보았습니다.

현재 글의 내용 중 틀린 부분이나, 지적하실 내용이 있으시다면 언제든지 알려주세요! 읽어주셔서 감사합니다.