티스토리 뷰
C#의 Collection에 속한 LinkedList<T>에 관한 글입니다.
이 글도 완벽한 성능 분석이 아닌, C++에서 사용한 List의 간단한 사용법과 비교하면서 중요하고 주로 사용했던 부분들에 대한 정보를 공유하고자 글을 작성하였습니다.
이 글은 C++의 STL으로 다룰 줄 아시는 분 or 사용해본 경험이 있다는 것을 전제로 작성하였습니다.
글은 MS의 MSDN을 참고했고 틀린 부분은 댓글을 달아주시면 확인 후 수정하도록 하겠습니다 ^_^
1. LinkedList<T>의 특성
C++의 list와 비슷합니다. 양방향 연결 리스트이며 동적으로 메모리를 관리해주고 자유롭게 삽입, 삭제가 가능한.. 자료구조입니다. 대부분의 교재 및 자료(블로그)에서 List, Queue, Stack, Dictionary만 설명해주고 있어서 MSDN을 뒤져가며 분명 C++의 list에 대응하는 자료구조가 C#에도 있을 것이다 라고 생각하고 찾아보니 역시 있었습니다.
| C++ | C# |
| Vector | List |
| List | LinkedList |
| Queue | Queue |
| Map | Dictionary |
| Stack | Stack |
가 아닐지.. 싶습니다.
그래서 크게 C#의 List와 LinkedList가 다른점은 C++에서 Vector과 List가 다른 점과 비슷하다고 봅니다. 배열 같은 경우는 삽입 삭제가 도중에서 일어난다면 값을 다 밀고 당겨야 하는 추가 연산이 필요합니다. LinkedList는 그렇지 않고 포인터만 변경해주면 되기 때문에 상수 시간에 삽입, 삭제를 할 수 있다는 장점이 있습니다. 하지만 탐색은 그렇게 빠르지 않다는 점.. 왜냐하면 임의로 접근이 불가능하기 때문입니다.
예를 들어 길이가 100인 linked list가 있다고 했을 때 50번째에 접근하려면 1칸씩 50번가야 접근할 수 있다는 점입니다.
vector(List)같은 경우는 [49]로 임의로 바로 접근할 수 있는데 말이죠..
부가적인 Linked List는 학부 자료구조 시간에 교수님께 많이 들으셨으리라 생각하고!! 이 정도로 넘어가겠습니다.(비전공자분이 시라면 다른 블로그나 사전, Youtube 등에 더 자세히 설명되어 있을 것이라 생각합니다.^^)
2. LinkedList <T>의 구성
사용할 때 필수로 알아야 하는 부분을 위주로 설명하겠습니다.
2.1) 생성자
처음부터 텅 빈 생성자 or 복사할 것이 존재하는 생성자(값이 존재)
크게 두 가지로 나눌 수 있겠습니다.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Helloworld
{
static void Main(string[] args)
{
LinkedList<int> IntList1 = new LinkedList<int>();
int[] list2arr = new int[] { 1, 20, 3 };
LinkedList<int> IntList2 = new LinkedList<int>(list2arr);
Console.WriteLine("-------IntList1--------");
foreach(int item in IntList1)
Console.Write($"{item} ");
Console.WriteLine();
Console.WriteLine("-------IntList2--------");
foreach (int item in IntList2)
Console.Write($"{item} ");
Console.WriteLine();
return;
}
}
}
다음은 위 코드의 결과입니다.
아무것도 들어있지 않은 Linked List1개(IntList1)와 int 배열을 매개변수로 받는 생성자로 만들어진 Linked List1개(IntList2)를 볼 수 있습니다.
다음은 Class를 매개변수로 넣어서, Class를 갖고 있는 Linked List로 보겠습니다.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Item
{
public Item() { }
public Item(string name_, int price_) { this.name = name_;this.price = price_; }
public string name { get; set; }
public int price { get; set; }
}
class Helloworld
{
static void Main(string[] args)
{
LinkedList<Item> ItemList1 = new LinkedList<Item>();
Item[] list2arr = new Item[] { new Item("pen", 500), new Item("book", 3000), new Item("coffee", 4000) };
LinkedList<Item> ItemList2 = new LinkedList<Item>(list2arr);
Console.WriteLine("-------ItemList1--------");
foreach(Item item in ItemList1)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine();
Console.WriteLine("-------ItemList2--------");
foreach (Item item in ItemList2)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine();
return;
}
}
}
이처럼 class도 담을 수 있고 생성할 수 있습니다.
2.2) 속성
속성으로는 Count, First, Last가 있습니다.
Count는 Size와 같은 개념, 또, Capacity는 없습니다.
First와 Last는 C++에서 front(), back()과 같은 느낌이고 가장 첫 객체, 마지막 객체의 정보를 갖고 옵니다. 텅 빈 Linked List라면 null을 나타냅니다.
추가적으로 First와 Last는, 그 안에 Value를 갖고 Value안에 클래스 멤버 변수들이 존재합니다.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Item
{
public Item() { }
public Item(string name_, int price_) { this.name = name_; this.price = price_; }
public string name { get; set; }
public int price { get; set; }
}
class Helloworld
{
static void Main(string[] args)
{
Item[] listarr = new Item[] { new Item("pen", 500), new Item("book", 3000), new Item("coffee", 4000), new Item("mask",1500) };
LinkedList<Item> ItemList = new LinkedList<Item>(listarr);
Console.WriteLine("-------ItemList--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine();
Console.WriteLine($"Count : {ItemList.Count}");
Console.WriteLine($"First : {ItemList.First.Value.name}");
Console.WriteLine($"Last : {ItemList.Last.Value.name}");
return;
}
}
}
First, Last는 첫 번째, 마지막 원소를 잘 가리키고 있음을 알 수 있고 Count는 List에 속한 원소의 개수를 잘 나타내고 있습니다.
2.3) 메서드
삽입, 삭제, 변경, 탐색 등을 위주로 살펴보겠습니다.
2.3.1) 삽입
C++ list처럼 puch_back의 기능을 하는 method가 있습니다. push_back은 가장 마지막에 넣는 것이지만, push_front처럼 list의 앞에 넣는 method도 있다.
우선, 가장 뒤에 삽입되는 것부터 해보고 다른 것도 살펴보자.
다음은 .AddLast(T) member method다. C++ list의 push_back과 동일.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Item
{
public Item() { }
public Item(string name_, int price_) { this.name = name_; this.price = price_; }
public string name { get; set; }
public int price { get; set; }
}
class Helloworld
{
static void Main(string[] args)
{
Item[] listarr = new Item[] { new Item("pen", 500), new Item("book", 3000), new Item("coffee", 4000), new Item("mask",1500) };
LinkedList<Item> ItemList = new LinkedList<Item>(listarr);
Console.WriteLine("-------ItemList--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n");
Console.WriteLine("---push_back(T) -> AddLast(T)---");
ItemList.AddLast(new Item("new item1", 5000));
ItemList.AddLast(new Item("new item2", 10000));
Console.WriteLine("ItemList.AddLast(new Item(\"new item1\",5000)) is entered.");
Console.WriteLine("ItemList.AddLast(new Item(\"new item2\",10000)) is entered.\n");
Console.WriteLine("-------after adding items--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine();
return;
}
}
}
다음은 실행결과이다.
순서대로 Linked List의 가장 뒤에 삽입되는 것을 확인할 수 있다. linked list니까 당연히 시간 복잡도는 O(1) 일 것이다.
위 코드에서 Add'Last'부분을 Add'First'로 변경하면, 다음과 같은 결과가 나온다.
이제 도중에 삽입하는 것을 살펴보자,
도중에 삽입하는 것은 AddAfter, AddBefore가 있다. ( C++처럼 그냥 insert 하면 편할 텐데.. 그래도 내로라하는 MS 개발자 분들이 만든 것이니 이유가 다 있겠죠? 개발하면서 선택의 폭이 넓어지고 더 세세하게 개발할 수 있으니..)
C++에서 도중에 삽입하려면 어느 위치에 삽입할 것인지 iterator로 가리키고 있어야 한다. 하지만 linked list의 특성상 바로 여기!라고는 못하고 처음 혹은 끝에서부터 한 칸씩 움직이면서 찾아가야 한다.
그래서, 여기서도 매개변수를 보면 AddAfter(LinkedListNode<T>, T)로, C++에서 iterator의 역할을 하는 것이 첫 번째 매개변수가 한다.
그래서 하나의 LinkedListNode를 가리키게 될 텐데, 이때 값 비교가 아닌 같은 객체에 대해 참조를 하고 있어야 한다는 점이다.
값 비교를 위해 내가 정의한 클래스에 IEquatable<T> 인터페이스를 구현해주자.
두 개의 클래스를 '=' 연산자를 사용해서 비교할 때 언제 '같다'라고 정의할 것인지에 대한 메서드이다.
즉, 여기서는 name, price 멤버를 갖고 있기 때문에, 이름과 가격이 같으면 같은 Item이다.라고 할 것이기 때문에
밑의 코드와 같이 Equals 메서드를 작성하였다.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Item :IEquatable<Item>
{
public Item() { }
public Item(string name_, int price_) { this.name = name_; this.price = price_; }
public string name { get; set; }
public int price { get; set; }
public bool Equals(Item other)
{
return name == other.name && price == other.price;
}
}
class Helloworld
{
static void Main(string[] args)
{
Item[] listarr = new Item[] { new Item("pen", 500), new Item("book", 3000), new Item("coffee", 4000), new Item("mask",1500) };
LinkedList<Item> ItemList = new LinkedList<Item>(listarr);
Console.WriteLine("--------ItemList--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n");
Console.WriteLine("---AddBefore(LinkedListNode<T>,T)---");
ItemList.AddBefore(ItemList.Find(new Item("book",3000)), new Item("new item1", 5000));
Console.WriteLine("ItemList.AddBefore(ItemList.Find(new Item(\"book\",3000)), new Item(\"new item1\", 5000));");
Console.WriteLine("-------after adding items--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine();
return;
}
}
}
이렇게 하면 book, 3000인 원소 앞에(before) 노드가 추가되는 것을 볼 수 있다.
after는 book, 3000인 원소 뒤에(after) 노드가 추가된다.
밑의 실행화면은 before를 사용한 결과이다.
이렇게 가장 앞, 뒤, 혹은 중간에 삽입하는 경우를 다 살펴보았다.
2.3.2) 삭제
이번에는 삭제하는 경우를 살펴보자.
이 경우도, 가장 앞, 뒤 그리고 특정 값을 가지는 원소를 찾아서 삭제하는 이 세 가지 경우를 살펴보겠다.
앞 뒤를 삭제하는 .RemoveFirst(), .RemoveLast()가 있다. AddLast()등과 비슷하게 생겼다.
이것도 단순히 가장 앞, 가장 뒤를 삭제한다.
그리고 그냥 .Remove(T) 메서드가 있다. 딱 봐도 T값과 동일한 객체를 리스트에서 찾아 삭제하는 것 같다.
이때도 찾을 때, 비교하는 것에 대한 정의가 필요하니까 IEquatable<T>를 구현해야 한다.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Item :IEquatable<Item>
{
public Item() { }
public Item(string name_, int price_) { this.name = name_; this.price = price_; }
public string name { get; set; }
public int price { get; set; }
public bool Equals(Item other)
{
return name == other.name && price == other.price;
}
}
class Helloworld
{
static void Main(string[] args)
{
Item[] listarr = new Item[] { new Item("pen", 500), new Item("book", 3000), new Item("coffee", 4000), new Item("mask",1500), new Item("cup",1000) };
LinkedList<Item> ItemList = new LinkedList<Item>(listarr);
Console.WriteLine("--------ItemList--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n\n");
Console.WriteLine("---RemoveFirst()---");
ItemList.RemoveFirst();
Console.WriteLine("ItemList.RemoveFirst()\n");
Console.WriteLine("-------after removing items--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n\n");
Console.WriteLine("---RemoveLast()---");
ItemList.RemoveLast();
Console.WriteLine("ItemList.RemoveLast()\n");
Console.WriteLine("-------after removing items--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n\n");
Console.WriteLine("---Remove(T)---");
ItemList.Remove(new Item("coffee",4000));
Console.WriteLine("ItemList.Remove(new item(\"coffee\"),4000)\n");
Console.WriteLine("-------after removing items--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n");
return;
}
}
}
실행결과는 다음과 같다.
위처럼 잘 동작하는 것을 볼 수 있다.
2.3.3) 변경, 탐색
한번 실험을 하면서 C++과 다르구나.. 라는걸 알았다.
이번 변경에서는 Linked List를 처음부터 끝까지 한 번씩 훑으면서 바꾸고 싶은 값이 존재한다면 바꾸는 그런 형태로 하였다. 왜냐하면 List(array)처럼 임의로 접근할 수 있는 게 아니로 Linked List는 처음부터 한 칸씩 훑어나가야 접근을 할 수 있기 때문이다.
그래서 C++방식처럼 iterator과 같이 그 linked list의 원소 하나를 가리키는 방식으로 탐색하는 것과,
Linked List에 구현되어 있는 foreach문을 사용해서 하나씩 훑는 방법이다.
특히, iterator 같은 방법을 추가한 이유는 foreach는 C++에서 변수를 값 복사로 읽기 때문이다. 그래서 foreach로 읽은 변수들의 값을 바꾸어도 값 복사이기 때문에 원본의 내용은 바뀌지 않는다.
그런데 C#에서는 class 같은 경우 모두 참조 복사를 하기 때문에 foreach에서 값을 바꾸어도 값이 변경되었다.
(C++은 참조로 명시하지 않는 이상 값 변경이 안됨.)
(for( object item : collection)문법 in C++)
아까 AddFirst같은 것 할 때 Find(T)를 써도 무방하다.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
class Item :IEquatable<Item>
{
public Item() { }
public Item(string name_, int price_) { this.name = name_; this.price = price_; }
public string name { get; set; }
public int price { get; set; }
public bool Equals(Item other)
{
return name == other.name && price == other.price;
}
}
class Helloworld
{
static void Main(string[] args)
{
Item[] listarr = new Item[] { new Item("pen", 500), new Item("book", 3000), new Item("coffee", 4000), new Item("mask",1500), new Item("cup",1000) };
LinkedList<Item> ItemList = new LinkedList<Item>(listarr);
Console.WriteLine("--------ItemList using foreach--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n");
Console.WriteLine("--------ItemList using iterator--------");
for (LinkedListNode<Item> ItemNode = ItemList.First; ItemNode != null; ItemNode = ItemNode.Next)
Console.Write($"({ItemNode.Value.name} : {ItemNode.Value.price}) ");
Console.WriteLine("\n\n");
Console.WriteLine("-------updated by foreach--------");
foreach (Item item in ItemList)
{
Console.Write($"({item.name} : {item.price}) ");
if (item.name == "book" && item.price == 3000)
item.price = 100000;
}
Console.WriteLine("\n");
Console.WriteLine("-------- after updating ItemList by foreach--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n\n");
Console.WriteLine("-------updated by iterator --------");
for (LinkedListNode<Item> ItemNode = ItemList.First; ItemNode != null; ItemNode = ItemNode.Next)
{
Console.Write($"({ItemNode.Value.name} : {ItemNode.Value.price}) ");
if (ItemNode.Value.name == "book" && ItemNode.Value.price == 100000)
ItemNode.Value.price = 3000;
}
Console.WriteLine("\n");
Console.WriteLine("-------- after updating ItemList by iterator--------");
foreach (Item item in ItemList)
Console.Write($"({item.name} : {item.price}) ");
Console.WriteLine("\n\n");
return;
}
}
}
실행결과는 다음과 같다.
C++에서 Iterator는 .begin()으로 시작하여 ++iterator, iterator++ 연산자를 통해서 뒤로 전진한다.
이 처럼, .First 속성을 사용해서 .begin()처럼 첫 번째 원소를 참조하는 LinkedListNode자료형 값을 반환받고 한 칸씩 증가하면서 null이 아닐 때까지 탐색하는 방법으로 용어만 다르지 원리는 똑같다.
그런데 MSDN에 의하면 이러한 iterator관리가 어려워서 일부러 숨겼다고 한다. .Enumerator()함수 설명에 들어가 보니 그렇게 나와있었다. 그래서 for each문을 사용해서 탐색하길 권장하고 있었다.
class는 무조건 참조 복사인데,, 값 복사를 하고 싶으면 .clone()이었나 이것도 뭘 구현해야 했었던 것 같다.(IClonable인가..?)
마치며..
C++에서는 linked list도 멤버 변수로 정렬 기능을 제공했던 것 같은데, C#에서는 제공하고 있는지 안 하는지 잘 모르겠습니다. 어쨌든, 삽입 삭제가 빈번한 경우 사용하기 좋은 그런 자료구조입니다.
LinkedList<T>는 LinkedListNode<T> ↔ LinkedListNode<T> ↔ LinkedListNode<T> ↔ LinkedListNode<T> ↔null로 이루어져 있다고 머릿속으로 그림만 그릴 줄 안다면 이 자료구조는 90% 정도 다 알고 있다고 해도 무방하다고 봅니다.
이 글이 다른 분께 도움이 되었으면 좋겠습니다.
감사합니다.
'개발 > C#' 카테고리의 다른 글
| [C#/Collection] Dictionary<TKey, TValue>, SortedDictionary<TKey, TValue> 분석 (0) | 2021.08.12 |
|---|---|
| [C# / Collection] SortedSet<T>, HashSet<T>분석 (0) | 2021.08.09 |
| [C#/JSON] JSON parser 구현 (0) | 2021.01.02 |
| [C#/ XML] XML parser 구현 (0) | 2021.01.01 |
| [C#/API] Naver 파파고 번역 API 사용해보기 (Papago/네이버 API, Naver API) (0) | 2020.12.19 |