C# - 연결 리스트(Linked List)

 

연결리스트 알아보기

연결리스트 ( Linked List )

정의

연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 포함하는 데이터 구조입니다. 노드(Node)는 연결 리스트의 기본 단위로, 리스트의 요소를 표현합니다. C#에서는 LinkedList<T> 클래스를 제공하여 연결 리스트를 쉽게 사용할 수 있습니다.

개요

연결 리스트는 배열과 달리 요소가 연속된 메모리 위치에 저장되지 않고, 각 요소가 포인터로 연결되어 있습니다. 이 때문에 연결 리스트는 요소의 삽입과 삭제가 배열보다 효율적일 수 있습니다. 연결 리스트에는 다음과 같은 유형이 있습니다:

• 단순 연결 리스트(Singly Linked List): 각 노드가 다음 노드에 대한 포인터만 가짐.
• 이중 연결 리스트(Doubly Linked List): 각 노드가 다음 노드와 이전 노드에 대한 포인터를 가짐.
• 원형 연결 리스트(Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 포인터를 가짐.

C#의 LinkedList<T>는 이중 연결 리스트입니다.

사용법

C#의 LinkedList<T> 클래스를 사용하여 연결 리스트를 생성, 추가, 삭제, 탐색하는 방법을 알아보겠습니다.

LinkedList<int> list = new LinkedList<int>();


list.AddLast(1); // 리스트의 끝에 노드 추가
list.AddFirst(0); // 리스트의 처음에 노드 추가
list.AddLast(2);


list.Remove(1); // 값이 1인 첫 번째 노드 삭제
list.RemoveFirst(); // 첫 번째 노드 삭제
list.RemoveLast(); // 마지막 노드 삭제


foreach (int value in list)
{
    Console.WriteLine(value);
}

Liked List 장점 및 단점

장점

• 동적 크기 조절 : 배열과 달리 연결 리스트는 크기가 동적으로 조절되어 메모리 낭비가 적습니다.
• 삽입 및 삭제의 효율성 : 리스트 중간에 요소를 삽입하거나 삭제하는 작업이 빠릅니다.
• 메모리 할당의 유연성 : 요소들이 메모리의 연속된 공간에 저장되지 않으므로, 메모리 할당이 유연합니다.

단점

• 추가 메모리 사용 : 각 노드는 데이터 외에도 포인터를 저장하기 위한 추가 메모리가 필요합니다.
• 비효율적인 접근 시간 : 특정 인덱스의 요소에 접근하려면 처음부터 순차적으로 탐색해야 하므로, 접근 시간이 O(n)입니다.
• 캐시 비효율성 : 요소들이 연속된 메모리에 저장되지 않으므로, 캐시 효율성이 떨어질 수 있습니다.

 

예제

아래는 C#의 LinkedList<T>를 사용하여 연결 리스트를 구현하고, 다양한 작업을 수행하는 예제입니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        // LinkedList 생성
        LinkedList<int> list = new LinkedList<int>();

        // 노드 추가
        list.AddLast(1);
        list.AddLast(2);
        list.AddLast(3);
        list.AddFirst(0);

        // 리스트 출력
        Console.WriteLine("초기 리스트:");
        PrintList(list);

        // 특정 노드 뒤에 삽입
        LinkedListNode<int> node = list.Find(2);
        list.AddAfter(node, 2);

        // 리스트 출력
        Console.WriteLine("\n노드 2 뒤에 2 추가 후 리스트:");
        PrintList(list);

        // 노드 삭제
        list.Remove(2); // 값이 2인 첫 번째 노드 삭제

        // 리스트 출력
        Console.WriteLine("\n값이 2인 첫 번째 노드 삭제 후 리스트:");
        PrintList(list);

        // 노드 검색
        bool containsThree = list.Contains(3);
        Console.WriteLine($"\n리스트에 3이 포함되어 있는가? {containsThree}");

        // 리스트 비우기
        list.Clear();
        Console.WriteLine("\n리스트 비운 후:");
        PrintList(list);
    }

    static void PrintList(LinkedList<int> list)
    {
        foreach (int value in list)
        {
            Console.Write(value + " -> ");
        }
        Console.WriteLine("null");
    }
}

위 예제에서는 LinkedList<T> 클래스의 다양한 메서드를 사용하여 노드를 추가, 삭제, 탐색하는 방법을 보여줍니다. PrintList 메서드는 리스트의 모든 요소를 출력합니다.

요약

C#의 LinkedList<T> 클래스는 연결 리스트를 쉽게 구현할 수 있게 해줍니다. 연결 리스트는 동적 크기 조절, 삽입 및 삭제의 효율성 등의 장점이 있지만, 추가 메모리 사용, 비효율적인 접근 시간 등의 단점도 있습니다. 연결 리스트를 사용할 때 이러한 장단점을 고려하여 적절한 데이터 구조를 선택하는 것이 중요합니다.