[자료구조] 연결리스트(LinkedList) 정리

연결리스트(LinkedList)

연결 리스트는 데이터를 노드(Node)라는 단위 객체에 저장하고, 각 노드가 다음 노드를 가리키는 참조(Reference)를 통해 선형적인 순서를 구성하는 자료구조다.

배열(Array)이 메모리상에 연속된 공간에 데이터를 저장하는 밀집 리스트(Dense List)인 것과 달리, 연결 리스트는 메모리상에 흩어져 있는 데이터를 포인터를 통해 논리적으로 연결하는 연결 리스트(Linked List)다.

각 노드는 다음과 같은 두 가지 핵심 요소로 구성된다.

• 데이터(Data): 노드가 실질적으로 저장하는 값.

• 참조(Reference) / 포인터(Pointer): 다음 노드의 메모리 주소를 가리키는 값. C#에서는 이를 '참조'라 칭한다. 마지막 노드의 참조는 null을 가리킨다.

이러한 구조적 특성으로 인해 배열과 비교하여 명확한 장단점을 지닌다.

• 장점: 데이터의 삽입 및 삭제가 효율적이다. 특정 위치에 데이터를 추가하거나 제거할 때, 해당 위치의 이전 노드와 다음 노드의 참조만 변경하면 되므로 O(1)의 시간 복잡도를 가진다. 배열처럼 데이터를 한 칸씩 밀거나 당기는 작업이 불필요하다.

• 단점: 특정 데이터에 대한 접근(Access) 및 탐색(Search) 속도가 느리다. 배열은 인덱스를 통해 O(1) 시간 복잡도로 데이터에 즉시 접근할 수 있으나, 연결 리스트는 원하는 데이터를 찾기 위해 반드시 첫 번째 노드(Head)부터 순차적으로 탐색해야 하므로 최악의 경우 O(n)의 시간 복잡도를 가진다.

---

구현방법

Node 클래스 정의
먼저, 연결 리스트의 기본 단위인 노드를 클래스로 정의한다. 제네릭 를 사용하여 모든 데이터 타입을 수용할 수 있도록 설계한다.

  /// <summary>
/// 연결 리스트의 개별 노드를 표현하는 클래스.
/// </summary>
/// <typeparam name="T">노드가 저장할 데이터의 타입</typeparam>
public class Node<T>
{
    // 실제 데이터
    public T Data { get; set; }
    // 다음 노드를 가리키는 참조
    public Node<T> Next { get; set; }

    public Node(T data)
    {
        this.Data = data;
        this.Next = null; // 생성 시점에는 다음 노드가 없으므로 null로 초기화
    }
}

MyLinkedList 클래스 정의
정의한 Node를 관리하고, 연결 리스트의 핵심 기능을 제공하는 MyLinkedList 클래스를 구현한다.

/// <summary>
/// 단일 연결 리스트를 구현한 클래스.
/// </summary>
public class MyLinkedList<T>
{
    private Node<T> head; // 리스트의 시작을 가리키는 노드
    private int count;    // 리스트에 포함된 노드의 개수

    public int Count => count;
    public bool IsEmpty => count == 0;

    public MyLinkedList()
    {
        this.head = null;
        this.count = 0;
    }
    
    // ... (이하 핵심 기능 메서드 구현)
}

핵심 기능 메서드 구현

• 데이터 추가 (Add)
  AddFirst(T data): 리스트 맨 앞에 데이터 추가
  가장 간단하고 빠른 추가 방식이다. 새로운 노드를 생성하고, 새 노드의 Next가 기존의 head를 가리키게 한 후, head를 새 노드로 교체하면 된다. 시간 복잡도는 O(1)이다.

public void AddFirst(T data)
{
    Node<T> newNode = new Node<T>(data);
    newNode.Next = this.head; // 새 노드가 기존 head를 가리킴
    this.head = newNode;      // head를 새 노드로 업데이트
    count++;
}

• AddLast(T data): 리스트 맨 뒤에 데이터 추가
  head부터 시작하여 Next가 null인 마지막 노드를 찾은 후, 그 노드의 Next를 새 노드로 연결해야 한다. 시간 복잡도는 O(n)이다.

  public void AddLast(T data)
{
    Node<T> newNode = new Node<T>(data);
    if (this.head == null)
    {
        this.head = newNode;
    }
    else
    {
        Node<T> current = this.head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
    }
    count++;
}

