B-2: 연결 리스트 — "노드와 포인터로 데이터를 직접 잇는다"

안녕하세요! 코딩테스트와 CS의 길잡이, 홍순구 튜터입니다.

지난 시간엔 스택·큐·덱 세 그릇을 손에 쥐었습니다. 그러면서 두 가지를 흘려 뒀죠. 하나는 파이썬 리스트로 큐를 짜면 pop(0)이 뒤 원소를 전부 한 칸씩 당겨 O(n)이라 함정이라는 것, 또 하나는 그래서 실전 큐로 쓰는 deque의 속이 사실 "원소를 작은 블록으로 이어 붙인 구조"에 가깝다는 것이었습니다.

오늘은 그 "이어 붙인다"를 끝까지 밀고 갑니다. 원소 하나하나를 노드(node)라는 칸에 담고, 칸끼리 포인터(pointer, 다음 칸의 주소)로 손을 잡게 이으면 연결 리스트(linked list)가 됩니다. 배열이 원소를 메모리에 빽빽이 붙여 두는 그릇이라면, 연결 리스트는 원소를 여기저기 흩어 두고 화살표로 잇는 그릇이에요.

왜 굳이 흩어 두고 화살표로 이을까요? 지난 시간에 본 리스트의 약점, "맨 앞이나 가운데에 끼우고 빼는 게 O(n)"을 풀기 위해서입니다. 연결 리스트는 바로 이 동작을 O(1)에 해냅니다. 대신 다른 걸 잃죠. 무엇을 얻고 무엇을 잃는지, 그 트레이드오프를 오늘 빅오로 똑똑히 따져 봅니다.

 오늘의 여정 — "노드와 포인터로 데이터를 직접 잇는다"

 [1] 노드와 포인터    →  배열의 약점에서 출발, 칸 하나 + 다음 칸 주소
 [2] 단일 연결 리스트  →  head에서 next로 한 칸씩, 순회는 O(n)
 [3] 삽입·삭제 O(1)   →  포인터만 고친다, 배열 vs 연결 리스트 빅오 대조
 [4] 더미 헤드        →  맨 앞 예외를 없애는 가짜 칸 하나
 [5] 이중 연결 리스트  →  앞뒤 두 방향, deque의 속 정체
 [6] 뒤집기           →  화살표 방향을 거꾸로 (코테 단골)
 [7] 사이클 검출       →  토끼와 거북이, 두 포인터로 고리를 잡는다

자, 데이터를 직접 손으로 잇는 그릇을 만들러 가 봅시다. 출발합니다!

💡 오늘 수업의 핵심 — "노드와 포인터로 연결 리스트를 직접 이어 보고, 삽입·삭제가 왜 O(1)인지(대신 인덱싱은 왜 O(n)인지)를 배열과 빅오로 대조하며, 더미 헤드·뒤집기·사이클 검출 같은 빈출 패턴을 익힌다"

🎯 학습 목표

• 노드(값 + 다음 노드 포인터)로 단일/이중 연결 리스트를 직접 구현하고, 순회·삽입·삭제 같은 핵심 연산의 시간·공간 복잡도를 빅오로 짚습니다.
• "노드를 찾는 비용(O(n))"과 "찾은 뒤 끼우는 비용(O(1))"을 갈라 보며, 배열 vs 연결 리스트 트레이드오프를 빅오 표로 비교합니다.
• 더미 헤드로 경계 예외를 없애고, 리스트 뒤집기·사이클 검출(빠른/느린 두 포인터) 같은 코테 빈출 패턴을 구현합니다.

Step 1: "배열의 약점에서 출발한다" — 노드와 포인터

지난 시간에 본 파이썬 리스트(배열)의 약점부터 다시 떠올려 봅시다. 리스트는 원소를 메모리에 한 줄로 빽빽이 붙여 둡니다. 덕분에 "3번째 원소 줘"라고 하면 시작 주소에서 세 칸 점프해 곧장 꺼냅니다. 이게 인덱싱 O(1)이에요.

그런데 맨 앞에 새 원소를 끼우려면? 뒤 원소를 전부 한 칸씩 밀어야 합니다. 가운데도 마찬가지죠. 원소가 10만 개면 10만 번을 미는 O(n)입니다. 빽빽이 붙여 둔 대가예요.

연결 리스트는 발상을 뒤집습니다. 원소를 붙여 두지 않고 메모리 여기저기 흩어 둔 뒤, 각 원소가 "내 다음은 저기야"라고 다음 칸의 주소를 들고 있게 합니다. 이 "값 하나 + 다음 칸 주소"를 담은 칸을 노드(node), 다음 칸을 가리키는 주소를 포인터(pointer)라고 불러요.

 배열(파이썬 리스트) — 메모리에 빽빽이 붙어 있다
   [ 1 ][ 2 ][ 3 ][ 4 ]      ← 3번째? 시작에서 세 칸 점프 = O(1)
                              ← 맨 앞 끼우기? 전부 밀기 = O(n)

 연결 리스트 — 흩어 두고 화살표로 잇는다
   head ─▶ [ 1 | ●─]─▶ [ 2 | ●─]─▶ [ 3 | / ]
            값  next     값  next     값  next(None=끝)

