C# 자료구조 정리좀..

배열은 고정된 크기의 연속된 배열요소들의 집합이므로 배열을 초기화 할 때 총 배열 요소의 수를 미리 지정해야 한다. 하지만 경우에 따라 배열요소가 몇 개나 필요한 지 미리 알 수 없는 경우가 있으며, 중간에 필요에 따라 배열을 확장해야 하는 경우도 있다. .NET에는 이러한 동적 배열을 지원하는 클래스로 ArrayList와 List<T>이 있다. 이들 동적 배열 클래스들은 배열 확장이 필요한 경우, 내부적으로 배열 크기가 2배인 새로운 배열을 생성하고 모든 기존 배열 요소들을 새로운 배열에 복사한 후 기존 배열을 해제한다. 동적 배열의 Time Complexity는 배열과 같이 인덱스를 통할 경우 O(1), 값으로 검색할 경우 O(n)을 갖는다. 

ArrayList 클래스 

ArrayList는 모든 배열 요소가 object 타입인 Non-generic 동적 배열 클래스이다. .NET의 Non-generic 클래스들은 System.Collections 네임스페이스 안에 있으며, 단점으로 박싱 / 언박싱이 일어나게 된다. ArrayList는 배열 요소를 읽어 사용할 때 object를 리턴하므로 일반적으로 원하는 타입으로 먼저 캐스팅(Casting)한 후 사용하게 된다

ArrayList myList = new ArrayList();
myList.Add(90);
myList.Add(88);
myList.Add(75);

// int로 casting
int val = (int) myList[1];

List<T> 클래스 

List<T>는 배열요소가 T 타입인 Generics로서 동적 배열을 지원하는 클래스이다. .NET의 Generic 클래스들은 System.Collections.Generic 네임스페이스 안에 있다. List클래스는 내부적으로 배열을 가지고 있으며, 동일한(Homogeneous) 타입의 데이타를 저장한다. 만약 미리 할당된 배열 크기(Capacity라 부른다)가 부족하면 내부적으로 배열을 2배로 늘려 동적으로 배열을 확장한다. ArrayList와 다르게 캐스팅을 할 필요가 없으며, 박싱 / 언박싱의 문제를 발생시키지 않는다.

List<int> myList = new List<int>();
myList.Add(90);
myList.Add(88);
myList.Add(75);
int val = myList[1];

SortedList<TKey,TValue> 클래스 

SortedList클래스는 Key값으로 Value를 찾는 Map ADT 타입 (ADT: Abstract Data Type)을 내부적으로 배열을 이용해 구현한 클래스이다. .NET에서 MAP ADT를 구현한 클래스로는 해시테이블을 이용한 Hashtable/Dictionary클래스, 이진검색트리를 이용한 SortedDictionary, 그리고 배열을 이용한 SortedList 등이 있다. SortedList클래스는 내부적으로 키값으로 소트된 배열을 가지고 있으며, 따라서 이진검색(Binary Search)가 가능하기 때문에 O(log n)의 검색 시간이 소요된다. 만약 미리 할당된 배열 크기(Capacity라 부른다)가 부족하면 내부적으로 배열을 2배로 늘려 동적으로 배열을 확장한다. 

SortedList<int, string> list = new SortedList<int, string>();
list.Add(1001, "Tim");
list.Add(1020, "Ted");
list.Add(1010, "Kim");

string name = list[1001];

foreach (KeyValuePair<int, string> kv in list)
{
    Console.WriteLine("{0}:{1}", kv.Key, kv.Value);
}
// 출력
//1001:Tim
//1010:Kim
//1020:Ted

외관상 SortedList가 Dictionary와 비슷하게 보일 수 있습니다. 하지만 이 둘은 근본적인 여러 차이점이 있습니다.

