C# 컬렉션과 자료구조 (Generic, Non-Generic.......)

개발Velog·2021년 8월 15일
BSTC샵D-ArrayGraphHashTableListarraydata structuredictionaryheaplinked listqueuestacktree자료구조
1

C#

목록 보기
9/9
post-thumbnail

List, Dictionary, HashTable등 C#에서 자주 사용하는 자료구조 클래스에 대해
정리해볼 예정.

💾 자료구조(Data Structure)란?

프로그래밍에서 데이터(자료)를 효율적으로 관리하는 것이 매우 중요한데
자료구조란 데이터를 구조적으로 표현하고 구현하는 중요한 알고리즘을 뜻한다.

Collections은 C#에서 지원하는 자료구조 클래스이다.
성능 이유로 현재 C#에서는 Generic Collections 사용한다.

*.net 2.0이하에서는 non-Generic Collections 사용했는데
속도와 타입안정성의 문제가 있었다.
데이터를 저장할 때 무조건 System.Objects 타입으로 저장을 하면서
데이터 저장, 추출할 때 형변환이 반드시 필요했으며 정확한 타입을 저장하지 않음으로
오류 발생의 여지가 현저히 높았다.

💾 Generic vs Non-Generic

  • 키별로 빠르게 조회할 수 있도록 항목을 키/값 쌍으로 저장
    Dictionary<TKey, TValue> vs Hashtable
  • 인덱스별로 항목 액세스
    List<T> vs Array, ArrayList
  • FIFO(선입선출) 방식으로 항목 사용
    Queue<T> vs Queue
  • LIFO(후입선출) 방식으로 데이터 사용
    Stack<T> vs Stack
  • 순서대로 항목 액세스
    LinkedList<T> vs null
  • 항목을 컬렉션에 추가하거나 컬렉션에서 제거할 때 알림이 표시됩니다.
    ObservableCollection<T> vs null
  • 정렬된 컬렉션
    SortedList<TKey, TValue> vs SortedList
  • 수학 함수용 집합
    HashSet<T> vs null

그 외에 스레드로부터 안전하거나 변경할 수 없는 컬렉션 옵션에는
ConcurrentDictionary<TKey, TValue>
, ImmutableList<T>
, ConcurrentQueue<T>
, ConcurrentStack<T>
, ImmutableSortedDictionary<TKey, TValue> 등이 있다.

💾 Generic Collections 사용법

Dictionary

Key와 Value로 값을 빠르게 조회할 수 있도록 하는 Collections Class

static void Main(string[] args)
{
    Dictionary<string, string> dicColor = new Dictionary<string, string>();
    dicColor.Add("Red", "빨강");
    dicColor.Add("Green", "초록");
    dicColor.Add("Blue", "파랑");
    try
    {
        if (dicColor.ContainsKey("Red"))//RED 들어있는지 체크
        {
            Console.WriteLine($"dicColor[Red] 이미 존재합니다. -> {dicColor["Red"]}");
        }
        else
        {
            dicColor.Add("Red", "빨강");
        }
        if (!dicColor.ContainsKey("Yellow"))//YELLOW 들어있는지 체크
        {
            dicColor.Add("Yellow", "노랑");
        }
        foreach (var keyValuePair in dicColor)
        {
            Console.WriteLine($"dicColor[{keyValuePair.Key}] = {keyValuePair.Value}");
        }
        if (dicColor.ContainsKey("Red"))//RED 들어있으면 꺼내기
        {
            Console.WriteLine($"dicColor[Red] = {dicColor["Red"]}");
        }
        dicColor.Add("Blue", "파랑");//BLUE 들어있는지 체크 (Exception)
        Console.WriteLine($"dicColor[Pink] = {dicColor["Pink"]}");//Yellow 있으면 출력 (Exception)
    }
    catch(Exception ex)
    {
        Console.WriteLine($"error {ex.Message}");
    }
}

List<T>

인덱스별로 관리 할 수 있는 동적 Collection