노드 하나를 코드로 옮기면 이렇게 단순합니다. 값(val) 하나와, 다음 노드를 가리키는 next 하나뿐이에요. 다음이 없으면(리스트의 끝이면) next는 None입니다.

# structures/linked_list.py

class Node:
    """단일 연결 리스트의 노드: 값 하나와 '다음 노드'를 가리키는 포인터 하나."""

    def __init__(self, val, next=None):
        self.val = val
        self.next = next        # 다음 노드(없으면 None) — 이게 '포인터'다

이 작은 노드가 오늘의 주인공입니다. 노드 하나는 자기 다음만 알 뿐, 전체를 모릅니다. "1번 노드는 2번을, 2번은 3번을 안다"처럼 각자 자기 다음만 손에 쥐고 줄줄이 이어진 게 연결 리스트예요. 그래서 맨 앞 노드(head)만 알면, 거기서 next를 따라 끝까지 갈 수 있습니다.

🎯 코테에서는 노드와 포인터가 연결 리스트뿐 아니라 트리·그래프의 바탕이 됩니다. 트리의 노드는 "자식 여럿을 가리키는 포인터"를 들고, 그래프의 노드는 "이웃들을 가리키는 포인터"를 듭니다. 오늘 잡는 "값 + 다음을 가리키는 포인터" 감각이 비선형 자료구조(C 카테고리)로 그대로 이어집니다.

💡 한 줄 정리

연결 리스트는 원소를 흩어 두고 노드(값 + 다음 포인터)로 잇는 그릇이다. head만 알면 next를 따라 끝까지 갈 수 있고, 배열의 "맨 앞·가운데 삽입 O(n)" 약점을 풀려는 데서 출발한다.

Step 2: "head에서 next로 한 칸씩" — 단일 연결 리스트를 직접 잇는다

노드 하나를 만들었으니, 이제 노드들을 이어 단일 연결 리스트(singly linked list)를 만들어 봅시다. "단일"은 화살표가 한 방향(다음 쪽)으로만 난다는 뜻이에요. 리스트 전체에서 우리가 꼭 들고 있어야 할 건 딱 하나, 맨 앞 노드를 가리키는 head입니다. 여기서부터 모든 게 시작돼요.

# structures/linked_list.py

class SinglyLinkedList:

    def __init__(self):
        self.head = None
        self._size = 0

    def push_front(self, val):
        """맨 앞에 새 노드를 끼운다. 새 노드의 next를 옛 head로 두면 끝. O(1)."""
        self.head = Node(val, self.head)
        self._size += 1

push_front를 먼저 보세요. 맨 앞에 끼우는 동작인데, 코드가 딱 한 줄입니다. 새 노드를 만들면서 그 next를 옛 head로 두고, head를 새 노드로 바꾸면 끝이에요. 뒤 원소를 미는 일이 전혀 없죠. 배열이라면 O(n)이었을 맨 앞 삽입이, 연결 리스트에선 포인터 둘만 고치는 O(1)입니다. 오늘의 첫 짜릿한 장면이에요.

 push_front(0) — 맨 앞에 0을 끼우기

 전:  head ─▶ [ 1 ]─▶ [ 2 ]─▶ [ 3 ]
 후:  head ─▶ [ 0 ]─▶ [ 1 ]─▶ [ 2 ]─▶ [ 3 ]
              새 노드의 next를 옛 head(1)로, head를 0으로 → 둘만 고침 (O(1))

반대로 맨 끝에 잇는 append는 사정이 다릅니다. 우리는 head만 들고 있지 꼬리가 어디인지 모르거든요. 그래서 끝 노드까지 next를 따라 걸어가야 합니다.

    def append(self, val):
        """맨 끝에 새 노드를 잇는다. 꼬리를 모르면 끝까지 따라가야 해 O(n)."""
        node = Node(val)
        if self.head is None:
            self.head = node
        else:
            curr = self.head
            while curr.next is not None:
                curr = curr.next
            curr.next = node
        self._size += 1

while curr.next is not None이 바로 끝까지 걸어가는 부분입니다. 원소가 n개면 n번 걸어야 끝에 닿으니 append는 O(n)이에요. (뒤에서 볼 이중 연결 리스트처럼 꼬리 포인터를 따로 들고 있으면 이 걸음을 생략해 O(1)로 만들 수 있습니다.)

전체를 눈으로 확인하는 to_list는, head부터 None을 만날 때까지 next를 따라가며 값을 모읍니다. 전부 훑으니 O(n)이에요.

    def to_list(self):
        """머리부터 끝까지 값들을 파이썬 리스트로 펼친다. 순회라 O(n)."""
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.val)
            curr = curr.next
        return result

append로 1, 2, 3을 잇고 push_front로 0을 앞에 끼운 뒤 펼치면 [0, 1, 2, 3]이 나옵니다. 이 "curr를 두고 curr = curr.next로 한 칸씩 전진하는" 순회 패턴은 오늘 내내 반복되니 눈에 익혀 두세요.