우선 Dictionary는 키값으로 소트되어 있지 않은 반면, SortedList는 키값으로 소트되어 있습니다. Dictionary는 해쉬테이블을 구현한 클래스로 Key에 의해 즉시 Value를 찾을 수 (즉, O(1)) 있지만, SortedList는 비록 문법적으로 Dictionary와 동일하게 값을 찾지만 내부적으로 Binary Search 방식 (O(log N))으로 찾기 때문에 Dictionary 보다 느립니다. 그리고 참고로 내부 구현을 보면 전혀 다른 구조를 갖습니다.

ConcurrentBag 클래스 

.NET 4.0 부터 멀티쓰레딩 환경에서 리스트를 보다 간편하게 사용할 수 있는 새로운 클래스인 ConcurrentBag<T> 가 제공되었다. ConcurrentBag<T> 클래스는 리스트와 비슷하게 객체들의 컬렉션을 저장하는데, List<T> 와는 달리 입력 순서를 보장하지는 않는다. ConcurrentBag 에 데이타를 추가하기 위해 Add() 메서드를 사용하고, 데이타를 읽기 위해서는 foreach문 혹은 TryPeek(), TryTake() 메서드를 사용한다. TryPeek()은 ConcurrentBag에서 데이타를 읽기만 하는 것이고, TryTake()는 데이타를 읽을 후 해당 요소를 ConcurrentBag에서 삭제하게 된다.

ConcurrentBag는 멀티쓰레드가 동시에 엑세스할 수 있는데, 예를 들어 ThreadA와 ThreadB가 ConcurrentBag에 데이타를 쓸 때, ThreadA가 1,2,3 을 넣고, ThreadB가 4,5,6 을 넣으면, ThreadA는 ConcurrentBag을 다시 읽을 때, 자신이 쓴 1,2,3을 우선순위로 먼저 읽은 다음, 나머지 다른 쓰레드에 의해 입력된 요소들 (4,5,6)을 읽게 된다.

아래 예제에서 첫번째 쓰레드는 100개의 숫자를 ConcurrentBag에 넣게 되고, 동시에 두번째 쓰레드는 1초마다 10회에 걸쳐 해당 ConcurrentBag의 내용을 출력하는 것이다. 

using System;
using System.Collections;
using System.Collections.Concurrent; // ConcurrentBag
using System.Threading;
using System.Threading.Tasks;

namespace ConcurrentApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var bag = new ConcurrentBag<int>();

            // 데이타를 Bag에 넣는 쓰레드
            Task t1 = Task.Factory.StartNew(() =>
            {
                for (int i = 0; i < 100; i++)
                {
                    bag.Add(i);
                    Thread.Sleep(100);
                }
            });

            // Bag에서 데이타를 읽는 쓰레드
            Task t2 = Task.Factory.StartNew(() =>
            {
                int n = 1;               
                // Bag 데이타 내용을 10번 출력함
                while (n <= 10)
                {                    
                    Console.WriteLine("{0} iteration", n);
                    int count = 0;

                    // Bag에서 데이타 읽기
                    foreach (int i in bag)
                    {
                        Console.WriteLine(i);
                        count++;
                    }
                    Console.WriteLine("Count={0}", count);

                    Thread.Sleep(1000);
                    n++;
                }
            });

            // 두 쓰레드가 끝날 때까지 대기
            Task.WaitAll(t1, t2);
        }
    }
}

링크드 리스트는 특정 노드에서 노드를 삽입, 삭제하기 편리 하지만 ( O(1) ), 특정 노드를 검색하기 위해서는 O(n)의 시간이 소요된다

LinkedList<T> 클래스 

.NET에는 링크드 리스트를 구현한 LinkedList<T> 클래스가 있다. 이 LinkedList 클래스는 이중 링크드 리스트로 구현되어 있으며, 리스트 노드는 LinkedListNode 클래스로 표현된다. 노드의 추가는 AddFirst, AddLast, AddBefore, AddAfter 등의 메서드들을 호출하여 처음 또는 끝, 혹은 특정 노드의 앞, 뒤에 새 노드를 추가할 수 있다. 아래 예는 Banana 노드 뒤에 Grape노드를 추가하는 예이다. 

LinkedList<string> list = new LinkedList<string>();
list.AddLast("Apple");
list.AddLast("Banana");
list.AddLast("Lemon");
            