• 데이터 삭제 (Remove)
  RemoveFirst(): 맨 앞 노드 삭제
  head를 현재 head의 Next 노드로 변경하기만 하면 된다. 시간 복잡도는 O(1)이다.

  public void RemoveFirst()
{
    if (IsEmpty)
        throw new InvalidOperationException("List is empty.");

    this.head = this.head.Next;
    count--;
}

• 데이터 탐색 (Find)
  Find(T data): 특정 데이터 값을 가진 노드 탐색
  head부터 시작하여 순차적으로 각 노드의 Data를 비교한다. 시간 복잡도는 O(n)이다.

  public Node<T> Find(T data)
{
    Node<T> current = this.head;
    while (current != null)
    {
        if (EqualityComparer<T>.Default.Equals(current.Data, data))
        {
            return current;
        }
        current = current.Next;
    }
    return null;
}

C# 내장 LinkedList 클래스 활용
닷넷 프레임워크는 System.Collections.Generic 네임스페이스에 LinkedList라는 강력한 이중 연결 리스트(Doubly Linked List) 클래스를 기본으로 제공한다.

이중 연결 리스트는 각 노드가 다음 노드(Next)뿐만 아니라 이전 노드(Previous)에 대한 참조도 함께 가지는 구조다. 이로 인해 양방향 탐색이 가능하며, 특정 노드 앞뒤에 데이터를 추가하거나 삭제하는 작업이 더 효율적이다.

주요 속성 및 메서드

• First: 리스트의 첫 번째 노드(LinkedListNode)를 반환한다.
• Last: 리스트의 마지막 노드를 반환한다.
• Count: 리스트의 노드 개수를 반환한다.
• AddFirst(T value): 리스트 맨 앞에 새 노드를 추가한다. (O(1))
• AddLast(T value): 리스트 맨 뒤에 새 노드를 추가한다. (O(1)) - Last 프로퍼티 덕분에 O(1)이 가능하다.
• AddBefore(LinkedListNode node, T value): 지정된 노드 node 앞에 새 노드를 추가한다. (O(1))
• AddAfter(LinkedListNode node, T value): 지정된 노드 node 뒤에 새 노드를 추가한다. (O(1))
• Remove(T value): 특정 값을 가진 첫 번째 노드를 제거한다. (O(n))
• Remove(LinkedListNode node): 지정된 노드를 제거한다. (O(1))
• RemoveFirst(): 첫 번째 노드를 제거한다. (O(1))
• RemoveLast(): 마지막 노드를 제거한다. (O(1))
• Find(T value): 특정 값을 가진 첫 번째 노드를 찾아 반환한다. (O(n))

예시

  // LinkedList<string> 인스턴스 생성
var names = new LinkedList<string>();

// 데이터 추가
names.AddLast("Alpha");
names.AddLast("Bravo");
names.AddLast("Charlie");
names.AddFirst("Start"); // ["Start", "Alpha", "Bravo", "Charlie"]

// 특정 노드 찾기 및 그 뒤에 데이터 추가
LinkedListNode<string> bravoNode = names.Find("Bravo");
if (bravoNode != null)
{
    names.AddAfter(bravoNode, "Beta"); // ["Start", "Alpha", "Bravo", "Beta", "Charlie"]
}

// 데이터 삭제
names.Remove("Start"); // ["Alpha", "Bravo", "Beta", "Charlie"]
names.RemoveLast();    // ["Alpha", "Bravo", "Beta"]

// 리스트 순회
Console.WriteLine("현재 리스트 요소:");
foreach (string name in names)
{
    Console.WriteLine(name);
}
// 출력:
// Alpha
// Bravo
// Beta

---

마무리

연결 리스트는 데이터의 삽입과 삭제가 빈번하게 발생하는 시나리오에서 성능을 발휘하는 자료구조다. 반면, 데이터에 대한 임의 접근(Random Access)이 중요하다면 배열 기반의 List가 훨씬 유리하다.

이 두 자료구조의 내부 동작 원리와 성능 특성을 명확히 이해하고, 당면한 문제의 요구사항에 가장 적합한 것을 선택하여 사용하는 것이 중요하다. 대부분의 일반적인 시나리오에서는 List가 더 나은 선택일 수 있지만, 큐(Queue), 스택(Stack)과 같은 다른 자료구조를 구현하거나, 대규모 데이터셋에서 삽입/삭제가 매우 잦은 특정 알고리즘 문제에서는 LinkedList가 좋은 선택이 될 수 있다.