🎯 코테에서는 이 순회 패턴 자체가 연결 리스트 문제의 절반입니다. "리스트 길이 세기", "특정 값 찾기", "끝에서 K번째 노드"가 모두 이 while curr 걸음 위에서 풀립니다. LeetCode의 연결 리스트 문제(Easy~Medium)는 거의 다 이 한 칸씩 전진하는 손놀림에서 시작해요.

💡 한 줄 정리

단일 연결 리스트는 head 하나만 들고, next를 따라 한 칸씩 걷는다. 맨 앞 삽입(push_front)은 O(1)이지만, 꼬리를 모르는 append와 전체 순회(to_list)는 끝까지 걸어 O(n)이다.

Step 3: "포인터만 고친다" — 삽입과 삭제가 O(1)인 이유

이제 연결 리스트가 가장 빛나는 동작입니다. 이미 찾아 둔 노드의 바로 뒤에 끼우고 빼기예요. 값 2가 든 노드를 가리키는 node가 손에 있다고 합시다. 그 뒤에 99를 끼우려면, 새 노드의 next를 원래 2의 다음(3)으로 두고, 2의 next가 새 노드를 가리키게 하면 끝입니다.

# structures/linked_list.py

    def insert_after(self, node, val):
        """주어진 노드 '바로 뒤'에 새 값을 끼운다. 포인터 둘만 고쳐 O(1).

        새 노드의 next를 node.next로 두고, node.next가 새 노드를 가리키게 한다.
        (노드를 '찾는' 비용은 O(n)이지만, 찾은 뒤 '끼우는' 비용 자체는 O(1)이다.)
        """
        node.next = Node(val, node.next)
        self._size += 1

 insert_after(node=2, 99) — 2 뒤에 99 끼우기

 전:  ... ─▶ [ 2 | ●─]──────────────▶ [ 3 ]─▶ ...

 후:  ... ─▶ [ 2 | ●─]─▶ [ 99 | ●─]─▶ [ 3 ]─▶ ...
              99의 next를 3으로, 2의 next를 99로 → 포인터 둘만 (O(1))

뒤 원소를 미는 일이 없습니다. 리스트 어디든, 노드만 손에 있으면 끼우기는 O(1)이에요. 삭제도 같은 결입니다. delete_after는 주어진 노드의 다음 노드를 건너뛰게 이어, 사슬에서 떼어 냅니다.

    def delete_after(self, node):
        """주어진 노드 '다음 노드'를 떼어낸다. node.next를 건너뛰게 이어 O(1).

        다음 노드가 없으면 아무 일도 하지 않는다.
        """
        if node.next is not None:
            node.next = node.next.next
            self._size -= 1

node.next = node.next.next 한 줄이 핵심입니다. 2의 다음이 3이고 3의 다음이 4라면, 2의 next를 4로 바꿔 3을 건너뛰게 합니다. 그러면 3은 아무도 가리키지 않으니 사슬에서 사라져요. 역시 O(1)입니다.

여기서 반드시 갈라 봐야 할 게 있어요. "노드를 찾는 비용"과 "찾은 뒤 끼우는/빼는 비용"은 별개입니다. 값으로 노드를 찾는 find는 head부터 훑어야 하니 O(n)이에요.

    def find(self, val):
        """값이 같은 첫 노드를 찾아 돌려준다(없으면 None). 머리부터 훑어 O(n)."""
        curr = self.head
        while curr is not None:
            if curr.val == val:
                return curr
            curr = curr.next
        return None

그러니 "값 2 뒤에 99 끼우기"를 처음부터 끝까지 하면, 찾기 O(n) + 끼우기 O(1) = O(n)입니다. 하지만 이미 노드를 손에 쥐고 있는 상황(예: 순회하며 지나가는 중)이라면 끼우기·빼기 자체는 O(1)이에요. 이 구분이 배열과의 진짜 차이를 만듭니다. 자, 이제 약속한 빅오 대조표입니다.

표가 정확히 거울처럼 갈립니다. 배열은 인덱싱이 빠르고 삽입·삭제가 느리며, 연결 리스트는 정반대예요. "어느 게 더 좋다"가 아니라 "이 문제에서 무슨 연산이 자주 일어나나"로 고르는 겁니다.

🎯 코테에서는 사실 파이썬에서 연결 리스트를 직접 짜서 제출할 일은 드뭅니다(대부분 list·deque로 충분해요). 그런데도 이걸 배우는 이유는, "삽입·삭제 O(1) vs 인덱싱 O(1)"이라는 트레이드오프 감각이 자료구조를 고르는 모든 판단의 바탕이기 때문입니다. 면접에서 "배열과 연결 리스트의 차이는?"이라고 물으면 바로 이 표가 답이에요.

💡 한 줄 정리

노드를 손에 쥐고 있으면 삽입(insert_after)·삭제(delete_after)는 포인터만 고쳐 O(1)이다. 단 값으로 노드를 '찾는' find는 O(n) — "찾기"와 "끼우기"의 비용은 별개로 따진다.

Step 4: "맨 앞 예외를 없애는 가짜 칸 하나" — 더미 헤드