LinkedListNode<string> node = list.Find("Banana");
LinkedListNode<string> newNode = new LinkedListNode<string>("Grape");

// 새 Grape 노드를 Banana 노드 뒤에 추가
list.AddAfter(node, newNode);

// 리스트 출력
list.ToList().ForEach(p => Console.WriteLine(p));

// Enumerator를 이용한 리스트 출력
foreach(var m in list)
{
    Console.WriteLine(m);

위에 p => 는 ..

C# 3.0부터 지원하는 => 연산자는 C#에서 람다 식(Lambda Expression)을 표현할 때 사용한다. 람다식은 무명 메서드와 비슷하게 무명 함수(anonymous function)를 표현하는데 사용된다. 람다식은 아래와 같이 입력 파라미터(0개 ~ N개)를 => 연산자 왼쪽에, 실행 문장들을 오른쪽에 둔다.

람다 Synyax : (입력 파라미터) => { 문장블럭 };

예를 들어 하나의 문자열을 받아 들여 메시지 박스를 띄운다면 다음과 같이 간단히 쓸 수 있다

str => { MessageBox.Show(str); }

입력 파라미터는 하나도 없는 경우부터 여러 개 있는 경우가 있다. 다음 예는 파라미터가 없는 케이스 부터 두개 있는 케이스까지 보여준다. 마지막 예는 입력 파라미터의 타입이 애매한 경우 이를 써줄 수 있음을 보여준다. 일반적으로 입력타입은 컴파일러가 알아서 찾아낸다.

() => Write("No");

(p) => Write(p);

(s, e) => Write(e);

(string s, int i) => Write(s, i);

Queue 클래스 

.NET에는 큐를 구현한 Queue클래스와 이의 Generic 형태인 Queue<T> 클래스가 있다. 이 Queue클래스는 내부적으로 순환 배열 (Circular Array)로 구현되어 있는데, 배열의 마지막 요소에 다다른 경우 다시 배열 처음 요소로 순환하는 구조(next % arrsize)를 가지고 있다. Queue는 내부적으로 head와 tail 포인터를 가지고 있는데, tail에 데이타를 추가하고(Enqueue) head에서 데이타를 읽고 제거(Dequeue)한다. 만약 데이타 양이 많아 순환 배열이 모두 찰 경우, Queue는 Capacity를 2배로 (디폴트 Growth Factor가 2이다) 증가시키고, 모든 배열 요소를 새 순환 배열에 자동으로 복사하여 큐를 확장한다.

Queue<int> q = new Queue<int>();
q.Enqueue(120);
q.Enqueue(130);
q.Enqueue(150);

int next = q.Dequeue(); // 120
next = q.Dequeue(); // 130

ConcurrentQueue 클래스 

멀티쓰레딩 환경에서 위의 Queue 클래스를 사용하기 위해서는 전통적인 방식인 lock 을 사용하는 방법과 Queue.Synchronized() 를 사용하여 Thread-safe한 Wrapper 큐를 사용하는 방법이 있다.

.NET 4.0 부터 멀티쓰레딩 환경에서 큐를 보다 간편하게 사용할 수 있는 새로운 클래스인 ConcurrentQueue<T> 가 제공되었다. Queue 클래스와 비슷하게 ConcurrentQueue 의 기본 동작 메서드는 Enqueue() 와 TryDequeue() 인데, ConcurrentQueue 에는 Dequeue() 메서드가 없고 대신 TryDequeue() 메서드를 사용한다. 또한 마찬가지로 ConcurrentQueue에서는 Peek() 메서드 대신 TryPeek() 메서드를 사용한다.

아래 예제는 하나의 쓰레드가 큐(ConcurrentQueue)에 0부터 99까지 계속 집어 넣을 때, 동시에 다른 쓰레드에서는 계속 큐에서 데이타를 빼내 읽어 오는 작업을 하는 샘플 코드이다

using System;
using System.Collections.Concurrent; // ConcurrentQueue
using System.Threading;
using System.Threading.Tasks;

namespace ConcurrentApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var q = new ConcurrentQueue<int>();

            // 데이타를 큐에 넣는 쓰레드
            Task tEnq = Task.Factory.StartNew(() =>
            {
                for (int i = 0; i < 100; i++)
                {
                    q.Enqueue(i);
                    Thread.Sleep(100);
                }
            });

            // 데이타를 큐에서 읽는 쓰레드
            Task tDeq = Task.Factory.StartNew(() =>
            {
                int n = 0;
                int result;
                while (n < 100)
                {
                    if (q.TryDequeue(out result))
                    {
                        Console.WriteLine(result);
                        n++;
                    }
                    Thread.Sleep(100);
                }
            });

            // 두 쓰레드가 끝날 때까지 대기
            Task.WaitAll(tEnq, tDeq);
        }
    }
}

