Linked List(연결 리스트)

개요

연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 함께 저장하여 데이터를 선형으로 연결한 자료구조이다. 배열과 달리 메모리 상에서 연속적이지 않아도 되며, 삽입/삭제 연산이 유연하다는 장점이 있다. 리스트의 형태에 따라 단일(Singly), 이중(Doubly), 원형(Circular) 등으로 구분되며, 알고리즘과 시스템 구현에서 핵심적으로 활용된다.

---

1. 개념 및 정의

구성 요소	설명
Node	데이터(data) + 포인터(next)로 구성된 기본 단위
Head	연결 리스트의 시작 노드를 가리키는 포인터
Tail	마지막 노드를 의미하며, next는 None 또는 Head를 가리킴

노드는 동적으로 생성되며, 메모리를 필요할 때마다 할당한다.

---

2. 배열과의 차이점 비교

항목	배열(Array)	연결 리스트(Linked List)
메모리 배치	연속적	비연속적 (포인터 기반)
접근 속도	O(1) (인덱스 접근)	O(n) (순차 접근)
삽입/삭제	O(n)	O(1) (노드 위치 알고 있을 경우)
크기 변경	불가능 또는 새 배열 할당	동적 확장 가능

---

3. 연결 리스트의 종류

종류	설명	특징
단일 연결 리스트 (Singly Linked List)	한 방향(next)으로만 연결	가장 기본 형태
이중 연결 리스트 (Doubly Linked List)	양방향(prev, next) 포인터 존재	양쪽 탐색 가능, 메모리 사용 ↑
원형 연결 리스트 (Circular Linked List)	마지막 노드가 첫 노드를 가리킴	반복 순회 구조 가능

---

4. 파이썬 구현 예시 (단일 연결 리스트)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def print_list(self):
        curr = self.head
        while curr:
            print(curr.data, end=' → ')
            curr = curr.next
        print('None')

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.print_list()  # 출력: 10 → 20 → 30 → None

---

5. 시간 복잡도 분석

연산	시간 복잡도
접근 (임의 인덱스)	O(n)
탐색 (Search)	O(n)
삽입 (Head 또는 위치 제공 시)	O(1)
삭제 (노드 참조 제공 시)	O(1)

헤드에 대한 연산은 빠르지만, 인덱스를 기준으로 한 접근은 느리다.

---

6. 장단점 정리

구분	장점	단점
메모리	크기 유동적, 단편화된 메모리 사용 가능	포인터 저장으로 메모리 추가 사용
성능	삽입/삭제 빠름 (헤드 기준)	탐색/접근 속도 느림
구조 확장	구현이 유연 (스택, 큐로 확장 용이)	구현 복잡도 ↑

---

7. 활용 사례

분야	활용 예시
데이터 구조 구현	스택, 큐, 해시 체이닝, 그래프 인접 리스트
메모리 관리	가비지 컬렉션, 동적 메모리 할당
운영체제	프로세스 스케줄링, 할당 테이블
알고리즘 문제풀이	노드 기반 경로 구현, LRU 캐시, 트리 구조 확장

---

8. 결론

연결 리스트는 삽입과 삭제가 잦고, 데이터 크기가 유동적인 문제에서 매우 유용한 자료구조다. 인덱스 기반 접근은 느리지만, 포인터를 통한 동적 구조 확장이 가능하다는 점에서 다양한 알고리즘과 시스템 구조의 기반이 된다. 단일, 이중, 원형 등 구조에 따라 다양하게 확장 가능하며, 자료구조 학습의 기본 중 하나로 반드시 이해해야 할 개념이다.