연결 리스트 코드를 짜다 보면 자꾸 발에 걸리는 게 있습니다. 맨 앞 노드(head)는 특별 취급을 해야 한다는 점이에요. 가운데 노드는 "앞 노드의 next를 고쳐서" 다루는데, head는 앞 노드가 없으니 self.head를 직접 바꿔야 하거든요.

예를 들어 "값이 target인 노드를 모두 지워라"를 짜 봅시다. 더미 헤드 없이 짜면, 맨 앞이 target인 경우를 위한 분기가 따로 필요합니다.

# structures/linked_list.py

def remove_all_naive(head, target):
    """값이 target인 노드를 모두 제거한다 — 더미 헤드 없이.

    맨 앞 노드가 target이면 head 자체를 옮겨야 해, '가운데를 지우는 로직'과 별개로
    앞쪽 while 분기가 따로 필요하다. head부터 끝까지 한 번 훑어 O(n).
    """
    # ① 맨 앞이 target인 동안 head를 다음으로 옮긴다 (이 분기가 따로 필요)
    while head is not None and head.val == target:
        head = head.next
    # ② 가운데~끝: curr.next가 target이면 건너뛰게 잇는다
    curr = head
    while curr is not None and curr.next is not None:
        if curr.next.val == target:
            curr.next = curr.next.next
        else:
            curr = curr.next
    return head

코드가 두 덩어리(①과 ②)로 갈렸죠. [3, 3, 1, 3, 2]에서 3을 지운다면, 맨 앞 3 두 개는 ①에서 head를 밀어 처리하고, 가운데 3은 ②에서 건너뛰게 잇습니다. 같은 "3을 지운다"인데 위치에 따라 다른 코드로 처리하는 게 영 거슬려요.

여기서 더미 헤드(dummy head, sentinel node)라는 깔끔한 기법이 나옵니다. 진짜 head 앞에 값이 의미 없는 가짜 노드 하나를 세워 두는 거예요. 그러면 진짜 맨 앞 노드도 "가짜 노드의 다음 노드"가 되어, 가운데 노드와 똑같이 다뤄집니다. 특별 취급이 사라져요.

def remove_all_dummy(head, target):
    """같은 일을, 더미(sentinel) 노드를 앞에 세워 head 예외 없이 한다.

    진짜 head 앞에 가짜 노드(dummy) 하나를 두면, '맨 앞 노드'도 '가운데 노드'와
    똑같이 'curr.next를 지운다' 한 가지 로직으로 처리된다. 앞쪽 특수 분기가 사라진다.
    끝에 dummy.next가 새 head다. O(n).
    """
    dummy = Node(0, head)        # 가짜 머리 — 진짜 head 앞 한 칸
    curr = dummy
    while curr.next is not None:
        if curr.next.val == target:
            curr.next = curr.next.next
        else:
            curr = curr.next
    return dummy.next

 더미 헤드 — 진짜 head 앞에 가짜 칸을 세운다

 [dummy]─▶ [ 3 ]─▶ [ 3 ]─▶ [ 1 ]─▶ [ 3 ]─▶ [ 2 ]
   └ 진짜 맨 앞(3)도 'dummy의 다음'이라, 가운데와 똑같이 'curr.next 지우기'로 처리
   끝에 dummy.next가 새 head (맨 앞이 지워졌어도 안전)

분기 ①이 통째로 사라졌습니다. while curr.next 하나로 맨 앞부터 끝까지 일관되게 처리하고, 마지막에 dummy.next를 새 head로 돌려줘요. 둘 다 [3, 3, 1, 3, 2]에서 3을 지우면 [1, 2]로 똑같은 결과가 나오지만, 코드가 훨씬 깔끔하죠. 시간 복잡도는 둘 다 한 번 훑는 O(n)으로 같습니다.

🎯 코테에서는 더미 헤드가 연결 리스트 문제의 단골 무기입니다. "노드 삭제", "두 리스트 병합", "중복 제거"처럼 맨 앞이 바뀔 수 있는 모든 문제에서, 더미 노드 하나로 경계 예외를 지워 버그를 크게 줄여요. 연결 리스트 문제를 만나면 "더미를 세울까?"를 먼저 떠올리는 습관이 큰 도움이 됩니다.

💡 한 줄 정리

더미 헤드는 진짜 head 앞에 세우는 가짜 노드다. 맨 앞 노드도 가운데와 똑같이 'curr.next를 고친다'로 다뤄져, head 특별 취급 분기가 통째로 사라진다(끝에 dummy.next가 새 head).

Step 5: "앞뒤 두 방향으로 잇는다" — 이중 연결 리스트와 deque의 정체

지금까지 화살표가 한 방향(다음 쪽)으로만 났습니다. 그래서 어떤 노드에서 앞으로 되돌아갈 수가 없었어요. 단일 연결 리스트의 delete_after가 "다음 노드"만 지울 수 있었던 것도 이 때문입니다 — 어떤 노드 자신을 지우려면 그 앞 노드를 알아야 하는데, 앞으로 가는 화살표가 없으니까요.

이중 연결 리스트(doubly linked list)는 화살표를 양방향으로 냅니다. 각 노드가 다음(next)뿐 아니라 이전(prev)도 가리켜요. 어느 노드에서든 앞뒤로 다 갈 수 있죠.

