C++ 쟁이가 C#을 배워보자 - List / LinkedList / SortedList

이번 포스트는 C#에서 제공하는 List 컬렉션들이다. 이름만 보더라도 딱 감이 오지 않는가? List는 그냥 봐도 일반(?) 리스트, LinkedList는 자료구조시간에 배우는 연결리스트, SortedList는 이전 포스트에서 다뤘던 SortedSet과 비슷한 느낌의 정렬된 리스트이다.

1. List

얼핏 보면 Set과 유사한 듯 싶지만 중복을 허용하지 않는 Set과는 달리 List는 중복을 허용한다. 또한 컬렉션 이름에서 볼 수 있듯이 컬렉션에 Add한 데이터를 Add한 순서대로 가지고 있는 자료구조이다.
리스트를 사용하는 방법은 Set과 유사하게 List<자료형> 형태로 선언하여 가능하다. 아래는 문자열  형을 리스트로 선언한 코드.

List<string> list = new List<string>();

리스트에 항목을 추가하는 것은 Add와 AddRange 메서드로 가능하다. Add 메서드는 단일 항목을, AddRange는 IEnumerable 인터페스를 구현한 컬렉션 객체를 추가할 때 사용한다.

list.Add("Iron Man");
list.Add("The Incredible Hulk");
list.Add("Iron Man2");
list.Add("Thor");
list.Add("Captain America: The First Avenger");
list.Add("Marvel's The Avengers");
list.Add("Iron Man 3");
list.Add("Thor: The Dard World");
list.Add("Captain America: The Winter Soldier");
list.Add("Guardians of the Galaxy");
list.Add("Avengers: Age of Ultron");
list.Add("Ant-Man");
list.Add("Captain America: Civil War");
list.Add("Doctor Strange");
list.Add("Guardians of Galaxy VOL. 2");
list.Add("Spider-Man: Homecoming");
list.Add("Thor: Ragnarok");
list.Add("Black Panther");
list.Add("Avengers: Infinity War");

위 코드는 2008년 ~ 2018년 개봉한 마블의 영화를 순서대로 리스트에 추가한 코드이다.리스트에 추가한 항목들을 꺼내는 방법은 foreach를 이용하여 처음부터 끝까지 순차적으로 접근을 할 수도 있지만 배열 첨자를 이용하여 인덱스 기반으로도 접근이 가능하다.

//인덱스 기반으로 리스트의 항목들을 출력
for(int i = 0; i < list.Count; i++)
{
    System.Console.WriteLine($"{list[i]}");
}

리스트에서의 항목 삭제는 Remove / RemoveAt으로 단일 항목 삭제가 가능하고, 다수 항목의 삭제는 RemoveAll / RemoveRange를 통해 가능하다.Remove 메서드로 단일 항목 삭제 시 유의해야 할 점은, 중복이 가능한 리스트 특성상, Remove의 파라미터로 넘긴 값과 동일한 "첫번째" 항목만이 삭제가 된다는 것이다.

list.Add("Iron Man");
list.Add("The Incredible Hulk");
list.Add("Iron Man2"); // 아래 Remove 메서드 호출로 이 항목이 삭제된다.
list.Add("Thor");
list.Add("Iron Man2"); // 이 항목은 동일하게 Iron Man2 이지만 삭제되지 않는다.

list.Remove("Iron Man2"); // 첫번째 Iron Man2 항목만 삭제된다.

2. LinkedList

LinkedList는 엄밀히 말하면 이중 연결 리스트(Doubly Linked List) 형태의 컬렉션이다. 이 말은 리스트의 노드가 값 외에 이전(Previous), 다음(Next) 노드의 레퍼런스를 가지고 있다는 것을 의미한다.자료구조 시간이 아니므로 간략하게 단일 연결 리스트와 이중 연결 리스트의 차이점을 보면 다음과 같다.

단일 연결 리스트 (출처: 위키피디아 연결 리스트 항목)

이중 연결 리스트 (출처: 위키피디아 연결 리스트 항목)

위 그림에서 볼 수 있듯이 단일 연결 리스트는 현재 노드의 다음 노드가 무엇인지만 아는 것이고, 이중 연결 리스트는 아래 그림과 같이 현재 노드의 이전, 다음 노드 둘 다 아는 형태이다.장점은 단일 연결 리스트는 정순회만 가능한 반면 이중 연결 리스트는 역으로 순회하는 것이 가능하다.단점은 이중 연결 리스트가 이전 노드의 정보를 가져야 하기 때문에 데이터 크기가 약간 더 크다는 점이다.

연결 리스트 컬렉션의 선언과 기본적인 사용법은 다음과 같다.

LinkedList<int> illist = new LinkedList<int>();
for (int i = 1; i <= 10; i++)
{
    illist.AddLast(i);
}