public class Part : IEquatable<Part> 
{
    public string PartName { get; set; }
    public int PartId { get; set; }
    public override string ToString()
    {
        return $"ID : {PartId} Name : {PartName}";
    }
    public override bool Equals(object obj)
    {
        if(obj is null)
        {
            return false;
        }
        Part objAsPart = obj as Part;
        if(objAsPart is null)
        {
            return false;
        }
        else
        {
            return Equals(objAsPart);
        }
    }
    public override int GetHashCode()
    {
        return PartId;
    }
    public bool Equals([AllowNull] Part other)
    {
        if(other is null)
        {
            return false;
        }
        return (this.PartId.Equals(other.PartId));
    }
}
static void Main(string[] args)
{
    List<Part> parts = new List<Part>();
    parts.Add(new Part() { PartName = "A_Part", PartId = 1 });
    parts.Add(new Part() { PartName = "B_Part", PartId = 2 });
    parts.Add(new Part() { PartName = "C_Part", PartId = 3 });
    parts.Add(new Part() { PartName = "D_Part", PartId = 4 });
    parts.Add(new Part() { PartName = "E_Part", PartId = 5 });

    foreach (Part part in parts)
    {
        Console.WriteLine(part);
    }
    Console.WriteLine();
    parts.Contains(new Part { PartName = "", PartId = 6 });
    parts.Insert(2, new Part() { PartName = "F_Part", PartId = 6 });

    foreach (Part part in parts)
    {
        Console.WriteLine(part);
    }
    Console.WriteLine();
    parts.Remove(new Part() { PartId = 3, PartName = "C_Part_1" });
    foreach (Part part in parts)
    {
        Console.WriteLine(part);
    }
    Console.WriteLine();
    parts.RemoveAt(3);
    foreach (Part part in parts)
    {
        Console.WriteLine(part);
    }
}

Queue<T>

Queue는 먼저 추가된 데이터가 먼저 출력 처리되는 (FIFO, First In First Out) 자료 구조이다.
Queue는 맨 뒤(tail) 에 데이터를 계속 추가하고, 맨 앞(head)에서만 데이터를 읽기 때문에 순차적으로 데이터를 처리 한다.

  • 예제는 기본동작은 똑같지만 .Net 4.0부터 멀티쓰레딩 환경에서 쉽게 큐를 사용할 수 있는 ConcurrentQueue<T>를 이용해 보았다. 
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(1000);
        }
    });


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

    Task.WaitAll(tEnq, tDeq);
}

Stack<T>

Stack은 가장 나중에 추가된 데이터가 먼저 출력 처리되는 (LIFO, Last In First Out)자료 구조로서 가장 최신 입력된 순서대로 처리해야 하는 상황에서 사용.
스택은 개념적으로 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조로 돼있다.
저장은 Push , 꺼내는 것은 Pop이라 한다.

  • 예제는 기본동작은 똑같지만 .Net 4.0부터 멀티쓰레딩 환경에서 쉽게 큐를 사용할 수 있는 ConcurrentTask<T>를 이용해 보았다.
    Pop() -> TryPop()
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, tPush);
}

LinkedList<T>

LinkedList는 데이터를 포함하는 노드를 연결하여 컬렉션을 만든 자료 구조로서 각 노드는 데이터와 다음/이전 링크 포인터를 갖는다.

종류

  • 단일 연결 리스트
    노드를 다음 링크로만 연결
  • 이중 연결 리스트
    각 노드를 이전, 이후 모두 연결
  • 순환 연결리스트
    마지막 노드의 다음 링크가 처음 노드 연결

시간복잡도

특정 노드 삽입 => O(1)
특정 노드 검색 => O(n)

이중 연결리스트인 LinkedList<T>를 이용해 보았다. 

static void Main(string[] args)
{
    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<string>().ForEach(p => Console.WriteLine(p));            

    // Enumerator 리스트 출력
    foreach (var item in list)
    {
        Console.WriteLine(item);
    }
}

SortedList<TKey, TValue>