# structures/linked_list.py

class DoublyNode:
    """이중 연결 리스트의 노드: 값 + 이전(prev)·다음(next) 두 방향 포인터."""

    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

 이중 연결 리스트 — 앞뒤 두 방향 화살표

 head                                        tail
  ▼                                           ▼
 None ◀─[ 1 ]⇄[ 2 ]⇄[ 3 ]─▶ None
        각 노드가 prev·next 둘을 들어, 어느 쪽으로도 갈 수 있다
        head·tail을 둘 다 들고 있어 양 끝이 다 빠르다

여기에 머리(head)와 꼬리(tail)를 둘 다 들고 있게 하면, 양 끝에서 넣고 빼기가 전부 O(1)이 됩니다. 꼬리를 알고 있으니 append도 끝까지 걸어갈 필요가 없어요.

    def append(self, val):
        """꼬리 쪽에 잇는다. tail을 들고 있어 O(1)."""
        node = DoublyNode(val, prev=self.tail)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self._size += 1

    def appendleft(self, val):
        """머리 쪽에 끼운다. O(1)."""
        node = DoublyNode(val, next=self.head)
        if self.head is None:
            self.head = self.tail = node
        else:
            self.head.prev = node
            self.head = node
        self._size += 1

append(꼬리에 추가)·appendleft(머리에 추가), 그리고 양 끝을 떼는 pop·popleft까지 전부 O(1)입니다. 어디서 많이 본 동작이죠? 맞아요, 바로 지난 시간의 collections.deque입니다. deque의 append/appendleft/pop/popleft가 다 O(1)이라고 했던 그 정체가, 사실 이 이중 연결 리스트(에 가까운 구조)예요. 지난 시간에 약속한 "덱의 속" 확인을 지금 한 겁니다.

양방향의 진짜 보상은 노드 삭제입니다. 어떤 노드를 가리키는 node만 있으면, 앞 노드를 따로 찾지 않고 곧바로 떼어 낼 수 있어요. node.prev가 이미 앞을 가리키고 있으니까요.

    def delete(self, node):
        """주어진 노드를 떼어낸다. 양옆(prev·next)을 직접 이어 O(1).

        앞 노드를 따로 찾을 필요가 없다 — node.prev가 이미 가리키고 있으니까.
        이게 단일 연결 리스트의 delete_after(앞 노드가 있어야 함)와 갈리는 지점이다.
        """
        prev, nxt = node.prev, node.next
        if prev is not None:
            prev.next = nxt
        else:
            self.head = nxt
        if nxt is not None:
            nxt.prev = prev
        else:
            self.tail = prev
        self._size -= 1

단일 리스트는 "다음 노드"만 지울 수 있었는데(delete_after), 이중 리스트는 자기 자신을 O(1)에 지웁니다. 앞뒤를 다 아니까요. 대신 노드마다 포인터를 하나씩 더(prev) 들어야 하니 공간을 조금 더 씁니다. 또 트레이드오프죠. 양방향 이동과 자기 삭제를 얻고, 포인터 하나만큼의 공간을 내준 겁니다.

🎯 코테에서는 이중 연결 리스트를 직접 짜기보다 collections.deque를 그냥 씁니다. 양 끝 작업이 O(1)이라 BFS의 큐, 슬라이딩 윈도우, 회문 검사에 딱이에요. 다만 LRU 캐시 같은 문제는 "이중 연결 리스트 + 해시"가 정석 설계라, 원리를 알아 두면 면접에서 한 수 위로 답할 수 있습니다(해시는 다음 시간에 만나요).

💡 한 줄 정리

이중 연결 리스트는 각 노드가 prev·next 양방향을 들고, head·tail을 다 들어 양 끝 작업이 모두 O(1)이다. deque의 속이 바로 이것 — 노드를 알면 자기 자신을 O(1)에 삭제(delete)할 수 있다.

Step 6: "화살표 방향을 거꾸로" — 연결 리스트 뒤집기

연결 리스트 문제에서 가장 자주 나오는 단골이 뒤집기(reverse)입니다. 1 → 2 → 3을 3 → 2 → 1로 만드는 거예요. 값을 옮기는 게 아니라, 화살표(next)의 방향만 거꾸로 돌립니다.

핵심은 포인터 세 개를 쥐는 거예요. 지금 보는 노드(curr), 그 앞에 이미 뒤집어 둔 노드(prev), 그리고 다음에 갈 노드(nxt)입니다. 왜 nxt를 미리 적어 둬야 할까요? curr.next를 prev 쪽으로 돌려 버리면, 원래 가려던 다음 노드로 가는 길이 끊기거든요. 그래서 돌리기 전에 다음 노드를 손에 적어 둡니다.

# structures/linked_list.py

