Part3. C# 실력다지기(4. LinkedList 이해하기)

LinkedList 이해하기

 

안녕하세요 토담이 아빠입니다. 지난 2달 동안 육아 및 기타 등등의 이유로 포스팅을 미뤄왔었는데요, 오늘부터 자주는 아니지만 조금씩 포스팅을 다시 시작하겠습니다. 그러면 이번 포스팅에서는 LinkedList에 대해서 알아보도록 하겠습니다.

LinkedList는 .NET Framework의 일부로서 C#에서 제공하는 강력한 자료 구조 중 하나입니다. 이 자료 구조는 동적 데이터를 효과적으로 처리하며, 고정 길이 배열의 한계를 해결하는 데 매우 유용합니다.

 

LinkedList란 무엇인가?

LinkedList는 '노드'라는 요소들이 서로 연결되어 있는 선형 데이터 구조입니다. 각 노드는 두 부분으로 구성되어 있습니다: 하나는 데이터를 저장하는 부분이고, 다른 하나는 다음 노드에 대한 참조(포인터)입니다. 이렇게 노드들이 서로 연결된 구조가 바로 LinkedList입니다.

 

LinkedList에는 '이중 연결 리스트'와 단일 연결 리스트'  두 가지 주요 형태가 있습니다. 이중 연결 리스트에서는 각 노드가 이전 노드와 다음 노드에 대한 참조를 가지고 있습니다. 반면에 단일 연결 리스트에서는 각 노드가 오직 다음 노드에 대한 참조만을 가집니다. C#에서 제공하는 LinkedList 클래스는 이중 연결 리스트를 구현하고 있습니다.

 

LinkList를 언제 사용해야 하는가?

 

LinkedList는 다음과 같은 상황에서 사용하는 것이 적합합니다.

 

• 자료의 크기를 미리 알 수 없는 경우
• 데이터의 중간에 삽입 또는 삭제가 빈번하게 발생하는 경우

 

C#에서 LinkedList 사용하기

 

C#에서 LinkedList를 사용하려면 먼저 'System.Collections.Generic'네임 스페이스를 참조해야 합니다.

다음은 LinkedList를 생성하고 항목을 추가하는 예제입니다.

---

LinkedList<string> linkedList = new LinkedList<string>();
linkedList.AddLast("Apple");
linkedList.AddLast("Banana");
linkedList.AddLast("Cherry");

---

LinkedList에 요소를 삽입하거나 삭제하는 것도 매우 간단합니다.

---

// "Banana" 뒤에 "Blueberry" 삽입
LinkedListNode<string> node = linkedList.Find("Banana");
if (node != null)
{
    linkedList.AddAfter(node, "Blueberry");
}

// "Apple" 삭제
node = linkedList.Find("Apple");
if (node != null)
{
    linkedList.Remove(node);
}

---

LinkedList를 순회하는 것도 매우 쉽습니다.

---

foreach (string fruit in linkedList)
{
    Console.WriteLine(fruit);
}

---

LinkedList는 노드의 삽입과 삭제가 자주 발생하며, 데이터의 크기를 미리 알 수 없는 상황에서 유용한 자료 구조입니다. C#의 LinkedList 클래스는 이중 연결 리스트를 쉽게 구현하도록 도와주며, 다양한 메서드를 제공하여 사용자의 부담을 줄여줍니다. 하지만 임의의 위치에 접근하는 데에는 시간이 많이 걸리므로, 이러한 요구가 있는 경우 ArrayList나 Array를 사용하는 것이 좋습니다.

 

 

LinkedList 직접구현

 

LinkedList를 직접 구현하려면 먼저 Node 클래스를 만들어야 합니다. 이 Node 클래스는 데이터를 저장하는 Value 필드와 다음 Node에 대한 참조를 저장하는 Next 필드를 가집니다. 이제 LinkedList를 구현해 보겠습니다.

---

public class Node<T>
{
    public T Value { get; set; }
    public Node<T> Next { get; set; }

    public Node(T value)
    {
        Value = value;
    }
}

public class MyLinkedList<T>
{
    private Node<T> head = null;
    private Node<T> tail = null;

    public void AddLast(T value)
    {
        var newNode = new Node<T>(value);

        if (head == null)
        {
            head = newNode;
            tail = head;
        }
        else
        {
            tail.Next = newNode;
            tail = newNode;
        }
    }

    public bool Remove(T value)
    {
        if (head == null)
        {
            return false;
        }

        if (head.Value.Equals(value))
        {
            head = head.Next;
            return true;
        }

        var current = head;
        while (current.Next != null)
        {
            if (current.Next.Value.Equals(value))
            {
                current.Next = current.Next.Next;
                return true;
            }
            current = current.Next;
        }

        return false;
    }

    public void Print()
    {
        var current = head;
        while (current != null)
        {
            Console.WriteLine(current.Value);
            current = current.Next;
        }
    }
}

---

위의 MyLinkedList 클래스는 제네릭 타입 T를 사용하여 어떤 타입의 데이터도 저장할 수 있도록 했습니다. AddLast 메서드는 리스트의 마지막에 새 노드를 추가하고, Remove 메서드는 주어진 값을 가진 노드를 찾아 제거합니다. Print 메서드는 리스트의 모든 노드를 출력합니다.

이제 이를 사용하는 예를 보겠습니다.

var myLinkedList = new MyLinkedList<string>();
myLinkedList.AddLast("Apple");
myLinkedList.AddLast("Banana");
myLinkedList.AddLast("Cherry");
myLinkedList.Print(); // Apple, Banana, Cherry 출력
myLinkedList.Remove("Banana");
myLinkedList.Print(); // Apple, Cherry 출력

---

이것이 C#을 사용하여 LinkedList를 직접 구현하는 간단한 방법입니다. 이 구현은 기본적인 기능만 포함하고 있으므로, 실제로 사용하려면 더 많은 기능과 에러 처리를 추가해야 할 수 있습니다.