이중 연결 리스트 (Doubly Linked List)의 개념 및 구현

이중 연결 리스트(Doubly Linked List)는 연결 리스트의 확장된 형태로, 각 노드가 이전 및 다음 노드를 가리키는 포인터를 통해 양방향으로 연결된 데이터 구조입니다. 단일 연결 리스트(Singly Linked List)보다 삽입, 삭제, 탐색 연산에 더 유연하게 접근할 수 있어 데이터 구조와 알고리즘 학습에 중요한 개념입니다. 이번 포스팅에서는 이중 연결 리스트의 개념, 주요 특징, 연산, 그리고 C#을 이용한 구현을 살펴보겠습니다.

---

1. 이중 연결 리스트란?

이중 연결 리스트는 각 노드(Node)가 데이터와 두 개의 링크(Link)를 가지는 연결 리스트입니다.
하나의 링크는 이전 노드(previous)를, 다른 하나는 다음 노드(next)를 가리킵니다.
이를 통해 리스트의 양방향 접근이 가능해, 단일 연결 리스트보다 다양한 연산을 보다 효율적으로 수행할 수 있습니다.

이중 연결 리스트의 구조

• 노드(Node): 데이터를 저장하고 두 개의 포인터를 가지는 리스트의 기본 단위.
• 데이터(Data): 노드가 보유하는 값.
• 이전 링크(Previous Link): 이전 노드를 가리키는 포인터. 첫 번째 노드에서는 null이 됩니다.
• 다음 링크(Next Link): 다음 노드를 가리키는 포인터. 마지막 노드에서는 null이 됩니다.

---

2. 이중 연결 리스트의 주요 연산

이중 연결 리스트의 주요 연산은 노드의 삽입, 삭제, 탐색, 출력 등이 있습니다. 양방향으로 이동이 가능하므로 단일 연결 리스트에 비해 연산 효율성이 높습니다.

2.1 삽입 (Insert)

이중 연결 리스트에 새 노드를 추가하는 연산입니다. 삽입 위치에 따라 연산이 조금씩 달라집니다.

• 처음에 삽입: 헤드를 새 노드로 설정하고 기존 헤드 노드를 새 노드의 다음 노드로 연결합니다.
• 중간에 삽입: 새 노드와 해당 위치의 이전 및 다음 노드를 연결해 양방향 링크를 설정합니다.
• 끝에 삽입: 리스트의 마지막 노드를 새 노드의 이전 노드로 설정하고, 새 노드를 리스트의 끝에 추가합니다.

2.2 삭제 (Delete)

특정 노드를 이중 연결 리스트에서 제거하는 연산입니다.

• 처음 노드 삭제: 헤드를 다음 노드로 변경하고 새로운 헤드의 이전 링크를 null로 설정합니다.
• 중간 노드 삭제: 삭제할 노드의 이전 및 다음 노드를 연결하여 해당 노드를 제거합니다.
• 마지막 노드 삭제: 마지막 노드를 이전 노드와 연결해 제거합니다.

2.3 탐색 (Search)

특정 데이터를 가진 노드를 찾아내는 연산입니다. 이중 연결 리스트에서는 양방향으로 탐색할 수 있어 효율적입니다.

2.4 출력 (Display)

모든 노드를 출력하며, 양방향 탐색이 가능하므로 원하는 방향으로 순차적으로 출력할 수 있습니다.

---

3. 이중 연결 리스트의 구현 - C# 코드 예제

이중 연결 리스트는 아래와 같이 C#으로 구현할 수 있습니다.

3.1 노드 클래스 정의

각 노드는 데이터를 포함하며, 이전과 다음 노드를 가리키는 링크를 포함합니다.

public class Node
{
    public int Data;
    public Node Prev;
    public Node Next;

    public Node(int data)
    {
        Data = data;
        Prev = null;
        Next = null;
    }
}

3.2 이중 연결 리스트 클래스 정의

이중 연결 리스트 클래스에는 삽입, 삭제, 탐색, 출력 메서드를 포함합니다.

public class DoublyLinkedList
{
    private Node head;

    // 리스트의 처음에 노드 삽입
    public void InsertFirst(int data)
    {
        Node newNode = new Node(data);
        newNode.Next = head;
        
        if (head != null)
        {
            head.Prev = newNode;
        }
        
        head = newNode;
    }

    // 리스트의 끝에 노드 삽입
    public void InsertLast(int data)
    {
        Node newNode = new Node(data);

        if (head == null)
        {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        
        current.Next = newNode;
        newNode.Prev = current;
    }

    // 특정 데이터를 가진 노드 삭제
    public void Delete(int data)
    {
        if (head == null) return;

        Node current = head;

        while (current != null && current.Data != data)
        {
            current = current.Next;
        }

        if (current == null) return;

        if (current.Prev != null)
        {
            current.Prev.Next = current.Next;
        }
        else
        {
            head = current.Next;
        }

        if (current.Next != null)
        {
            current.Next.Prev = current.Prev;
        }
    }

    // 리스트 출력 (처음부터 끝까지)
    public void Display()
    {
        Node current = head;
        while (current != null)
        {
            Console.Write(current.Data + " <-> ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }

    // 특정 데이터를 가진 노드 탐색
    public bool Search(int data)
    {
        Node current = head;
        while (current != null)
        {
            if (current.Data == data)
            {
                return true;
            }
            current = current.Next;
        }
        return false;
    }
}

3.3 사용 예시

아래는 이중 연결 리스트 클래스를 이용하여 노드를 추가, 삭제, 탐색하는 예제입니다.

public class Program
{
    public static void Main()
    {
        DoublyLinkedList list = new DoublyLinkedList();

        list.InsertFirst(1);
        list.InsertLast(2);
        list.InsertLast(3);

        Console.WriteLine("리스트 출력:");
        list.Display();

        Console.WriteLine("2 삭제 후 리스트 출력:");
        list.Delete(2);
        list.Display();

        Console.WriteLine("3 탐색 결과:");
        Console.WriteLine(list.Search(3) ? "3이 리스트에 있습니다." : "3이 리스트에 없습니다.");
    }
}

 

---

4. 이중 연결 리스트의 장점과 단점

장점

• 양방향 탐색 가능: 노드를 양방향으로 접근할 수 있어 삽입과 삭제가 효율적입니다.
• 유연한 노드 추가/삭제: 특정 위치에서의 삽입, 삭제가 용이합니다.

단점

• 메모리 오버헤드: 각 노드가 두 개의 포인터를 가지므로 단일 연결 리스트보다 더 많은 메모리를 사용합니다.
• 구현 복잡도: 양방향 링크 설정이 필요해 단일 연결 리스트에 비해 구현이 복잡합니다.

---

이중 연결 리스트는 양방향 탐색이 가능하고 유연한 데이터 구조로, 리스트의 중간에서 노드를 자주 추가하거나 삭제해야 하는 상황에서 특히 유용합니다. 배열과 단일 연결 리스트에 비해 구현이 다소 복잡하지만, 이를 통해 다양한 데이터 구조 문제를 해결할 수 있습니다. 이중 연결 리스트의 개념을 이해하고 직접 구현해보면, 데이터 구조를 보다 깊이 이해하는 데 도움이 될 것입니다.