연결 리스트

🎯 학습 목표

이 강을 마치면 연결 리스트의 구조를 설명하고, 노드 클래스로 직접 구현할 수 있습니다. 그리고 배열과 정반대인 성질 — 중간 삽입·삭제는 O(1)인데 인덱스 접근은 O(n) — 을 근거로 언제 어느 것을 쓸지 판단할 수 있게 됩니다.

파이썬에서 연결 리스트를 직접 쓸 일은 드뭅니다. 그럼에도 배우는 이유는 19강 트리와 22강 그래프가 같은 노드-포인터 구조이기 때문입니다. 여기서 "참조로 연결한다"는 감각을 잡아야 합니다.

💡 노드와 연결

연결 리스트는 데이터와 다음 노드의 위치를 함께 가진 노드들이 사슬처럼 이어진 구조입니다. 배열과 달리 메모리에 연속으로 붙어 있을 필요가 없습니다.

배열 vs 연결 리스트

  [배열]  메모리에 연속
    ┌────┬────┬────┬────┐
    │ 10 │ 20 │ 30 │ 40 │
    └────┴────┴────┴────┘
    주소 계산으로 바로 접근 → O(1)
    중간 삽입은 밀어야 함    → O(n)

  [연결 리스트]  흩어져 있고 참조로 연결
    head
     │
     ▼
    ┌────┬───┐   ┌────┬───┐   ┌────┬───┐
    │ 10 │ ●─┼──▶│ 20 │ ●─┼──▶│ 30 │ / │
    └────┴───┘   └────┴───┘   └────┴───┘
                                      ↑ None (끝)

    3번째를 보려면 head 부터 따라가야 함 → O(n)
    중간 삽입은 참조만 바꾸면 됨          → O(1)

  중간 삽입의 원리

   10 ──▶ 20 ──▶ 30      10과 20 사이에 15를 넣으려면

   ① 새 노드 15를 만들고, 15의 next 를 20으로
   ② 10의 next 를 15로

   10 ──▶ 15 ──▶ 20 ──▶ 30

   ▲ 다른 노드는 전혀 건드리지 않았다 → O(1)
     단, '10의 위치를 이미 알고 있을 때'만 O(1)이다.
     찾아가는 데 O(n)이 든다면 전체는 O(n)이다.  ★

  삭제도 같다
   10 ──▶ 15 ──▶ 20   에서 15를 지우려면
   10의 next 를 20으로 바꾸면 끝이다.

마지막 별표가 중요합니다. "삽입·삭제가 O(1)"이라는 말은 위치를 이미 알고 있다는 전제입니다. 위치를 찾아야 한다면 탐색에 O(n)이 들어 결국 O(n)입니다.

📖 배열과 연결 리스트, 언제 무엇을

연산	배열(파이썬 리스트)	연결 리스트
i번째 접근	O(1)	O(n)
맨 앞 삽입·삭제	O(n)	O(1)
중간 삽입·삭제(위치를 알 때)	O(n)	O(1)
맨 뒤 삽입	상각 O(1)	O(n) 또는 O(1)*
탐색	O(n)	O(n)
메모리	값만	값 + 참조(오버헤드)
캐시 효율	좋음(연속)	나쁨(흩어짐)

* 꼬리(tail) 참조를 따로 관리하면 맨 뒤 삽입도 O(1)입니다.

실무에서 파이썬 리스트가 대부분의 경우 더 낫습니다. 연결 리스트는 참조 저장에 메모리를 더 쓰고, 메모리에 흩어져 있어 실제 접근 속도도 느린 경우가 많습니다. 앞쪽 작업이 잦다면 deque(6강)가 더 실용적인 선택입니다.

그럼에도 알아야 하는 이유는 변형 구조들 때문입니다.

• 이중 연결 리스트 — 앞뒤 양쪽 참조를 가집니다. deque나 LRU 캐시 구현의 기반입니다.
• 원형 연결 리스트 — 마지막이 처음을 가리킵니다. 순환 처리에 씁니다.
• 트리·그래프 — 참조로 연결한다는 아이디어가 그대로 확장됩니다(19·22강).

💻 실전 예제 — 구현과 대표 문제

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None          # 다음 노드에 대한 참조


def build(values):
    """리스트를 연결 리스트로 만든다 → head 반환"""
    head = None
    for v in reversed(values):    # 뒤에서부터 앞에 붙인다
        node = Node(v)
        node.next = head
        head = node
    return head


def to_list(head):
    """연결 리스트를 파이썬 리스트로 → O(n)"""
    result = []
    current = head
    while current:                # None 이면 끝
        result.append(current.value)
        current = current.next
    return result


