C# 링크드 리스트 구현 정리

C# 링크드 리스트 구현 정리

1. ForwardLinkedList (단일 연결 리스트)

구조

ForwardLinkedList<T>는 각 노드가 다음 노드만 참조하는 단일 연결 리스트다.

노드는 다음 세 가지 요소를 가진다.

• Value: 노드에 저장된 데이터
• Next: 다음 노드를 가리키는 참조
• List: 노드가 소속된 리스트

리스트는 head와 tail을 관리한다.

• head: 첫 번째 노드
• tail: 마지막 노드

이전 노드를 가리키는 참조가 없기 때문에 뒤에서 앞으로 이동할 수 없다.

주요 메서드

AddFirst(T value)

새 노드를 생성하고 기존 head를 새 노드의 Next에 연결한다. 이후 head를 새 노드로 변경한다.

리스트가 비어 있다면 tail도 새 노드를 가리키도록 한다.

AddLast(T value)

새 노드를 생성한 뒤 기존 tail의 Next에 연결한다. 이후 tail을 새 노드로 변경한다.

리스트가 비어 있다면 head와 tail 모두 새 노드를 가리킨다.

AddAfter(node, value)

지정한 노드의 다음 위치에 새 노드를 삽입한다.

새 노드의 Next를 기존 다음 노드로 연결하고, 지정한 노드의 Next가 새 노드를 가리키도록 변경한다.

지정한 노드가 마지막 노드라면 AddLast()를 사용한다.

AddBefore(node, value)

지정한 노드의 바로 앞에 새 노드를 삽입한다.

단일 연결 리스트는 이전 노드를 직접 참조할 수 없으므로 head부터 순회해 지정한 노드의 이전 노드를 찾는다.

따라서 중간에 삽입할 때 O(n)이 걸린다.

Remove(node)

삭제할 노드를 찾은 다음 이전 노드의 Next를 삭제할 노드의 다음 노드로 연결한다.

삭제 대상이 첫 번째 노드라면 head를 변경한다. 마지막 노드라면 tail도 이전 노드로 변경한다.

삭제한 노드의 Next와 List를 null로 변경하고 Count를 감소시킨다.

단일 연결 리스트는 이전 노드를 찾아야 하므로 노드를 알고 있더라도 삭제 작업은 O(n)이다.

Find(value) / Contains(value)

head부터 순회하며 값을 비교한다.

Find()는 일치하는 노드를 반환하고, Contains()는 해당 값의 존재 여부를 반환한다.

Clear()

모든 노드의 연결을 해제한 뒤 head, tail을 null로 변경하고 Count를 0으로 초기화한다.

Backward()

제공하지 않는다. 이전 노드를 가리키는 참조가 없기 때문에 역방향 순회가 불가능하다.

특징

• 구조가 단순하다.
• 앞에 삽입하거나 앞에서 삭제하는 작업이 빠르다.
• 이전 노드를 찾으려면 처음부터 순회해야 한다.
• 끝에 추가하는 작업은 tail을 관리하므로 O(1)이다.

---

2. DoublyLinkedList (이중 연결 리스트)

구조

DoublyLinkedList<T>는 각 노드가 이전 노드와 다음 노드를 모두 참조하는 이중 연결 리스트다.

노드는 다음 네 가지 요소를 가진다.

• Value: 노드에 저장된 데이터
• Next: 다음 노드를 가리키는 참조
• Previous: 이전 노드를 가리키는 참조
• List: 노드가 소속된 리스트

리스트는 head와 tail을 관리한다.

이전 노드를 직접 참조할 수 있기 때문에 양방향 이동이 가능하다.

주요 메서드

AddFirst(T value)

새 노드의 Next를 기존 head로 연결한다.

기존 head가 있다면 기존 노드의 Previous가 새 노드를 가리키도록 변경한다.

이후 head를 새 노드로 변경한다.

리스트가 비어 있다면 tail도 새 노드를 가리킨다.

AddLast(T value)

새 노드의 Previous를 기존 tail로 연결한다.

기존 tail의 Next가 새 노드를 가리키도록 변경하고, tail을 새 노드로 변경한다.

리스트가 비어 있다면 head와 tail 모두 새 노드를 가리킨다.

AddAfter(node, value)

지정한 노드의 다음 위치에 새 노드를 삽입한다.

새 노드의 Previous는 지정한 노드, Next는 기존 다음 노드를 가리킨다.

기존 다음 노드의 Previous도 새 노드를 가리키도록 변경한다.

지정한 노드가 마지막 노드라면 AddLast()를 사용한다.

AddBefore(node, value)

지정한 노드의 이전 위치에 새 노드를 삽입한다.

새 노드의 Next는 지정한 노드, Previous는 기존 이전 노드를 가리킨다.