연결 리스트에 아이템을 추가하는 AddLast 메서드는 리스트의 맨 뒤에 추가하기 위한 메서드이다. 반대로 맨 앞에 추가하는 메서드는 AddFirst이다.리스트 중간에 노드를 추가하는 방법은 AddAfter / AddBefore 메서드가 있는데 이는 기준 노드를 알고 있어야 사용이 가능하다.

LinkedListNode node = illist.First;
node = node.Next;
node = illist.AddAfter(node, 100);

위 코드는 세번째 위치에 100을 추가하는 코드이다. 여기서 AddAfter가 아닌 AddBefore로 노드를 추가하게 되면 두번째 위치에 100이 추가가 되고 기존의 노드들은 한칸씩 뒤로 밀리게 된다.
노드 제거 메서드는 RemoveFirst와 RemoveLast를 사용하면 된다. 이는 이름에서 알 수 있듯이 맨 처음 노드와 맨 마지막 노드를 제거하는 메서드이다. 그냥 Remove 메서드는 파라미터로 입력한 값이 첫번째로 나오는 노드를 제거하게 된다.

illist.Remove(100); // 값이 100인 노드 제거
illist.RemoveFirst(); // 헤드 노드 제거
illist.RemoveLast(); // 테일 노드 제거

각 노드에 접근하는 방법은 First / Last 멤버를 통해 직접 노드를 가져다 쓰는 방법과 아래 코드처럼 foreach를 통해 전체 노드를 순차적으로 접근하는 방법이 있다.

foreach (var item in illist)
{
    System.Console.WriteLine($"{item}");
}

3. SortedList

정렬된 리스트 컬렉션은 SortedSet과 유사한 느낌이나 정렬의 기준이 값이 아닌 별도의 키를 받아 하게 되어 있다. 또한 위 두가지 리스트 같이 값은 중복이 가능하나 정렬 기준인 키는 중복이 불가능하다. 또한 다른 리스트와는 다르게 key-value 형태로 구성을 해야 한다. 이는 추후 포스팅 할 Dictionary 컬렉션과 유사하다.
정수형 키와 문자열 값을 가지는 정렬된 리스트는 다음과 같이 선언 및 사용이 가능하다.

SortedList<int, string> slist = new SortedList<int, string>();

slist.Add(2008, "Iron Man");
slist.Add(2008, "The Incredible Hulk");//에러!
slist.Add(2010, "Iron Man2");
slist.Add(2011, "Thor");
slist.Add(2011, "Captain America: The First Avenger");//에러!
slist.Add(2012, "Marvel's The Avengers");
slist.Add(2013, "Iron Man 3");
slist.Add(2013, "Thor: The Dard World");//에러!
slist.Add(2014, "Captain America: The Winter Soldier");
slist.Add(2014, "Guardians of the Galaxy");//에러!
slist.Add(2015, "Avengers: Age of Ultron");
slist.Add(2015, "Ant-Man");//에러!
slist.Add(2016, "Captain America: Civil War");
slist.Add(2016, "Doctor Strange");//에러!
slist.Add(2017, "Guardians of Galaxy VOL. 2");
slist.Add(2017, "Spider-Man: Homecoming");//에러!
slist.Add(2017, "Thor: Ragnarok");//에러!
slist.Add(2018, "Black Panther");
slist.Add(2018, "Avengers: Infinity War");//에러!

그러나 위에서 설명했듯이 키가 중복되면 에러가 발생하므로 위의 코드는 런타임시 아래와 같은 오류를 발생시키고 종료하게 된다.

Unhandled Exception: System.ArgumentException: An item with the same key has already been added. Key: 2008
Parameter name: key
   at System.Collections.Generic.SortedList`2.Add(TKey key, TValue value)

key 혹은 value 값으로 정렬된 리스트에 이미 존재하는 값인지를 확인하고 싶은 경우에는 ContainsKey / ContainsValue 메서드를 사용하면 쉽게 알 수 있다.

if (slist.ContainsKey(201602) == true)
{
    System.Console.WriteLine("201602 exists");
}
else
{
    System.Console.WriteLine("201602 does not exists");
}

if (slist.ContainsValue("Avengers 4") == true)
{
    System.Console.WriteLine("Avengers 4 exists");
}
else
{
    System.Console.WriteLine("Avengers 4 does not exists");
}

정렬된 리스트의 각 항목에 접근하는 방법은 기존 다른 컬렉션과 마친가지로 foreach로 접근하는 방법이 있다. 아래 코드에서는 KeyValuePair 형태로 선언이 되므로 Key / Value 멤버를 통해 각각의 값에 접근이 가능하다.

foreach (var item in slist)
{
    System.Console.WriteLine($"{item.Key} : {item.Value}");
}

또한 배열 첨자를 사용하여 직접 key값을 넣어 접근하는 방법도 가능하다. 배열 첨자라고 인덱스로 접근한다 생각하면 경기도 오산이다.

System.Console.WriteLine($"{slist[201602]}"); // Doctor Strange 출력