def reverse(head):
    """연결 리스트 뒤집기 → O(n), 추가 메모리 O(1)"""
    prev = None
    current = head
    while current:
        nxt = current.next        # 다음을 미리 저장  ★
        current.next = prev       # 방향을 뒤집는다
        prev = current            # 한 칸 전진
        current = nxt
    return prev                   # 새 head


def has_cycle(head):
    """순환이 있는지 판별 → 토끼와 거북이, 공간 O(1)"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # 한 칸씩
        fast = fast.next.next     # 두 칸씩
        if slow is fast:          # 만나면 순환
            return True
    return False


head = build([10, 20, 30, 40])
print(to_list(head))              # [10, 20, 30, 40]
print(to_list(reverse(head)))     # [40, 30, 20, 10]

cyc = build([1, 2, 3])
cyc.next.next.next = cyc          # 마지막이 처음을 가리키게
print(has_cycle(cyc))             # True

코드를 줄 단위로 보겠습니다.

• self.next = None — 다음이 없음을 뜻합니다. 연결 리스트의 끝을 None으로 표시하는 것이 관례입니다.
• for v in reversed(values) — 뒤에서부터 만들면 매번 맨 앞에 붙이면 되어 O(1)입니다. 앞에서부터 만들려면 꼬리를 따로 관리해야 합니다.
• while current: — None은 거짓이므로 이 한 줄로 끝까지 순회합니다.
• nxt = current.next — 뒤집기의 핵심입니다. current.next를 바꾸기 전에 다음 노드를 저장해 두지 않으면 나머지 사슬을 잃어버립니다.
• prev = current; current = nxt — 두 포인터를 한 칸씩 전진시킵니다. 반복이 끝나면 current는 None이고 prev가 새 head입니다.
• slow = fast = head — 토끼와 거북이 알고리즘입니다. 순환이 있으면 빠른 포인터가 반드시 느린 포인터를 따라잡습니다.
• while fast and fast.next — 두 조건 모두 필요합니다. fast.next.next를 하려면 fast.next가 존재해야 합니다. 순서를 바꾸면 오류가 납니다.
• if slow is fast — is는 같은 객체인지 확인합니다. ==는 값 비교라 다른 노드인데 값이 같으면 잘못 판정할 수 있습니다.

has_cycle은 공간 O(1)로 순환을 찾습니다. 방문한 노드를 집합에 담는 방법도 있지만 공간 O(n)이 듭니다. 두 포인터의 속도 차이만으로 해결하는 것이 이 알고리즘의 묘미입니다.

⚠️ 자주 하는 실수

첫째, 뒤집기에서 다음 노드를 잃어버립니다. current.next = prev를 먼저 하면 나머지 사슬로 가는 길이 끊깁니다. 반드시 nxt에 저장한 뒤 바꾸세요.

둘째, None 확인을 빠뜨립니다. current.next.value처럼 두 단계를 건너뛸 때 중간이 None이면 오류입니다. 확인 순서를 지키세요.

셋째, head가 바뀌는 것을 놓칩니다. 맨 앞을 삽입·삭제하면 head 자체가 달라집니다. 함수에서 새 head를 반환하거나, 더미 노드를 앞에 두어 head 변경을 없애는 기법을 씁니다.

넷째, is와 ==를 혼동합니다. 노드를 비교할 때는 같은 객체인지가 중요하므로 is를 씁니다.

다섯째, 실전에서 굳이 직접 구현합니다. 코딩 테스트에서 "연결 리스트를 만들라"는 문제가 아니면 파이썬 리스트나 deque가 거의 항상 낫습니다. 개념 이해와 실전 선택은 별개입니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	노드 = 값 + 다음 노드 참조
2	배열과 정반대 — 접근 O(n), 삽입 O(1)
3	삽입 O(1)은 위치를 알 때만
4	뒤집기는 다음을 먼저 저장
5	순환 판별은 토끼와 거북이 (공간 O(1))
6	노드 비교는 is
7	실전에서는 리스트·deque가 대개 낫다

지금 해 볼 것은 reverse에서 nxt = current.next 줄을 지우고 실행해 보는 것입니다. 사슬이 끊겨 결과가 한 개짜리로 나오는 것을 보면 왜 미리 저장해야 하는지 확실해집니다.

다음 19강 「트리 기초」에서는 노드가 여러 개의 자식을 가지는 구조로 넓힙니다. 용어(루트·리프·깊이·높이)를 정리하고, 전위·중위·후위 순회를 재귀로 구현하겠습니다.

📚 참고 자료

• Classes — Python 공식 문서
• collections.deque — Python 공식 문서
• Identity comparisons (is) — Python 공식 문서