자료구조 : 스택 (Stack) 

스택 (Stack)은 가장 나중에 추가된 데이타가 먼저 출력 처리되는(LIFO, Last In First Out) 자료 구조로서 가장 최신 입력된 순서대로 처리해야 하는 상황에 이용된다. 스택은 개념적으로 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조로 되어 있다. 자료는 스택에 저장하는 것은 Push라 하고, 가장 최근 것부터 꺼내는 것은 Pop이라 한다. Stack의 Push와 Pop은 일반적으로 O(1)의 시간이 소요되지만, Push의 경우 만약 스택이 Full되어 동적 확장이 일어난다면 O(n)의 시간이 소요된다. 

Stack 클래스 

.NET에는 스택을 구현한 Non-generic인 Stack클래스와 이의 Generic 형태인 Stack<T> 클래스가 있다. Queue와 마찬가지로 .NET의 Stack클래스는 내부적으로 순환 배열 (Circular Array)으로 구현되어 있으며, 스택이 가득 차면 자동으로 배열을 동적으로 확장하게 된다. 

Stack<double> s = new Stack<double>();
s.Push(10.5);
s.Push(3.54);
s.Push(4.22);

double val = s.Pop(); //4.22

ConcurrentStack 클래스 

.NET 4.0 부터 멀티쓰레딩 환경에서 스택을 보다 간편하게 사용할 수 있는 새로운 클래스인 ConcurrentStack<T> 가 제공되었다. Stack 클래스와 비슷하게 ConcurrentStack 의 기본 동작 메서드는 Push() 와 TryPop() 인데, ConcurrentStack 에는 Pop() 메서드가 없고 대신 TryPop() 메서드를 사용한다.

아래 예제는 하나의 쓰레드가 ConcurrentStack 에 0부터 99까지 계속 집어 넣을 때, 동시에 다른 쓰레드에서는 계속 그 스택에서 데이타를 빼내 읽어 오는 작업을 하는 샘플 코드이다. 스택을 Pop 하는 속도를 약간 늦춤으로 해서 0 부터 99까지 순차적으로 출력하지 않을 가능성이 더 커지게 하였다. 

using System;
using System.Collections;
using System.Collections.Concurrent; // ConcurrentStack
using System.Threading;
using System.Threading.Tasks;

namespace ConcurrentApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = new ConcurrentStack<int>();

            // 데이타를 스택에 넣는 쓰레드
            Task tPush = Task.Factory.StartNew(() =>
            {
                for (int i = 0; i < 100; i++)
                {
                    s.Push(i);
                    Thread.Sleep(100);
                }
            });

            // 데이타를 스택에서 읽는 쓰레드
            Task tPop = Task.Factory.StartNew(() =>
            {
                int n = 0;
                int result;
                while (n < 100)
                {
                    if (s.TryPop(out result))
                    {
                        Console.WriteLine(result);
                        n++;
                    }
                    Thread.Sleep(150);
                }
            });

            // 두 쓰레드가 끝날 때까지 대기
            Task.WaitAll(tPush, tPop);
        }
    }
}

자료구조 : 해시테이블 (Hash Table) 

