[C#][자료구조] LinkedList<T>

✅ LinkedList<T>

📌 LinkedList란?

LinkedList<T>는 노드(Node)들이 포인터(참조)로 연결된 자료구조입니다. 각 노드는 값(Data)과 다음/이전 노드에 대한 참조를 가지며, 양방향 연결 리스트(Doubly Linked List)로 구현되어 있습니다.

배열(Array)이나 List와 달리, 삽입/삭제가 O(1)로 빠른 장점이 있지만, 인덱스로 직접 접근할 수 없어 탐색은 O(N)입니다.

📌 LinkedList는 언제 사용될까?

• 삽입/삭제가 빈번하게 발생하는 경우
• 데이터 크기를 예측하기 어려운 경우
• 큐/스택 같은 자료구조를 구현할 때
• 중간 위치에 효율적으로 요소를 추가/제거해야 할 때

📊 기본 연산과 시간 복잡도

연산	설명	시간 복잡도
AddFirst	맨 앞에 노드 추가	O(1)
AddLast	맨 뒤에 노드 추가	O(1)
Remove	특정 노드 제거	O(1)
Find	특정 값 가진 노드 탐색	O(N)
Count	노드 개수 확인	O(1)

✅ C#에서의 LinkedList

📌 기본 사용법

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var linkedList = new LinkedList();

        // 추가
        linkedList.AddLast("Apple");
        linkedList.AddLast("Banana");
        linkedList.AddFirst("Orange"); // 맨 앞에 삽입

        foreach (var item in linkedList)
            Console.WriteLine(item); // Orange, Apple, Banana

        // 특정 노드 찾기
        var node = linkedList.Find("Apple");
        linkedList.AddAfter(node, "Cherry"); // Apple 뒤에 삽입

        // 삭제
        linkedList.Remove("Banana");

        Console.WriteLine(string.Join(", ", linkedList)); // Orange, Apple, Cherry
    }
}

📌 LinkedList vs List 비교

구분	List<T>	LinkedList<T>
내부 구조	동적 배열	노드 + 포인터
인덱스로 접근	O(1)	O(N)
중간 삽입/삭제	O(N)	O(1) (노드 참조 시)
캐시 효율	좋음	낮음 (포인터 분산)
권장 상황	조회가 많을 때	삽입/삭제가 많을 때

📝 정리

• LinkedList<T>는 노드 기반의 양방향 연결 리스트
• 삽입/삭제가 빠르지만, 탐색은 느리다
• 순차적 접근 위주라면 List<T>, 삽입/삭제가 많다면 LinkedList<T> 권장
• 내부적으로 포인터를 관리하기 때문에 메모리 오버헤드가 있음