def reverse_list(head):
    """단일 연결 리스트를 뒤집는다. 세 포인터(prev·curr·next)로 화살표만 거꾸로.

    한 노드씩 보며 'next 화살표'를 앞 노드 쪽으로 돌린다. 미리 다음 노드를
    nxt에 적어 둬야 사슬이 끊기지 않는다. 한 번 훑으니 시간 O(n), 새 노드를
    안 만들고 포인터만 고쳐 공간 O(1). 새 머리(원래 꼬리)를 돌려준다.
    예: 1->2->3 을 뒤집으면 3->2->1.
    """
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next        # ① 다음 노드를 먼저 적어 둔다 (안 그러면 사슬이 끊긴다)
        curr.next = prev       # ② 화살표를 앞쪽으로 돌린다
        prev = curr            # ③ 한 칸 전진
        curr = nxt
    return prev                # 끝에 prev가 새 머리(원래 꼬리)

루프 한 바퀴가 노드 하나의 화살표를 뒤집습니다. 세 줄(①②③)의 순서가 생명이에요. 다음을 적어 두고(①) → 화살표를 돌리고(②) → 한 칸 전진(③). 그림으로 한 바퀴를 따라가 봅시다.

 reverse_list — 화살표를 한 칸씩 거꾸로

 시작:   prev=None    curr=1 ─▶ 2 ─▶ 3 ─▶ None

 1바퀴:  None ◀─ 1    curr=2 ─▶ 3 ─▶ None     (1의 화살표를 None 쪽으로)
 2바퀴:  None ◀─ 1 ◀─ 2    curr=3 ─▶ None     (2의 화살표를 1 쪽으로)
 3바퀴:  None ◀─ 1 ◀─ 2 ◀─ 3    curr=None     (3의 화살표를 2 쪽으로)

 끝:     prev=3 이 새 머리 → 3 ─▶ 2 ─▶ 1 ─▶ None

새 노드를 하나도 안 만들고, 기존 노드의 화살표만 돌렸습니다. 그래서 시간은 한 번 훑는 O(n), 공간은 포인터 세 개뿐이라 O(1)이에요. [1, 2, 3]을 뒤집으면 [3, 2, 1]이 나옵니다.

🎯 코테에서는 리스트 뒤집기가 그 자체로도 빈출이고(LeetCode "Reverse Linked List"), "리스트가 회문인지 판정", "K개씩 묶어 뒤집기" 같은 변형의 부품으로도 쓰입니다. 세 포인터 손놀림(nxt 적어 두기 → 돌리기 → 전진)은 통째로 외워 두면 시험장에서 손이 먼저 움직여요.

💡 한 줄 정리

리스트 뒤집기는 값이 아니라 화살표(next) 방향을 거꾸로 돌린다. prev·curr·nxt 세 포인터로, 다음을 적어 두고(끊김 방지) → 돌리고 → 전진하면 O(n) 시간·O(1) 공간으로 끝난다.

Step 7: "토끼와 거북이" — 두 포인터로 사이클 검출

마지막은 연결 리스트의 명장면, 사이클(cycle, 고리) 검출입니다. 보통 리스트는 끝에 None이 있어 언젠가 멈추는데, 만약 어떤 노드의 next가 앞쪽 노드를 다시 가리키면 사슬이 고리가 됩니다. 순회하면 None을 영영 못 만나 무한 루프에 빠지죠. "이 리스트에 고리가 있나?"를 알아내는 게 사이클 검출이에요.

 사이클(고리)이 있는 리스트

 1 ─▶ 2 ─▶ 3 ─▶ 4
       ▲          │
       └──────────┘   (4의 next가 2를 다시 가리킴 → None을 못 만난다)

