자료구조 시리즈 6편

연결 리스트(Linked List) 완전 이해하기

이전 글에서는 큐(Queue)에 대해 알아봤습니다.
이번에는 노드(Node)들이 포인터로 연결된 구조인 연결 리스트(Linked List) 를 자세히 정리해봅니다.

 

1. 연결 리스트란?

연결 리스트는 각 노드가 데이터와 다음 노드에 대한 포인터를 함께 저장하는 자료구조입니다.

• 동적 크기 조정 가능
• 삽입과 삭제가 빠름 (특히 중간 삽입/삭제)
• 메모리에 연속적으로 저장될 필요가 없음

---

2. 연결 리스트의 특징

항목 설명

삽입/삭제	빠름 (O(1) - 위치만 알면)
접근	느림 (O(n) - 처음부터 순회 필요)
메모리 사용	포인터 공간 추가 필요
크기 조정	동적 크기 조정 가능

---

3. 연결 리스트 종류

종류 설명

단일 연결 리스트(Singly Linked List)	한 방향(다음 노드만)으로 연결
이중 연결 리스트(Doubly Linked List)	앞뒤로 양방향 연결
원형 연결 리스트(Circular Linked List)	마지막 노드가 첫 번째 노드를 가리킴

---

4. 단일 연결 리스트 사용 예시 (C# 기준)

C# 내장 LinkedList<T> 클래스를 사용할 수 있습니다.

 선언과 초기화

using System.Collections.Generic;

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

 요소 추가

list.AddLast("노드1");
list.AddLast("노드2");
list.AddFirst("노드0");

 요소 순회

foreach (var item in list)
{
    Console.WriteLine(item);
}

 특정 노드 뒤에 삽입

LinkedListNode<string> node = list.Find("노드1");
list.AddAfter(node, "노드1.5");

 요소 삭제

list.Remove("노드2");

---

5. 실생활 예시로 이해하기

• 연결 리스트 = 지하철 칸
  • 각 칸(노드)이 다음 칸을 이어서 연결됨
  • 중간 칸 추가/제거가 쉽고 빠름

---

6. 연결 리스트의 활용 사례

사용 예시 설명

메모리 효율적 관리	필요할 때마다 노드를 동적 생성
Undo/Redo 구현	이전 작업으로 이동할 때 양방향 연결 리스트 사용
캐시 구현(LRU 캐시)	최근 사용 데이터를 빠르게 관리

---

이번 글에서는 연결 리스트(Linked List) 의 개념, 종류, C# 코드 사용법을 정리했습니다.

• 배열과 다르게 메모리에 연속 저장되지 않음
• 중간 삽입/삭제가 매우 빠름
• 단일, 이중, 원형 연결 리스트 등 다양한 변형이 존재