키를 기준으로 자동 정렬되며, 키/값. 쌍의 컬렉션을 나타내는 자료구조.

특성

  • 요소가 추가되면 즉시 정렬 (IComparer<T>기반)
  • 키는 고유해야 하며 null이 될 수 없다.
  • 값은 null 또는 중복일 수 있다.

시간복잡도

  • 기본적으로 O(log n)

SortedList<TKey, TValue>를 이용해 보았다. 

static void Main(string[] args)
{
    #region 1. 키가 숫자일 경우 숫자 정렬

    SortedList<int, string> sortedList1 = new SortedList<int, string>();
    sortedList1.Add(3, "Three");
    sortedList1.Add(1, "One");
    sortedList1.Add(2, "Two");
    sortedList1.Add(4, "Four");

    foreach (KeyValuePair<int, string> kvp in sortedList1)
    {
        Console.WriteLine($"{kvp.Key} / {kvp.Value}");
    }

    foreach (var kvp in sortedList1)
    {
        Console.Write("{0, -10} ", kvp);
    }
    Console.WriteLine();

    #endregion

    #region 2. 키가 문자일 경우 문자정렬

    SortedList<string, int> sortedList2 = new SortedList<string, int>();
    sortedList2.Add("Three", 3);
    sortedList2.Add("One", 1);
    sortedList2.Add("Two", 2);
    sortedList2.Add("Four", 4);

    foreach (KeyValuePair<string, int> kvp in sortedList2)
    {
        Console.WriteLine($"{kvp.Key} / {kvp.Value}");
    }

    foreach (var kvp in sortedList2)
    {
        Console.Write("{0, -10} ", kvp);
    }
    Console.WriteLine();

    #endregion

    #region 3. TryGetValue 함수 사용

    SortedList<string, int> sortedList3 = new SortedList<string, int>();
    sortedList3.Add("Three", 3);
    sortedList3.Add("One", 1);
    sortedList3.Add("Two", 2);
    sortedList3.Add("Four", 4);

    int val;
    if(sortedList3.TryGetValue("Ten", out val))
    {
        Console.WriteLine($"key : Ten, value : {val}");
    }
    else
    {
        Console.WriteLine("[Ten] : key is not valid");
    }

    if(sortedList3.TryGetValue("One", out val))
    {
        Console.WriteLine($"key : One, value : {val}");
    }

    #endregion

    #region 4. 매개변수를 키로 하는 요소 / 매개변수를 값으로 하는 요소

    SortedList<string, int> sortedList4 = new SortedList<string, int>();
    sortedList4.Add("Three", 3);
    sortedList4.Add("One", 1);
    sortedList4.Add("Two", 2);
    sortedList4.Add("Four", 4);

    //매개변수를 키로
    Console.WriteLine(sortedList4.ContainsKey("One"));
    Console.WriteLine(sortedList4.ContainsKey("Ten"));
    //매개변수를 값으로
    Console.WriteLine(sortedList4.ContainsValue(2));
    Console.WriteLine(sortedList4.ContainsValue(6));

    #endregion  

    #region 5. 삭제하는 법

    SortedList<string, int> sortedList5 = new SortedList<string, int>();
    sortedList5.Add("Three", 3);
    sortedList5.Add("One", 1);
    sortedList5.Add("Two", 2);
    sortedList5.Add("Four", 4);

    sortedList5.Remove("Three");//키가 "Three" 삭제
    sortedList5.RemoveAt(0);//첫번째 요소

    foreach (KeyValuePair<string, int> kvp in sortedList5)
    {
        Console.Write("{0, -10} ", kvp);
    }

    Console.WriteLine();

    #endregion  
}
출처 및 참조 :

https://docs.microsoft.com/ko-kr/dotnet/standard/collections/
http://www.csharpstudy.com/

profile
개발Velog
안녕하세요. 데이터와 동고동락 중인 개발자 입니다.
이전 포스트

📜 JSON이란 무엇일까?

0개의 댓글