기존 이전 노드의 Next와 지정한 노드의 Previous도 새 노드를 가리키도록 변경한다.

지정한 노드가 첫 번째 노드라면 AddFirst()를 사용한다.

Remove(node)

삭제할 노드의 이전 노드와 다음 노드를 서로 연결한다.

이전 노드가 있다면 이전 노드의 Next를 다음 노드로 변경한다. 이전 노드가 없다면 head를 다음 노드로 변경한다.

다음 노드가 있다면 다음 노드의 Previous를 이전 노드로 변경한다. 다음 노드가 없다면 tail을 이전 노드로 변경한다.

삭제한 노드의 Next, Previous, List를 null로 변경하고 Count를 감소시킨다.

노드를 이미 알고 있다면 이전 노드와 다음 노드에 바로 접근할 수 있으므로 O(1)이다.

Find(value) / Contains(value)

head부터 Next를 따라 순회하며 값을 검색한다.

Clear()

모든 노드의 Next, Previous, List를 null로 변경한다.

이후 head, tail을 null로 변경하고 Count를 0으로 초기화한다.

Backward()

tail부터 시작해 Previous를 따라 이동한다.

마지막 노드부터 첫 번째 노드까지 역방향으로 순회할 수 있다.

특징

• 이전 노드와 다음 노드를 모두 참조한다.
• 노드를 알고 있다면 삽입과 삭제가 O(1)이다.
• 정방향과 역방향 순회가 가능하다.
• 단일 연결 리스트보다 노드당 메모리를 더 사용한다.
• 삽입과 삭제 과정에서 변경해야 할 참조가 많다.

---

3. CircularDoublyLinkedList (원형 이중 연결 리스트)

구조

CircularDoublyLinkedList<T>는 이중 연결 리스트에 원형 구조를 추가한 자료구조다.

일반적인 이중 연결 리스트는 첫 번째 노드의 Previous와 마지막 노드의 Next가 null이다.

하지만 원형 이중 연결 리스트는 다음과 같이 연결된다.

• 마지막 노드의 next가 첫 번째 노드를 가리킨다.
• 첫 번째 노드의 prev가 마지막 노드를 가리킨다.

따라서 리스트의 처음과 끝이 서로 연결된다.

이 구현은 head만 관리하며, 마지막 노드는 head.prev를 통해 접근한다.

노드의 Next와 Previous

이 구현의 노드는 실제 연결을 저장하는 next, prev 필드와 외부에 제공하는 Next, Previous 프로퍼티를 구분한다.

• next, prev: 실제 원형 연결을 유지한다.
• Next: 다음 노드가 첫 번째 노드라면 null을 반환한다.
• Previous: 현재 노드가 첫 번째 노드라면 null을 반환한다.

즉, 내부적으로는 원형 구조를 유지하면서 외부에서는 일반적인 리스트처럼 끝을 구분할 수 있도록 만든다.

주요 메서드

InsertBefore(target, newNode)

지정한 노드의 바로 앞에 새 노드를 연결하는 내부 메서드다.

새 노드의 prev를 기존 이전 노드로, next를 지정한 노드로 설정한다.

이후 기존 이전 노드의 next와 지정한 노드의 prev가 새 노드를 가리키도록 변경한다.

원형 연결 리스트의 삽입 작업을 공통으로 처리하는 역할을 한다.

AddFirst(T value)

새 노드를 생성한다.

리스트가 비어 있다면 새 노드의 next와 prev가 자기 자신을 가리키도록 설정한다.

리스트에 노드가 있다면 InsertBefore()를 이용해 기존 첫 번째 노드 앞에 삽입하고, head를 새 노드로 변경한다.

AddLast(T value)

리스트가 비어 있다면 AddFirst()와 마찬가지로 자기 자신을 가리키는 원형 구조를 만든다.

노드가 있다면 InsertBefore(head, newNode)를 호출한다.

첫 번째 노드 바로 앞에 삽입되므로 새 노드는 마지막 노드가 된다.

AddAfter(node, value)

지정한 노드의 다음 위치에 새 노드를 삽입한다.

지정한 노드의 다음 노드를 기준으로 InsertBefore()를 호출한다.

AddBefore(node, value)

지정한 노드의 바로 앞에 새 노드를 삽입한다.

삽입 대상이 기존 head라면 새 노드를 head로 변경한다.

Remove(node)

삭제할 노드가 리스트의 유일한 노드인지 확인한다.

유일한 노드라면 head를 null로 변경한다.

그렇지 않다면 삭제할 노드의 이전 노드와 다음 노드를 서로 연결한다.

삭제 대상이 head라면 head를 다음 노드로 변경한다.

마지막으로 삭제한 노드의 next, prev, List를 null로 변경하고 Count를 감소시킨다.

노드의 이전 노드와 다음 노드를 바로 알 수 있으므로 O(1)이다.