가장 단순한 방법은 "지나온 노드를 전부 기록(set)해 두고, 이미 본 노드를 또 만나면 고리"입니다. 되긴 하지만 기록에 공간이 O(n) 들어요. 더 우아한 방법이 플로이드의 토끼와 거북이(Floyd's cycle detection)입니다. 포인터 두 개를 쓰되, 느린 거북이는 한 칸씩, 빠른 토끼는 두 칸씩 가게 해요.

# structures/linked_list.py

def has_cycle(head):
    """리스트에 사이클(고리)이 있는지. 플로이드의 '토끼와 거북이'. O(n) 시간·O(1) 공간.

    느린 포인터(slow)는 한 칸, 빠른 포인터(fast)는 두 칸씩 간다. 사이클이 없으면
    fast가 먼저 끝(None)에 닿고, 사이클이 있으면 fast가 트랙을 돌다 결국 slow를
    따라잡아 둘이 같은 노드에서 만난다. 방문 기록(set) 없이 포인터 둘로만 O(1) 공간.
    (이 빠른/느린 두 포인터 사고는 뒤에 '투 포인터' 시간에 다시 만난다.)
    """
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next            # 한 칸
        fast = fast.next.next       # 두 칸
        if slow is fast:            # 같은 노드에서 만나면 고리가 있다
            return True
    return False

왜 이게 통할까요? 고리가 없으면 토끼가 두 칸씩 가다 먼저 끝(None)에 닿아 False를 냅니다. 고리가 있으면 토끼가 고리를 빙빙 돌고, 거북이도 결국 고리 안으로 들어옵니다. 그러면 토끼가 거북이보다 매 칸 한 칸씩 빠르게 다가가 언젠가 반드시 같은 노드에서 만나요(운동장 트랙에서 빠른 주자가 느린 주자를 한 바퀴 따라잡듯). 만나면 True입니다.

기록용 set이 없으니 공간은 포인터 둘, O(1)이에요. 시간은 O(n)입니다. 같은 두 포인터 발상으로 가운데 노드 찾기도 한 번의 순회로 됩니다. 토끼가 끝에 닿을 때 거북이는 딱 절반 지점에 있거든요.

def find_middle(head):
    """가운데 노드를 한 번의 순회로 찾는다. 빠른/느린 두 포인터. O(n) 시간·O(1) 공간.

    fast가 두 칸씩 가 끝에 닿을 때, slow는 절반만 갔으니 가운데에 선다. 길이가
    짝수면 두 가운데 중 '뒤쪽'을 돌려준다(예: 1->2->3->4 면 3). 길이를 따로
    세어 n//2를 다시 훑는 두 번 순회 대신, 한 번에 끝낸다.
    """
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

길이를 먼저 세고(O(n)) 다시 절반을 훑는(O(n)) 두 번 순회 대신, 한 번의 순회로 가운데를 잡습니다. [1, 2, 3, 4, 5]면 가운데 3, [1, 2, 3, 4]면 뒤쪽 가운데 3이 나와요.

이 "빠른 포인터와 느린 포인터를 함께 움직인다"는 발상은 연결 리스트에만 머물지 않습니다. 다음에 배열에서 두 포인터로 구간을 O(n)에 훑는 투 포인터(two pointers) 기법으로 다시 만나요. 오늘은 그 맛보기를 연결 리스트에서 본 겁니다.

🎯 코테에서는 사이클 검출(LeetCode "Linked List Cycle"), 사이클 시작점 찾기, 끝에서 K번째 노드, 가운데 노드가 전부 두 포인터 한 가족입니다. "포인터 두 개를 다른 속도/간격으로 움직인다"는 패턴 하나로 이 문제들이 줄줄이 풀려요. 연결 리스트 문제에서 막히면 "포인터를 하나 더 둬 볼까?"를 떠올리세요.

💡 한 줄 정리

플로이드의 토끼와 거북이는 느린(한 칸)·빠른(두 칸) 두 포인터로 사이클을 O(1) 공간에 잡는다(만나면 고리). 같은 발상으로 가운데 노드도 한 번의 순회로 찾으며, 이 두 포인터 사고는 투 포인터 기법으로 이어진다.

마무리

오늘은 데이터를 직접 손으로 잇는 그릇, 연결 리스트를 만들었습니다. 노드(값 + 포인터)로 단일·이중 리스트를 잇고, 포인터만 고쳐 삽입·삭제를 O(1)에 해냈어요. 더미 헤드로 경계 예외를 지우고, 화살표를 거꾸로 돌려 리스트를 뒤집고, 토끼와 거북이로 고리까지 잡았습니다. 지난 시간 흘려 둔 "덱의 속"이 이중 연결 리스트였다는 것도 직접 확인했죠.

오늘 배운 핵심 세 가지

• 💡 하나 — 연결 리스트는 흩어 두고 포인터로 잇는다. 배열과 빅오가 거울처럼 갈린다. 배열은 인덱싱 O(1)·삽입 O(n), 연결 리스트는 인덱싱 O(n)·(노드를 알 때) 삽입·삭제 O(1)이다. "찾기 O(n)"과 "끼우기 O(1)"은 별개로 따진다.
• 💡 둘 — 포인터를 다루는 세 가지 정석 패턴. 더미 헤드(맨 앞 예외 제거), 세 포인터 뒤집기(화살표 거꾸로, O(1) 공간), 빠른/느린 두 포인터(사이클·가운데). 연결 리스트 문제의 대부분이 이 셋의 조합이다.
• 💡 셋 — 모든 선택은 트레이드오프다. 양 끝이 빠르면(이중) 포인터 공간을 더 쓰고, 인덱싱이 빠르면(배열) 삽입이 느리다. 자료구조는 "무엇이 더 좋다"가 아니라 "이 문제에서 무슨 연산이 자주 일어나나"로 고른다.

다음 시간 예고

오늘까지 "값으로 노드를 찾기"는 늘 O(n)이었습니다. 연결 리스트도, 배열도, 값을 찾으려면 처음부터 하나씩 비교해야 했죠. 그런데 만약 값을 O(1)에 곧장 찾는 그릇이 있다면 어떨까요?

다음 시간(B-3)엔 선형 자료구조의 마지막 주자, 해시 테이블(hash table)을 만납니다. "값 자체로 위치를 계산해" 평균 O(1)에 넣고 찾는 마법 같은 그릇이에요. 파이썬의 dict와 set이 바로 이것입니다. 그 비밀인 해시 함수와, 두 값이 같은 칸으로 몰릴 때 생기는 충돌(collision)을 어떻게 푸는지를 직접 짜 봅니다. 오늘 본 연결 리스트가 충돌 처리(체이닝)에서 다시 등장하니, 노드를 잇는 손을 잘 기억해 두세요.

과제

오늘 배운 연결 리스트를 직접 손으로 다뤄 보는 문제들입니다. 풀어 본 뒤 예시 답안과 맞춰 보세요. 각 풀이의 시간·공간 복잡도를 빅오로 적는 것도 잊지 마세요.

[기초] 특정 값 노드 모두 삭제하기

단일 연결 리스트의 head와 값 target이 주어질 때, 값이 target인 노드를 모두 삭제하고 새 head를 돌려주는 함수를 작성하세요. 맨 앞 노드가 target일 수도 있습니다(예: [1, 2, 1, 3, 1]에서 target=1이면 [2, 3]). 오늘 배운 더미 헤드를 써서, 맨 앞 노드도 가운데 노드와 똑같은 한 가지 로직으로 처리해 보세요. 시간·공간 복잡도도 빅오로 적으세요. (이 유형은 LeetCode Easy "Remove Linked List Elements" 패턴입니다.)

[응용] 정렬된 두 연결 리스트 병합하기

각각 오름차순으로 정렬된 두 단일 연결 리스트의 head가 주어집니다. 두 리스트를 합쳐 하나의 정렬된 리스트로 만들고 새 head를 돌려주는 함수를 작성하세요(예: [1, 3, 5]와 [2, 4] → [1, 2, 3, 4, 5]). 두 리스트의 머리를 비교해 작은 쪽을 결과에 붙이고, 그 리스트의 포인터를 한 칸 전진시키는 식으로 풉니다. 더미 헤드를 결과 리스트의 시작점으로 두면 "결과의 첫 노드" 예외가 사라져 깔끔해져요. 두 리스트 길이가 각각 n, m일 때 시간 복잡도를 빅오로 적으세요. (LeetCode Easy "Merge Two Sorted Lists" 패턴.)

[심화] 사이클의 시작 노드 찾기

연결 리스트에 사이클이 있을 때, 고리가 시작되는 노드(처음으로 다시 방문하게 되는 노드)를 돌려주는 함수를 작성하세요. 사이클이 없으면 None입니다. 오늘 배운 토끼와 거북이로 "고리가 있다"까지는 잡았는데, 시작점은 어떻게 찾을까요?

플로이드 알고리즘의 2단계가 답입니다. 토끼와 거북이가 처음 만난 지점에서, 포인터 하나를 head로 되돌리고 두 포인터를 이번엔 둘 다 한 칸씩 움직이면, 둘이 다시 만나는 곳이 바로 사이클의 시작입니다. 왜 그런지(거리 관계를 식으로) 설명까지 곁들이면 좋아요. 시간 O(n)·공간 O(1)로 풀어 보세요. 입력이 10만 노드라면 set으로 기록하는 O(n) 공간 풀이와 비교해 무엇이 유리한지도 "1초 1억 연산"과 메모리 관점에서 한 줄 적으세요. (LeetCode Medium "Linked List Cycle II" 패턴.)

생각해볼 주제

정답이 하나가 아닌 질문들입니다. 혼자 고민해도 좋고, 스터디에서 토론해도 좋아요.

1. 파이썬엔 연결 리스트가 따로 없는데, 왜 배울까?

파이썬의 list는 사실 동적 배열이고, 양 끝 작업은 deque로 충분합니다. 그래서 코딩테스트에서 연결 리스트를 직접 짜 제출할 일은 거의 없어요. 그런데도 이 자료구조를 배우는 이유는 무엇일까요? "삽입·삭제 O(1) vs 인덱싱 O(1)"이라는 트레이드오프 감각, 포인터를 다루는 사고, 그리고 트리·그래프로 이어지는 노드 개념을 엮어서 생각해 보세요. "실전에서 안 쓰는데 왜 배우나"라는 질문에 스스로 답해 보는 겁니다.

2. 더미 헤드는 왜 버그를 줄일까?

더미 헤드는 노드 하나를 더 써서 "맨 앞 노드 특별 취급"을 없앱니다. 그런데 이건 단순히 코드가 짧아지는 것 이상의 의미가 있어요. 프로그램의 버그는 대개 "보통 경우"가 아니라 "경계(맨 앞·맨 끝·빈 경우)"에서 터집니다. 더미 헤드가 "경계를 보통 경우로 바꾼다"는 관점에서, 왜 이게 버그를 줄이는지 설명해 보세요. 그리고 이 "경계를 없애는" 발상이 연결 리스트 말고 어디에서 또 통할지(예: 배열의 양 끝에 보초 값 두기)도 떠올려 보세요.

3. 토끼와 거북이는 왜 set 풀이보다 우아할까?

사이클 검출은 "지나온 노드를 set에 기록"으로도 풀립니다(시간 O(n), 공간 O(n)). 토끼와 거북이는 같은 시간 O(n)에 공간을 O(1)로 줄이죠. 두 풀이 모두 정답인데, 무엇이 토끼와 거북이를 "더 우아하다"고 부르게 할까요? 공간 복잡도만의 문제일까요, 아니면 "추가 자료구조 없이 포인터만으로 푼다"는 점이 주는 다른 가치가 있을까요? 반대로, set 풀이가 더 나은 상황(예: 사이클의 시작점뿐 아니라 모든 방문 노드가 필요할 때)은 없을지도 생각해 보세요.