해시(Hash)는 키 값을 해시 함수(Hash function)으로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다.
키 값을 통해 직접 엑세스하기 위해서 모든 가능한 키 값을 갖는 배열을 만들면, 배열크기가 엄청나게 커지게 된다. 예를 들어, 주민등록번호를 키 값으로 하는 경우, 000000-0000000 부터 999999-9999999까지 10의 13승의 배열 공간이 필요한데, 만약 회원수가 1000명인 경우, 1000명을 저장하기 위해 10^13의 엄청난 배열 공간이 필요하게 된다. 이렇게 낭비되는 공간을 줄이기 위해 해시 함수를 사용하게 되는데, 이 함수는 적은 공간 안에서 모든 키를 직접 찾아갈 수 있도록 해준다. 하지만 경우에 따라 서로 다른 키가 동일한 해시테이블 버켓 위치를 가리킬 수 있는데, 이를 해결하기 위해 여러 Collision Resolution 방식이 사용된다. Collision Resolution의 방식으로 Linear Probing(클러스터 현상이 잘 일어난다. 클러스터는 여러개가 연결되어 하나처럼된듯..), Quadratic Probing, Rehashing (Double Hashing), Chaining 등 여러가지가 있다. 해시테이블 자료구조는 추가, 삭제, 검색에서 O(1)의 시간이 소요된다. 

Hashtable 클래스 

.NET에 해시테이블을 구현한 Non-generic 클래스로 Hashtable 클래스가 있다. Hashtable은 Key값과 Value값 모두 object 타입을 받아들이며, 박싱/언박싱을 하게 된다. Hashtable은 Rehashing (Double Hashing)방식을 사용하여 Collision Resolution을 하게 된다. 즉, 해시함수를 H1(Key) 부터 Hk(Key) 까지 k개를 가지고 있으며, 키 충돌(Collision)이 발생하면, 차기 해시함수를 계속 사용하여 빈 버켓을 찾게된다. 이 자료구조는 추가, 삭제, 검색에서 O(1)의 시간이 소요된다. 

Hashtable ht = new Hashtable();
ht.Add("irina", "Irina SP");
ht.Add("tom", "Tom Cr");

if (ht.Contains("tom"))
{
    Console.WriteLine(ht["tom"]);
}

Dictionary<Tkey,TValue> 클래스 

.NET에 Generic방식으로 해시테이블을 구현한 클래스로 Dictionary<Tkey,TValue> 클래스가 있다. Dictionary는 Key값과 Value값 모두 Strong type을 받아들이며, 박싱/언박싱을 일으키지 않는다. Dictionary는 Chaining 방식을 사용하여 Collision Resolution을 하게 된다. 이 자료구조는 추가, 삭제, 검색에서 O(1)의 시간이 소요된다. 

느슨한 타입은 타입 없이 변수를 선언하는 것이다. 반면에 강력한 타입(strong typing)을 사용하는 언어는 타입과 함께 변수를 선언해야만 한다. 다음의 예제를 살펴보자:

1 2 3 4 5 6 7

/* JavaScript Example (loose typing) */ var a = 13; // Number 선언 var b = "thirteen"; // String 선언 /* Java Example (strong typing) */ int a = 13; // int 선언 String b = "thirteen"; // String 선언

Dictionary<int, string> emp = new Dictionary<int, string>();
emp.Add(1001, "Jane");
emp.Add(1002, "Tom");
emp.Add(1003, "Cindy");

string name = emp[1002];
Console.WriteLine(name);

ConcurrentDictionary<Tkey,TValue> 클래스 

.NET 4.0 부터 멀티쓰레딩 환경에서 Dictionary를 보다 간편하게 사용할 수 있는 새로운 클래스인 ConcurrentDictionary<T> 가 제공되었다. ConcurrentDictionary 클래스에서는 기본적으로 데이타를 추가하기 위해 TryAdd() 메서드를 사용하고, 키값을 읽기 위해서는 TryGetValue() 메서드를 사용한다. 또한 기존 키값을 갱신하기 위해서 TryUpdate() 메서드를, 기존 키를 지우기 위해서는 TryRemove() 메서드를 사용한다.

