[C#] 링크드 리스트 (Linked List)

 

1. 링크드 리스트(Linked List)란?

 

C#의 링크드 리스트(Linked List)는 데이터 구조의 한 현태로, 각 요소가 노드(Node)로 구성되며, 각 노드는 데이터와 다음 노드에 대한 참조를 포함합니다. 링크드 리스트는 동적 메모리 할당을 통해 크기가 가변적이며, 연속적인 메모리 주소에 저장되는 것이 아닌, 비 연속적으로 저장이 되며 이전, 다음 노드 정보를 통해 데이터를 연결합니다.
이러한 구조로 배열과 달리 요소의 삽입 및 삭제가 용이하다는 장점이 있습니다.
'System.Collections.Generic' 네임스페이스에 포함된 'LinkedList<T>' 클래스를 사용하여 링크드 리스트를 구현할 수 있습니다.

 

 

 

---

2. 내부 작동 구조

 

링크드 리스트는 주로 세 가지 유형이 있습니다.

 

1. 단일 링크드 리스트(Singly Linked List): 각 노드는 다음 노드를 가리키는 포인터 하나를 가집니다.

2. 이중 링크드 리스트(Doubly Linked List): 각 노드는 다음 노드와 이전 노드를 가리키는 두 개의 포인터를 가집니다.

3. 원형 링크드 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 단일 또는 이중 링크드 리스트입니다.

 

C#의 'LinkedList<T>'는 이중 링크드 리스트를 구현한 것입니다. 각 노드는 'LinkedListNode<T>' 객체로 표현되며, 이 객체는 'Value', 'Next', 'Prvious' 프로퍼티를 가지고 있습니다.

 

예를 들어, C# 링크드 리스트의 구조는 다음과 같습니다.

• Node1: Value | Next -> Node2 | Previous -> null
• Node2: Value | Next -> Node3 | Previous -> Node1
• Node3: Value | Next -> null | Previous -> Node2

 

 

 

---

3. 주요 메서드

 

 

1. AddFirst(T value): 리스트의 시작 부분에 새로운 노드를 추가합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddFirst(1);
list.AddFirst(2); // 2 -> 1

 

 

2. AddLast(T value): 리스트의 끝 부분에 새로운 노드를 추가합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2); // 1 -> 2

 

 

3. AddBefore(LinkedListNode<T> node, T value): 지정된 노드 앞에 새로운 노드를 추가합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(3);
LinkedListNode<int> node = list.Find(3);
list.AddBefore(node, 2); // 1 -> 2 -> 3

 

 

4. AddAfter(LinkedListNode<T> node, T value): 지정된 노드 뒤에 새로운 노드를 추가합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
LinkedListNode<int> node = list.Find(1);
list.AddAfter(node, 1.5); // 1 -> 1.5 -> 2

 

 

5. Remove(T value): 첫 번째로 일치하는 요소를 리스트에서 제거합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.Remove(1); // 2만 남음

 

 

6. RemoveFirst(): 리스트의 첫 번째 노드를 제거합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.RemoveFirst(); // 2만 남음

 

 

7. RemoveLast(): 리스트의 마지막 노드를 제거합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.RemoveLast(); // 1만 남음

 

 

8. Find(T value): 리스트에서 첫 번째로 일치하는 노드를 찾습니다. 찾은 노드를 반환하며, 찾지 못한 경우 null을 반환합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
LinkedListNode<int> node = list.Find(2); // node는 값이 2인 노드를 가리킴

 

 

9. Contains(T value): 리스트에 특정 값이 포함되어 있는지 여부를 확인합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
bool contains = list.Contains(2); // true

 

 

10. Clear(): 리스트의 모든 노드를 제거합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
list.Clear(); // 리스트가 비어있음

 

 

11. First: 리스트의 첫번째 노드를 가져옵니다. 노드가 없는 경우 null을 반환합니다.

LinkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
LinkedListNode<int> firstNode = list.First; // firstNode는 값이 1인 노드를 가리킴
int firstValue = firstNode.Value; // 1

 

 

12. Last: 리스트의 마지막 노드를 가져옵니다. 노드가 없는 경우 null을 반환합니다.

inkedList<int> list = new LinkedList<int>();
list.AddLast(1);
list.AddLast(2);
LinkedListNode<int> lastNode = list.Last; // lastNode는 값이 2인 노드를 가리킴
int lastValue = lastNode.Value; // 2

 

 

 

---

4. 시간복잡도

 

• 삽입(Insertion):
  • 리스트의 시작이나 끝에 삽입하는 경우: O(1)
  • 리스트의 중간에 삽입하는 경우: O(n)

 

• 삭제(Deletion):
  • 리스트의 시작이나 끝에서 삭제하는 경우: O(1)
  • 리스트의 중간에서 삭제하는 경우: O(n)

 

• 검색(Search): 특정 값을 찾는 경우: O(n)

 

• 접근(Access): 인덱스를 기반으로 값에 접근하는 경우: O(n)

 

링크드 리스트는 데이터의 삽입 및 삭제가 빈번한 경우에는 유리합니다. 하지만 특정 인덱스에 접근하는 경우 배열에 비해 비효울적인 자료구조입니다.

 

 

 

---

5. 핵심 정리

1. 유연한 크기  조절: 링크드 리스트는 동적 메모리 할당을 통해 크기를 자유롭게 조절할 수 있습니다.
2. 삽입 및 삭제의 용이성: 배열에 비해 요소의 삽입 및 삭제가 간편합니다.
3. 느린 접근 시간: 특정 인덱스에 대한 접근 시간이 배열에 비해 느립니다.
4. 이중 링크드 리스트: C#의 LinkedList는 이중 링크드 리스트로 구현되어 있어, 양방향 탐색이 가능합니다.
5. 주요 메서드와 속성: AddFirst, AddLast, Remove, Find, Contains, Clear, First,  Last등 다양한 메서드와 속성을 통해 리스트를 효과적으로 관리할 수 있습니다.

 

 

 

---

6. 결론

 

C#의 링크드 리스트는 동적 데이터 구조로, 배열에 비해 삽입 및 삭제가 용이하지만, 특정 인덱스 접근이 느리다는 단점이 있습니다. LinkedList<T> 클래스를 사용하면 이중 링크드 리스트의 장점을 활용할 수 있으며, 특정 용도에 적합한 데이터 구조를 선택하는 것이 중요합니다. 데이터의 삽입, 삭제가 빈번한 상황에서는 링크드 리스트를, 빠른 접근이 필요한 상황에서는 배열을 사용하는 것이 효율적입니다.

링크드 리스트는 알고리즘과 데이터 구조를 이해하는 데 중요한 개념이며, 이를 잘 활용하면 더 효율적인 코드를 작성할 수 있습니다.

 

 

 

---

지금까지 링크드리스트에 대해 알아보았습니다.

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