Find(value) / Contains(value)

head부터 시작해 next를 따라 순회한다.

원형 구조이므로 null만으로 순회를 종료할 수 없다. 처음 시작했던 노드로 돌아오면 순회를 종료한다.

Clear()

모든 노드의 next, prev, List를 null로 변경한다.

원형 구조이므로 시작 노드로 다시 돌아왔는지 확인하면서 순회한다.

모든 노드의 연결을 해제한 뒤 head를 null로 변경하고 Count를 0으로 초기화한다.

Backward()

마지막 노드인 head.prev부터 시작해 prev를 따라 이동한다.

처음 시작했던 노드로 돌아오면 순회를 종료한다.

특징

• 이전 노드와 다음 노드가 원형으로 연결된다.
• 마지막 노드에서 첫 번째 노드로 바로 이동할 수 있다.
• head만 관리하며 마지막 노드는 head.prev로 접근한다.
• 끝을 판단할 때 null이 아니라 시작 노드로 돌아왔는지 확인해야 한다.
• 일반적인 이중 연결 리스트보다 순회 종료 조건을 더 주의해서 작성해야 한다.

---

4. 세 가지 자료구조 비교

5. 공통으로 사용한 구현 개념

제네릭

세 자료구조는 모두 제네릭으로 작성했다.

T를 사용하면 정수, 문자열, 클래스 객체 등 다양한 자료형을 저장할 수 있다.

IEnumerable와 IEnumerator

세 리스트 모두 IEnumerable<T>를 구현한다.

GetEnumerator()에서 yield return을 사용해 노드의 값을 하나씩 반환한다.

따라서 foreach로 리스트를 순회할 수 있다.

yield return

현재 노드의 값을 반환하고 다음 순회 요청이 들어오면 이어서 실행한다.

단일 연결 리스트와 일반 이중 연결 리스트는 Next를 따라 이동한다.

원형 이중 연결 리스트는 시작 노드로 돌아왔는지 추가로 확인한다.

EqualityComparer.Default

Find()에서 값을 비교할 때 사용한다.

제네릭 자료형이 어떤 종류인지 미리 정하지 않아도 해당 자료형의 기본 동등성 비교 방식을 이용할 수 있다.

List와 Count 관리

각 노드는 자신이 속한 리스트를 List에 저장한다.

노드를 추가할 때는 List에 현재 리스트를 저장하고, 제거할 때는 null로 변경한다.

ValidataNode()는 전달받은 노드가 실제로 현재 리스트에 속하는지 확인한다.

이를 통해 다른 리스트의 노드나 이미 제거된 노드를 잘못 사용하는 것을 방지한다.

6. 구현할 때 주의할 부분

연결 관계 유지

이중 연결 리스트는 Next와 Previous를 모두 변경해야 한다.

한쪽 연결만 변경하면 정방향과 역방향 순회 결과가 달라질 수 있다.

빈 리스트와 노드 하나만 있는 리스트

삽입과 삭제를 구현할 때는 다음 상황을 구분해야 한다.

• 리스트가 비어 있는 경우
• 노드가 하나만 있는 경우
• 첫 번째 노드를 처리하는 경우
• 마지막 노드를 처리하는 경우
• 중간 노드를 처리하는 경우

특히 원형 리스트는 노드가 하나만 있어도 자기 자신을 가리키는 구조라는 점에 주의해야 한다.

원형 리스트의 순회

원형 리스트는 마지막 노드의 다음 노드가 null이 아니다.

따라서 단순히 current != null만으로 순회를 종료할 수 없다.

시작 노드를 기억하고 다시 시작 노드에 도달했는지 확인해야 한다.

원형 리스트의 노드 프로퍼티

현재 구현에서 Next와 Previous는 List.First를 참조한다.

노드를 리스트에서 제거하면 List가 null이 되므로, 제거된 노드에서 해당 프로퍼티를 호출하면 예외가 발생할 수 있다.

또한 연결 필드인 next, prev가 외부에 공개되어 있지 않도록 접근 범위를 제한하는 것이 안전하다.

---

7. 최종 정리

• ForwardLinkedList: 다음 노드만 연결하는 가장 단순한 구조다. 이전 노드를 찾는 작업이 필요하므로 중간 삭제와 앞에 삽입하는 작업에 불리하다.
• DoublyLinkedList: 이전 노드와 다음 노드를 모두 연결한다. 노드를 알고 있다면 빠르게 삽입하거나 삭제할 수 있다.
• CircularDoublyLinkedList: 이중 연결 리스트의 마지막과 처음을 연결한다. 처음과 끝이 이어지는 구조가 필요한 경우 활용할 수 있다.

세 자료구조의 핵심 차이는 노드가 어떤 방향으로 연결되어 있는지, 그리고 리스트의 끝을 어떤 방식으로 표현하는지에 있다.