아래 예제는 하나의 쓰레드가 ConcurrentDictionary 에 Key 1부터 100까지 계속 집어 넣을 때, 동시에 다른 쓰레드에서는 계속 그 해시테이블에서 Key 1부터 100까지의 데이타를 빼내 (순차적으로) 읽어 오는 작업을 하는 샘플 코드이다.

using System;
using System.Collections;
using System.Collections.Concurrent; // ConcurrentDictionary
using System.Threading;
using System.Threading.Tasks;

namespace ConcurrentApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var dict = new ConcurrentDictionary<int, string>();

            Task t1 = Task.Factory.StartNew(() =>
            {
                int key = 1;                
                while (key <= 100)
                {
                    if (dict.TryAdd(key, "D" + key))
                    {
                        key++;
                    }
                    Thread.Sleep(100);
                }
            });

            Task t2 = Task.Factory.StartNew(() =>
            {
                int key = 1;
                string val;
                while (key <= 100)
                {
                    if (dict.TryGetValue(key, out val))
                    {
                        Console.WriteLine("{0},{1}", key, val);
                        key++;
                    }
                    Thread.Sleep(100);
                }
            });

            Task.WaitAll(t1, t2);
        }
    }
}

자료구조 : 이진 트리 (Binary Tree) 

트리(Tree)에서 많이 사용되는 특별한 트리로서 이진트리를 들 수 있는데, 이진 트리는 자식노드가 0개 ~ 2개인 트리를 말한다. 따라서 이진트리 노드는 데이타필드와 왼쪽노드 및 오른쪽노드를 갖는 자료 구조로 되어 있다. 이진 트리는 루트 노드로부터 출발하여 원하는 특정 노드에 도달할 수 있는데, 이때의 검색 시간(Search Time)은 O(n)이 소요된다.

자료구조 : 이진검색트리 (Binary Search Tree) 

이진트리(Tree)의 특수한 형태로 자주 사용되는 트리로서 이진검색트리 (Binary Search Tree)가 있다. 이진검색트리는 이진트리의 모든 속성을 가짐과 동시에 중요한 또 하나의 속성을 가지고 있는데, 그것은 특정 노드에서 자신의 노드보다 작은 값들은 모두 왼쪽에 있고, 큰 값들은 모두 오른쪽에 위치한다는 점이다. 또한 중복된 값을 허락하지 않는다. 따라서 전체 트리가 소트되어 있는 것과 같은 효과를 같게 되어 검색에 있어 배열이나 이진트리처럼 순차적으로 모든 노드를 검색하는 것(O(n))이 아니라, 매 검색마다 검색영역을 절반으로 줄여 O(log n)으로 검색할 수 있게 된다. 하지만 노드들이 한쪽으로 일렬로 기울어진 Skewed Tree인 경우, 검색영역을 n-1로만 줄이기 때문에 O(n)만큼의 시간이 소요된다. 즉, 예를 들어 소트된 데이타를 이진검색트리에 추가하게 되면, 이렇게 한쪽으로 치우쳐 진 트리가 생겨 검색시간이 O(n)으로 떨어지게 되는데, 이러한 현상을 막기 위하여 노드 추가/갱신시 트리 스스로 다시 밸런싱(Self balancing)하여 검색 최적화를 유지할 수 있다. 이러한 트리를 Self-Balancing Binary Search Tree 또는 Balanced Search Tree라 하는데, 가장 보편적인 방식으로 AVL Tree, Red-Black Tree 등을 들 수 있다.
NOTE: 참고로 Search Tree에는 최대 2개의 자식노드를 갖는 Binary Search Tree 이외에, 여러 개의 자식노드들을 갖는 N-Way 검색 트리 (n-way Search Tree)가 있는데, 대표적으로 B-Tree (혹은 이의 변형인 B* Tree, B+ Tree)가 있으며 흔히 SQL Server와 같은 관계형 DB 인덱스로 주로 사용된다.