단일 연결 리스트 (Singly Linked List)의 개념 및 구현

단일 연결 리스트(Singly Linked List)는 가장 기본적인 형태의 연결 리스트로, 데이터 구조에서 각 노드가 다음 노드를 가리키는 포인터를 통해 선형으로 연결되는 형태입니다. 배열과는 달리 동적 메모리 할당을 통해 리스트 크기를 유연하게 조절할 수 있어, 효율적인 메모리 사용이 가능합니다. 이번 포스팅에서는 단일 연결 리스트의 개념, 특징, 주요 연산, 그리고 C#을 이용한 구현 방법을 살펴보겠습니다.

---

1. 단일 연결 리스트란?

단일 연결 리스트는 노드(Node)가 연속적으로 연결된 데이터 구조입니다.
각 노드는 데이터와 다음 노드를 가리키는 포인터(링크)로 구성됩니다.
단일 연결 리스트에서는 각 노드가 다음 노드를 가리키므로, 노드 접근은 처음 노드부터 순차적으로 진행됩니다.

단일 연결 리스트의 구조

• 노드(Node): 단일 연결 리스트에서 각 요소를 나타내는 기본 단위입니다.
• 데이터(Data): 각 노드가 보유하는 값.
• 링크(Link): 다음 노드를 가리키는 포인터로, 리스트의 끝 노드에는 null이 저장됩니다.

---

2. 단일 연결 리스트의 주요 연산

단일 연결 리스트는 각종 연산을 통해 데이터 삽입, 삭제, 탐색을 수행할 수 있습니다. 주요 연산에는 다음과 같은 것들이 있습니다.

2.1 삽입 (Insert)

단일 연결 리스트에 새 노드를 추가하는 연산입니다. 위치에 따라 다르게 처리할 수 있습니다.

• 처음에 삽입: 새 노드를 헤드(Head)로 설정하고 기존 헤드를 연결합니다.
• 중간에 삽입: 특정 위치를 찾아 새 노드를 삽입하고 링크를 재구성합니다.
• 끝에 삽입: 리스트 끝의 null을 새 노드로 연결합니다.

2.2 삭제 (Delete)

특정 노드를 단일 연결 리스트에서 삭제하는 연산입니다.

• 처음 노드 삭제: 헤드를 다음 노드로 변경합니다.
• 중간 노드 삭제: 이전 노드가 다음 노드를 가리키도록 재구성합니다.
• 마지막 노드 삭제: 마지막 전 노드가 null을 가리키도록 처리합니다.

2.3 탐색 (Search)

특정 값을 가진 노드를 찾는 연산입니다. 연결 리스트의 경우 순차 탐색을 통해 원하는 값을 찾습니다.

2.4 출력 (Display)

모든 노드를 순서대로 출력하는 연산입니다.

---

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

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

3.1 노드 클래스 정의

먼저 노드 클래스를 정의합니다. 각 노드는 데이터를 저장하고, 다음 노드를 가리키는 링크를 포함합니다.

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

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

3.2 단일 연결 리스트 클래스 정의

단일 연결 리스트를 구성하는 클래스에는 삽입, 삭제, 탐색 등의 메서드가 포함됩니다.

public class SinglyLinkedList
{
    private Node head;

    // 리스트의 처음에 노드 삽입
    public void InsertFirst(int data)
    {
        Node newNode = new Node(data);
        newNode.Next = head;
        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;
    }

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

        if (head.Data == data)
        {
            head = head.Next;
            return;
        }

        Node current = head;
        while (current.Next != null)
        {
            if (current.Next.Data == data)
            {
                current.Next = current.Next.Next;
                return;
            }
            current = current.Next;
        }
    }

    // 모든 노드를 출력
    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()
    {
        SinglyLinkedList list = new SinglyLinkedList();

        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. 단일 연결 리스트의 장점과 단점

장점

• 동적 크기 조절: 배열과 달리 리스트의 크기를 동적으로 조절할 수 있습니다.
• 삽입 및 삭제의 효율성: 특정 위치에서의 삽입 및 삭제가 용이하며, 특히 리스트의 앞쪽에서 삽입/삭제 시 효율적입니다.

단점

• 탐색 시간: 특정 요소를 찾으려면 순차적으로 검색해야 하므로 평균 탐색 시간은 O(n)입니다.
• 메모리 오버헤드: 각 노드가 다음 노드의 주소를 저장해야 하므로 추가적인 메모리 공간이 필요합니다.

---

단일 연결 리스트는 노드가 연결된 간단하고 유연한 데이터 구조로, 삽입과 삭제가 빈번히 발생하는 상황에 유용하게 사용됩니다. 배열과 달리 리스트의 크기를 동적으로 조절할 수 있어 효율적인 메모리 사용이 가능하지만, 순차 접근을 해야 하므로 탐색이 비교적 느린 단점이 있습니다. 단일 연결 리스트의 개념을 이해하고 C#으로 구현해보면, 다양한 상황에서 리스트를 효과적으로 활용할 수 있을 것입니다.