연결 리스트란? 동작 원리, 코드, 시간 복잡도

연결 리스트가 해결하는 문제

배열(파이썬의 list)은 요소를 메모리의 연속된 한 덩어리에 보관합니다. a[i]를 읽는 것은 즉시 끝나지만, 맨 앞에 삽입하면 나머지 요소가 모두 한 칸씩 오른쪽으로 밀리므로 O(n)이 듭니다. 연결 리스트는 이 이동을 피합니다. 각 요소가 자기만의 노드에 들어 있고 노드끼리는 참조로 연결되어 있어서, 삽입할 때는 참조 몇 개만 바꾸면 됩니다.

연결 리스트는 스택, 큐, 해시 테이블 버킷(체이닝), LRU 캐시, 그래프의 인접 리스트 등 많은 자료구조의 기본 재료입니다.

쉬운 말로 설명하는 원리

보물찾기를 떠올려 보세요. 각 단서는 다음 단서가 어디 있는지 알려 줍니다. 7번 단서로 바로 건너뛸 수는 없고, 1번부터 6번까지 차례로 따라가야 합니다. 리스트 자체는 첫 번째 노드인 head만 기억하고, 마지막 노드는 아무것도 가리키지 않습니다(None).

예제: 삽입과 삭제

3 -> 7 -> 9 리스트에서 시작합니다. 3 뒤에 5를 삽입한 다음 7을 삭제합니다.

1. 값이 5인 새 노드를 만듭니다.
2. new.next를 3 다음 노드(7)로 설정합니다.
3. node3.next를 새 노드로 설정합니다. 이제 리스트는 3 -> 5 -> 7 -> 9입니다.
4. 7을 삭제하려면 head부터 따라가 7 바로 앞 노드(5)를 찾습니다.
5. node5.next = node5.next.next로 7을 건너뜁니다. 이제 리스트는 3 -> 5 -> 9입니다. 도달할 수 없게 된 노드는 파이썬의 가비지 컬렉터가 해제합니다.

파이썬으로 구현하는 단일 연결 리스트

이 클래스는 head 참조와 크기 카운터를 유지합니다. 앞과 뒤에 추가하기, 처음으로 일치하는 값 삭제하기, 순회를 지원합니다.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1
    def push_back(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1
    def remove(self, value):
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False          # not found
        if prev is None:
            self.head = cur.next  # removing the head
        else:
            prev.next = cur.next
        self.size -= 1
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next

items = LinkedList()
for x in [3, 7, 9]:
    items.push_back(x)
items.push_front(1)
items.remove(7)
print(list(items), items.size)  # [1, 3, 9] 3

여기서 push_back은 리스트 전체를 따라가므로 O(n)입니다. tail 참조를 추가로 유지하면 O(1)이 되며, 실제 큐 구현은 이렇게 합니다.

대표 연산: 뒤집기와 사이클 탐지

리스트를 제자리에서 뒤집는 것은 연결 리스트 코딩 면접에서 가장 흔한 문제입니다. 리스트를 한 번 순회하면서 각 next 포인터의 방향을 돌립니다.

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next     # remember the rest
        cur.next = prev    # turn the pointer around
        prev, cur = cur, nxt
    return prev            # new head
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)  # 3 2 1
print(has_cycle(head))  # False

has_cycle은 플로이드의 토끼와 거북이 알고리즘입니다. 느린 포인터는 한 칸, 빠른 포인터는 두 칸씩 움직입니다. 루프가 있으면 빠른 포인터가 결국 느린 포인터와 만나고, 없으면 None에 도달합니다. 추가 메모리는 O(1)만 사용합니다.

시간 복잡도와 공간 복잡도

실제로는 연결 리스트의 빅오가 더 좋은 연산에서도 배열이 더 빠른 경우가 많습니다. 배열 요소는 메모리에서 나란히 놓여 CPU 캐시를 잘 활용하지만, 연결 리스트의 노드는 흩어져 있기 때문입니다.

변형과 흔한 실수

• 빈 리스트를 잊는 실수: head.next를 읽기 전에 항상 head is None을 확인하세요.
• next를 저장하기 전에 덮어써서 리스트의 나머지를 잃는 실수(reverse의 nxt 참고).
• 첫 번째 노드를 삭제할 때 head를, 마지막 노드를 삭제할 때 tail을 갱신하지 않는 실수.
• 매우 긴 리스트에 재귀를 쓰는 실수: 파이썬의 기본 재귀 한도는 약 1000 프레임이므로 반복문 코드가 더 안전합니다.
• 더미(센티널) head 노드를 두면 대부분의 특수 처리가 사라집니다. 모든 실제 노드가 앞 노드를 갖게 되기 때문입니다.
• 이중 연결 리스트에서는 삽입과 삭제마다 참조 네 개를 갱신해야 합니다. 하나라도 빠뜨리면 리스트가 조용히 망가집니다.

연결 리스트를 쓸 때와 파이썬에서 대신 쓸 것

이미 참조를 쥐고 있는 위치에서 양 끝이나 중간에 삽입·삭제를 하고, 임의 접근이 거의 필요 없을 때 연결 리스트를 사용하세요. 예로는 LRU 캐시(이중 연결 리스트와 해시 맵), 메모리 할당기의 프리 리스트, 실행 취소 기록, 해시 테이블의 버킷이 있습니다.

일상적인 파이썬 코드에서는 직접 만들 일이 드뭅니다. 큐나 덱에는 양쪽 끝에서 O(1)로 추가·제거할 수 있는 collections.deque를 쓰고, 일반적인 시퀀스에는 list를 쓰세요. 연결 리스트를 직접 구현하는 것은 학습, 면접, 그리고 LRU 캐시처럼 노드를 O(1)에 이어 붙여야 할 때입니다.

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
print(q.popleft(), q.pop(), list(q))  # 0 4 [1, 2, 3]