연결 리스트 - 포인터로 잇기

이 장에서 배우는 것

앞 장에서 배열은 번호로 원소를 찾아가는 구조였다. 중간에 빈자리를 만들려면 뒤의 원소들을 옮겨야 했다. 이번에는 원소를 담은 작은 객체들이 서로 다음 객체를 가리키게 만든다. 원소 전체를 옮기는 대신 연결을 바꾸는 방식이다. 전공 수업에서는 이러한 구조를 연결 리스트(linked list)라고 부른다.

이 장에서는 연결이 바뀌는 과정을 코드와 그림으로 확인한다. 완성 코드에서는 이중 연결 리스트를 만들고, 최근에 사용한 항목을 앞쪽으로 옮기는 캐시의 뼈대를 구현한다. 《논리로 푸는 알고리즘》이 자료구조를 이용해 문제를 해결하는 쪽이라면, 이 책은 그 자료구조의 내부를 직접 만드는 쪽이다.

• 단일 연결 리스트와 이중 연결 리스트의 차이를 설명한다.
• 삽입과 삭제에서 바꿔야 할 참조와 순서를 확인한다.
• 더미 노드로 양 끝의 예외 처리를 줄인다.
• 탐색 방문 횟수와 연결 대입 횟수를 세어 시간 복잡도를 확인한다.
• 이중 연결 리스트로 사용 순서를 관리하고 내장 자료구조의 결과와 비교한다.

문제 상황

설정 파일을 읽는 도구를 만든다고 하자. 같은 파일을 여러 번 읽는 일이 잦아 최근에 읽은 결과 두 개를 잠시 보관하려 한다. 새 결과를 저장할 때 공간이 부족하면 가장 오랫동안 사용하지 않은 결과를 버린다. 기존 결과를 다시 사용했다면 그 결과를 가장 최근 위치로 옮겨야 한다.

이처럼 다시 쓸 가능성이 있는 결과를 보관하는 공간을 캐시(cache)라고 한다. 그중 가장 오래 사용하지 않은 항목부터 내보내는 정책을 최근 최소 사용 정책, 줄여서 LRU(Least Recently Used)라고 부른다. 여기서 오래되었다는 기준은 저장한 시각만이 아니라 마지막으로 사용한 순서다.

배열의 앞을 최근 위치로 정하면 중간 항목을 앞으로 옮길 때 여러 원소가 이동한다. 반면 연결 리스트에서는 항목을 담은 객체의 연결을 끊고 앞에 다시 붙일 수 있다. 다만 먼저 해당 객체를 찾아야 한다. 이 장의 캐시는 찾는 과정도 직접 순회하므로 전체 조회는 항목 수에 비례한다. 순서 변경이 빠르다는 사실과 조회 전체가 빠르다는 주장은 구분해야 한다.

완성 프로그램은 파일을 실제로 읽지 않는다. 파일 식별자 대신 정수 키를, 읽은 결과 대신 문자열을 사용한다. 외부 환경 없이도 저장, 재사용, 퇴출 순서를 확인하기 위해서다.

객체를 참조로 연결한다

데이터와 연결 정보를 함께 담은 단위를 노드(node)라고 한다. 파이썬에서 노드는 클래스로 정의한 객체로 만들 수 있다. 다른 객체를 가리키는 값을 참조(reference)라고 한다. 전공 수업에서는 노드 사이의 연결을 설명할 때 포인터(pointer)라는 말을 흔히 쓴다. 이 장에서는 파이썬 객체 참조로 그 역할을 구현한다. 메모리 주소를 계산하거나 주소에 직접 값을 쓰지는 않는다.

단일 연결 리스트는 각 노드에 다음 노드를 가리키는 next를 둔다. 마지막 노드의 next에는 연결 대상이 없다는 뜻으로 None을 저장한다. 첫 노드를 가리키는 참조를 보관하면 next를 따라 전체 원소를 읽을 수 있다. 이렇게 연결을 하나씩 따라가는 일을 순회(traversal)라고 한다.

그림의 좌우 배치는 읽는 순서다. 실제 객체들이 메모리에서도 이 순서로 붙어 있다는 뜻은 아니다. 배열은 논리적으로 연속된 칸을 번호로 선택하지만, 연결 리스트는 각 노드가 다음 위치에 대한 정보를 보관한다.

A 다음에 X를 끼우려면 먼저 X.next에 원래 A.next를 저장하고, 그다음 A.next를 X로 바꾼다. 순서를 바꾸면 뒤쪽 노드로 가는 연결을 잃을 수 있다. 다음 코드는 완성 프로그램에 들어 있는 단일 연결 예제다. 고정된 노드 세 개만 사용해 연결 변경 자체를 살펴본다.

a.next = b
x.next = a.next
a.next = x

실행 후 읽는 순서는 A, X, B다. X를 삭제하려면 X 바로 앞에 있는 A를 알고 있어야 한다. A.next를 X.next로 바꾸면 된다. X가 뒤쪽을 계속 가리키지 않도록 X.next도 None으로 정리한다. 단일 연결 리스트는 뒤로 가는 연결이 없으므로 삭제 대상만 알아서는 그 앞 노드의 next를 바꿀 수 없다.

맨 앞 노드는 앞 노드가 없다는 점도 주의해야 한다. 더미 노드가 없는 단일 연결 리스트에서 맨 앞을 삭제한다면 첫 노드를 보관하는 변수 자체를 다음 노드로 바꿔야 한다. 단순히 지역 변수에 다른 노드를 대입하는 것으로는 리스트의 시작점이 갱신되지 않는다.

배열과 연결 리스트가 원소에 도달하는 방법

작업	배열	연결 리스트
i번째 원소 읽기	번호로 해당 칸 선택	첫 노드부터 i번 연결 이동
중간에 삽입	뒤쪽 원소 이동	위치를 찾은 뒤 연결 변경
저장 공간	원소를 담는 칸	원소와 노드별 연결 정보
순서대로 읽기	인접한 칸을 차례로 읽음	각 노드의 다음 참조를 읽음

연결 리스트가 배열보다 언제나 빠른 것은 아니다. 연결 리스트에는 노드 객체와 참조를 저장하는 공간이 필요하다. 연속된 메모리 영역을 읽는 배열이 실제 실행에서 유리한 경우도 많다. 연결 변경이 적다는 사실만으로 프로그램 전체의 실행 시간을 판단해서는 안 된다.

양방향 연결과 더미 노드

이중 연결 리스트(doubly linked list)는 다음 노드뿐 아니라 이전 노드도 가리킨다. 노드의 prev가 이전 노드를, next가 다음 노드를 가리킨다. 가운데 노드를 알고 있다면 앞 노드를 다시 찾지 않고 양쪽 이웃을 연결할 수 있다.

대신 지켜야 하는 관계가 늘어난다. A.next가 B라면 B.prev도 A여야 한다. 연산 전후에 계속 참이어야 하는 조건을 불변식(invariant)이라고 한다. 이 장의 핵심 불변식은 서로 이웃한 두 노드의 앞뒤 연결이 일치한다는 것이다.

양 끝에는 데이터를 저장하지 않는 더미 노드(dummy node)를 둔다. head는 시작 경계를, tail은 끝 경계를 나타낸다. 전공 수업에서는 이런 경계용 노드를 센티널(sentinel)이라고도 부른다. 빈 리스트에서도 head.next는 tail이고 tail.prev는 head다. 데이터가 하나 들어가도 두 경계 노드는 그대로 남는다.

left와 right 사이에 새 노드를 넣으려면 네 참조를 설정한다. 새 노드의 prev와 next를 지정하고, 두 이웃이 새 노드를 가리키게 만든다. 삭제할 때는 left.next와 right.prev를 서로 연결한다. 삭제한 노드의 prev와 next도 None으로 정리하지만, 이는 남은 리스트의 연결을 복구하는 작업과 구분해서 센다.

완성 코드의 writes는 리스트 안의 앞뒤 관계를 만들거나 바꾸는 참조 대입 횟수다. 삽입은 4회, 삭제는 2회다. 노드 생성, 더미 노드 초기화, 삭제한 노드 정리, 원소 수 변경은 이 계수에 넣지 않는다. 이처럼 무엇을 세는지 먼저 정해야 숫자를 해석할 수 있다.

find는 방문한 데이터 노드 수를 visits에 누적한다. 더미 노드와 끝 검사 횟수는 포함하지 않는다. 첫 항목을 찾으면 1회이고, n개가 있는 리스트에서 없는 값을 찾으면 n회다. n이 늘어도 삽입의 연결 대입은 4회지만, 탐색 방문은 늘어날 수 있다. 전공 수업에서는 전자를 상수 시간 O(1), 후자의 최악 상황을 선형 시간 O(n)이라고 부른다.

시간 복잡도는 입력 크기가 커질 때 필요한 작업량의 증가 양상이다. 여기서 O는 증가율의 상한을 표현하는 표기다. 이 장의 횟수는 특정 작업을 골라 센 값이며 실행 시간의 모든 비용을 합산한 값은 아니다. 그래도 입력 크기와 함께 늘어나는 작업을 구별하는 데 도움이 된다.

연결 리스트로 사용 순서를 관리한다

캐시의 앞쪽에는 가장 최근에 사용한 항목을 두고, 뒤쪽에는 가장 오래 사용하지 않은 항목을 둔다. 조회에 성공하면 해당 노드를 떼어 앞에 붙인다. 새 항목을 넣을 때 공간이 가득 찼다면 tail.prev가 가리키는 데이터 노드를 먼저 삭제한다.

리스트에는 키와 값을 함께 저장한다. 키는 항목을 구분하는 식별자이며 값은 보관할 결과다. 같은 키로 다시 저장하면 값과 사용 순서를 함께 갱신한다. 없는 키를 조회하면 None을 돌려준다. 이 예제는 저장 값으로 문자열만 사용하므로 조회 실패와 실제 값을 구별할 수 있다.

키를 찾는 도구는 아직 따로 만들지 않는다. find가 앞에서부터 키를 하나씩 비교한다. 따라서 캐시에 n개가 있으면 조회와 저장은 최악의 경우 O(n)이다. 찾은 뒤 순서를 바꾸는 부분만 O(1)이다. 키에서 노드로 빠르게 접근하는 구조를 추가하는 일은 해시 테이블을 다룰 때 이어갈 수 있다.

구현에서 공개한 push_front는 새로 만든 노드를 받는다. remove와 move_front는 현재 리스트에 들어 있는 데이터 노드를 받는다. 더미 노드나 다른 리스트의 노드를 전달하는 사용법은 지원하지 않는다. 자료구조가 받는 입력 조건을 밝히는 것도 구현의 일부다. 모든 잘못된 사용을 검사하려면 소속 정보를 추가하는 등의 설계가 더 필요하다.

완성 코드

다음 내용을 main.py에 저장한다. 직접 만든 구조에서는 내장 list, dict, set이나 큐 도구를 저장소로 사용하지 않는다. 연결 리스트는 노드 참조만으로 저장소를 구성하므로 내부 배열도 필요하지 않다. 마지막 비교용 ReferenceLRU에서만 내장 dict를 사용한다. 문자열을 이어 만드는 text는 출력용이며 탐색이나 저장을 대신하지 않는다.

class SingleNode:
    def __init__(self, value):
        self.value = value
        self.next = None


def single_demo():
    a = SingleNode("A")
    b = SingleNode("B")
    x = SingleNode("X")
    a.next = b

    x.next = a.next
    a.next = x
    text = ""
    node = a
    visits = 0
    while node is not None:
        if text:
            text += " "
        text += node.value
        visits += 1
        node = node.next
    print(f"단일 삽입: {text} | 방문={visits}")

    a.next = x.next
    x.next = None
    print(f"단일 삭제: {a.value} {a.next.value}")


class Node:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
        self.visits = 0
        self.writes = 0

    def push_front(self, node):
        left = self.head
        right = left.next
        node.prev = left
        node.next = right
        left.next = node
        right.prev = node
        self.size += 1
        self.writes += 4

    def remove(self, node):
        left = node.prev
        right = node.next
        left.next = right
        right.prev = left
        self.writes += 2
        self.size -= 1
        node.prev = None
        node.next = None

    def move_front(self, node):
        if self.head.next is node:
            return
        self.remove(node)
        self.push_front(node)

    def find(self, key):
        node = self.head.next
        while node is not self.tail:
            self.visits += 1
            if node.key == key:
                return node
            node = node.next
        return None

    def text(self):
        result = ""
        node = self.head.next
        while node is not self.tail:
            if result:
                result += " "
            result += f"{node.key}:{node.value}"
            node = node.next
        return result if result else "(비어 있음)"


class LRUCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("용량은 양수여야 한다")
        self.capacity = capacity
        self.items = DoublyLinkedList()

    def get(self, key):
        node = self.items.find(key)
        if node is None:
            return None
        self.items.move_front(node)
        return node.value

    def put(self, key, value):
        node = self.items.find(key)
        if node is not None:
            node.value = value
            self.items.move_front(node)
            return
        if self.items.size == self.capacity:
            self.items.remove(self.items.tail.prev)
        self.items.push_front(Node(key, value))


def list_demo():
    items = DoublyLinkedList()
    items.push_front(Node("C", "c"))
    items.push_front(Node("B", "b"))
    items.push_front(Node("A", "a"))
    print(f"이중 삽입: {items.text()} | 연결 대입={items.writes}")

    node = items.find("B")
    print(f"B 탐색: {node.value} | 방문={items.visits}")
    before = items.writes
    items.remove(node)
    print(f"B 삭제: {items.text()} | 연결 대입={items.writes - before}")

    node = items.tail.prev
    before = items.writes
    items.move_front(node)
    print(f"끝을 앞으로: {items.text()} | 연결 대입={items.writes - before}")


def growth_demo():
    for count in (1, 4, 8):
        items = DoublyLinkedList()
        for key in range(count):
            items.push_front(Node(key, key))
        items.find(-1)
        print(
            f"크기={count} | 없는 키 방문={items.visits}"
            f" | 삽입 연결 대입={items.writes}"
        )


class ReferenceLRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = dict()
        self.key_ops = 0

    def get(self, key):
        self.key_ops += 1
        if key not in self.data:
            return None
        value = self.data.pop(key)
        self.data[key] = value
        self.key_ops += 2
        return value

    def put(self, key, value):
        self.key_ops += 1
        if key in self.data:
            self.data.pop(key)
            self.key_ops += 1
        elif len(self.data) == self.capacity:
            oldest = next(iter(self.data))
            self.data.pop(oldest)
            self.key_ops += 1
        self.data[key] = value
        self.key_ops += 1

    def text(self):
        result = ""
        for key in reversed(self.data):
            if result:
                result += " "
            result += f"{key}:{self.data[key]}"
        return result if result else "(비어 있음)"


def cache_demo():
    custom = LRUCache(2)
    builtin = ReferenceLRU(2)
    same = True
    for cache in (custom, builtin):
        cache.put(1, "A")
        cache.put(2, "B")
        hit = cache.get(1)
        cache.put(3, "C")
        miss = cache.get(2)
        cache.put(1, "AA")
        same = same and hit == "A" and miss is None

    actual = custom.items.text()
    expected = builtin.text()
    print(f"직접 LRU: {actual}")
    print(f"내장 dict 기준: {expected}")
    print(f"조회와 순서 일치: {same and actual == expected}")
    print(
        f"직접 계수: 방문={custom.items.visits}"
        f" | 연결 대입={custom.items.writes}"
    )
    print(f"내장 계수: 키 연산={builtin.key_ops}")


def main():
    single_demo()
    list_demo()
    growth_demo()
    cache_demo()


if __name__ == "__main__":
    main()

줄별 해설

SingleNode의 value는 데이터이고 next는 다음 노드다. single_demo에서 a.next = b로 처음 두 노드를 연결한다. x.next = a.next는 뒤쪽 연결을 새 노드에 먼저 보관하는 줄이다. 이어지는 a.next = x가 삽입을 마무리한다. while문은 현재 노드가 None이 될 때까지 데이터를 읽는다. 출력의 방문 3회는 A, X, B를 각각 한 번 읽었다는 뜻이다.

삭제의 a.next = x.next는 A에서 X를 건너뛰고 B로 가게 한다. x.next = None은 분리한 노드의 연결을 정리한다. 이것은 객체 메모리를 직접 해제하는 명령이 아니다. 파이썬의 객체 수명 관리와 리스트에서 노드를 떼는 작업은 구분해야 한다. 이 예제에서는 지역 변수 x가 여전히 그 객체를 가리킨다.

Node의 기본값 None은 더미 노드를 만들 때도 같은 클래스를 사용하기 위한 것이다. head와 tail은 key나 value가 None인지 검사해서 구별하지 않는다. 객체 자체가 경계 노드인지를 is로 검사한다. 따라서 데이터의 내용과 경계의 역할이 섞이지 않는다. 전공 수업에서 객체의 동일성이라고 부르는 것은 값이 같은지가 아니라 같은 객체인지의 문제다.

DoublyLinkedList의 생성자는 빈 상태의 두 경계를 연결한다. head.prev와 tail.next는 None으로 남는다. 실제 데이터가 있는 방향만 순회하므로 바깥쪽 연결은 필요하지 않다. size는 더미 노드를 제외한 원소 수다. 매번 원소를 세지 않고 삽입과 삭제 때 갱신한다.

push_front에서 right를 먼저 보관하는 이유는 원래 첫 데이터 노드를 잃지 않기 위해서다. 빈 리스트라면 right는 tail이다. 네 줄의 참조 대입이 끝나면 새 노드 양쪽의 연결이 모두 맞는다. 이 네 줄 사이에는 잠시 불변식이 성립하지 않을 수 있다. 이 코드는 다른 실행 흐름이 도중에 리스트를 읽거나 수정하는 상황을 다루지 않는다.

remove는 양 이웃을 지역 변수로 확보한 뒤 서로 연결한다. 이후 노드의 연결을 None으로 지운다. 정리를 먼저 하면 이웃을 얻을 수 없으므로 순서가 중요하다. remove를 같은 노드에 두 번 호출하는 것도 허용하지 않는다. 첫 삭제 후에는 prev와 next가 None이기 때문이다.

move_front의 첫 검사는 이미 맨 앞인지 확인한다. 맨 앞이라면 연결 대입은 0회다. 나머지는 삭제 2회와 삽입 4회를 합쳐 6회다. remove에서 size가 하나 줄고 push_front에서 하나 늘어나므로 이동 전후 원소 수는 같다. 노드를 새로 생성하지 않아 기존 노드를 가리키던 참조도 유지된다.

find에서 visits를 증가시키는 줄은 키 비교 직전에 있다. 성공한 노드도 방문에 포함된다. text도 순회하지만 visits에는 더하지 않는다. 사용자에게 보여 주는 문자열 생성 비용이 탐색 계수에 섞이지 않게 한 것이다. 출력 문자열을 반복해서 잇는 방식은 큰 리스트의 효율적인 출력 구현을 목표로 하지 않는다.

list_demo는 C, B, A 순서로 앞에 넣어 최종 순서를 A, B, C로 만든다. B는 두 번째 방문에서 발견된다. 삭제 후에는 A, C가 남는다. tail.prev로 C를 바로 얻어 앞으로 옮기므로 이 이동에는 추가 탐색이 없다. before는 누적 계수에서 이번 연산에 해당하는 차이만 구하기 위한 값이다.

growth_demo의 튜플 (1, 4, 8)은 실험 크기를 적어 둔 입력이며 직접 만든 저장소가 아니다. range는 해당 횟수만큼 반복하게 한다. 각 리스트에는 음수가 없는 키만 넣으므로 find(-1)은 항상 끝까지 방문한다. 방문은 1, 4, 8로 늘고, 삽입 연결 대입의 총합은 4, 16, 32가 된다. 삽입 한 번당 4회라는 비율은 그대로다.

LRUCache의 생성자는 용량이 0 이하인 입력을 거부한다. get은 찾기에 성공했을 때만 순서를 바꾼다. put은 기존 키의 갱신을 먼저 처리한다. 그렇지 않으면 가득 찬 상태에서 기존 키를 갱신할 때 다른 항목을 불필요하게 퇴출할 수 있다. 새 키이고 가득 찼을 때만 가장 뒤의 데이터 노드를 제거한다.

ReferenceLRU는 마지막 비교를 위한 내장 dict 구현이다. dict의 삽입 순서를 이용해 가장 오래된 항목을 앞쪽에 둔다. 기존 키를 사용하면 pop으로 뺀 뒤 다시 저장하여 마지막 위치로 옮긴다. 출력할 때는 역순으로 읽어 직접 만든 캐시와 같은 최근 순서를 보여 준다.

key_ops는 포함 여부 검사, pop, 키를 지정한 저장을 각각 1회로 센다. 길이 조회, 반복자 생성과 이동, 출력용 조회는 제외한다. 내부에서 실제로 몇 번 비교했는지를 뜻하지 않는다. 표준 인터페이스만으로 dict 내부의 모든 탐색 횟수를 관찰할 수 없기 때문이다. 서로 다른 계수를 단위 없이 나누어 속도 배율로 해석해서는 안 된다.

실행 결과

명령은 문법 검사와 실행 순서다. 문법 검사에서는 출력이 없고 프로그램 실행 결과만 다음과 같이 나타난다. 난수를 사용하지 않으므로 실행할 때마다 같은 결과를 얻는다.

python3 -W error -m py_compile main.py
python3 -W error main.py

단일 삽입: A X B | 방문=3
단일 삭제: A B
이중 삽입: A:a B:b C:c | 연결 대입=12
B 탐색: b | 방문=2
B 삭제: A:a C:c | 연결 대입=2
끝을 앞으로: C:c A:a | 연결 대입=6
크기=1 | 없는 키 방문=1 | 삽입 연결 대입=4
크기=4 | 없는 키 방문=4 | 삽입 연결 대입=16
크기=8 | 없는 키 방문=8 | 삽입 연결 대입=32
직접 LRU: 1:AA 3:C
내장 dict 기준: 1:AA 3:C
조회와 순서 일치: True
직접 계수: 방문=9 | 연결 대입=26
내장 계수: 키 연산=14

캐시의 순서를 따라가 보자. 1과 2를 저장하면 최근 순서는 2, 1이다. 1을 읽으면 1, 2가 된다. 이어서 3을 넣으면 오래된 2가 나가고 3, 1이 남는다. 2 조회는 실패하므로 순서를 바꾸지 않는다. 마지막으로 1의 값을 AA로 갱신하면 1, 3이 된다.

직접 만든 캐시의 여섯 요청에서 방문 수는 차례로 0, 1, 2, 2, 2, 2다. 합은 9다. 연결 대입은 4, 4, 6, 6, 0, 6으로 합이 26이다. 조회 실패는 연결을 바꾸지 않으며, 퇴출과 새 삽입이 함께 일어나면 2 + 4회다.

내장 기준 구현은 포함 여부 검사 6회, 저장 5회, pop 3회로 키 연산이 14회다. 두 결과가 같다는 검사는 이번 요청열의 반환값과 마지막 순서가 일치한다는 뜻이다. 모든 가능한 입력에 대한 증명은 아니다. 또한 직접 구현의 방문 9회와 내장 구현의 키 연산 14회는 관찰 수준이 다르므로 어느 쪽이 빠르다는 결론을 주지 않는다.

실무에서 자주 틀리는 것

뒤쪽 연결을 보관하기 전에 덮어쓴다

다음 코드는 A 뒤에 X를 넣으려다가 X가 자기 자신을 가리키게 만든다. 첫 줄이 끝나면 a.next가 이미 x이므로 둘째 줄은 x.next = x와 같다. 이 상태에서 끝을 찾는 순회는 종료되지 않는다.

a.next = x
x.next = a.next

원래 다음 노드로 가는 참조를 먼저 새 노드에 저장한다. 완성 코드의 단일 삽입 예제가 이 순서를 실행한다.

x.next = a.next
a.next = x

이중 연결에서 한쪽만 고친다

앞에서부터 읽을 때 문제가 보이지 않아도 뒤로 읽으면 삭제한 노드가 다시 나타날 수 있다. 다음 코드는 오른쪽 노드의 prev를 그대로 둔다.

left.next = right

두 방향을 함께 수정한다. 완성 코드의 remove에서 쓰는 두 줄이다. 정방향 순회가 성공했다는 사실만으로 양방향 연결이 올바르다고 판단하지 않는다.

left.next = right
right.prev = left

빈 상태에서 더미 노드를 삭제한다

빈 리스트의 tail.prev는 head다. 다음 코드를 빈 상태에서 실행하면 데이터가 아닌 경계 노드를 제거하려 한다. head.prev가 None이므로 remove의 연결 변경도 수행할 수 없다.

items.remove(items.tail.prev)

외부에서 끝 원소를 제거하는 기능을 추가한다면 원소 수를 먼저 검사한다. 캐시에서는 양수 용량과 가득 찼다는 조건이 이 상황을 막는다. 다른 호출 위치에도 같은 조건이 자동으로 적용되는 것은 아니다.

if items.size > 0:
    items.remove(items.tail.prev)

조회에 성공해도 사용 순서를 그대로 둔다

다음 get은 값을 돌려주지만 사용 기록을 갱신하지 않는다. 그러면 방금 읽은 항목이 다음 저장에서 퇴출될 수 있다. 단순 저장 순서와 최근 사용 순서는 다르다.

def get(self, key):
    node = self.items.find(key)
    if node is None:
        return None
    return node.value

성공한 조회에서 이동을 수행한다. 완성 코드의 캐시 요청열은 이 차이를 확인한다. 1을 읽은 뒤 3을 넣었을 때 1이 남고 2가 나가야 한다.

def get(self, key):
    node = self.items.find(key)
    if node is None:
        return None
    self.items.move_front(node)
    return node.value

한눈에 보기

이 장의 연산 조건과 관찰할 작업량

연산	필요한 조건	관찰한 횟수	시간 복잡도
단일 리스트 중간 삽입	바로 앞 노드를 앎	연결 대입 2회	O(1)
단일 리스트 중간 삭제	바로 앞 노드를 앎	우회 연결 1회, 분리 정리 1회	O(1)
이중 리스트 앞 삽입	새 노드가 분리된 상태	연결 대입 4회	O(1)
이중 리스트 삭제	소속 데이터 노드를 앎	연결 대입 2회	O(1)
앞으로 이동	소속 데이터 노드를 앎	이미 앞이면 0회, 아니면 6회	O(1)
키 탐색	데이터 노드 n개	최대 n개 방문	O(n)
이 장의 캐시 조회·저장	키를 순회로 찾음	최대 n개 방문과 상수 회 연결 변경	O(n)

이중 연결 리스트는 데이터 노드 n개와 더미 노드 두 개를 만든다. 각 노드가 고정된 수의 참조를 가지므로 저장 공간은 O(n)이다. 단일 연결 리스트도 O(n)이지만 노드마다 연결 하나만 둔다. 같은 증가율이라는 말은 실제 저장 바이트까지 같다는 뜻이 아니다.

배열은 번호로 자주 읽는 요구에 잘 맞고, 연결 리스트는 이미 알고 있는 노드의 순서를 자주 바꾸는 요구에 잘 맞는다. 삭제할 값을 먼저 찾아야 한다면 탐색 비용도 포함한다. 다음 장에서 다룰 스택과 큐처럼 넣고 빼는 위치를 제한하면, 연결 리스트의 어느 끝을 관리할지에 따라 구현이 달라진다.

연습 문제

1. 빈 이중 연결 리스트에서 시작해 값 하나를 삽입하고 삭제하라. 두 더미 노드가 다시 직접 연결되는지 검사하고 연결 대입 합계를 출력하라.
2. 데이터를 뒤에서 앞으로 읽는 reverse_text 메서드를 추가하라. list_demo에서 B를 삭제한 직후 역순 결과가 C:c A:a인지 확인하라.
3. 노드가 네 개 있는 리스트에서 맨 앞, 맨 뒤, 없는 키를 차례로 탐색하라. 매번 visits의 차이를 출력하고, 없는 키의 방문 수가 마지막 키의 방문 수와 같은 이유를 설명하라.
4. 캐시 용량을 1로 두고 1 저장, 1 갱신, 2 저장을 수행하라. 각 단계의 순서와 마지막 조회 결과를 확인하라. 용량을 0으로 주면 왜 거부해야 하는지도 설명하라.

정답과 해설

빈 상태로 돌아오기

다음 코드는 완성 코드의 클래스 정의 아래에서 실행할 수 있다. assert는 뒤의 조건이 거짓이면 AssertionError를 발생시키는 검사문이다. 참이면 다음 줄로 진행한다. 일반 실행에서 내부 관계를 확인하는 용도로 사용한다.

items = DoublyLinkedList()
node = Node(7, "G")
items.push_front(node)
items.remove(node)
assert items.head.next is items.tail
assert items.tail.prev is items.head
assert items.size == 0
assert node.prev is None and node.next is None
print(items.writes)
# 출력: 6

삽입 4회와 삭제 2회의 합이다. 빈 상태를 복구할 때도 일반 삭제와 같은 두 이웃 연결 규칙을 사용한다. 더미 노드의 이점은 이런 경계 사례에서 확인할 수 있다.

역방향으로 읽기

다음 메서드를 DoublyLinkedList 안에 추가한다. 정방향에서 시작이 head.next였다면 역방향에서는 tail.prev다. 종료 경계도 tail에서 head로 바뀐다.

def reverse_text(self):
    result = ""
    node = self.tail.prev
    while node is not self.head:
        if result:
            result += " "
        result += f"{node.key}:{node.value}"
        node = node.prev
    return result if result else "(비어 있음)"

list_demo의 B 삭제 출력 다음에 print(items.reverse_text())를 넣으면 C:c A:a가 출력된다. 잘못된 삭제 코드처럼 오른쪽 prev를 고치지 않았다면 여기서 삭제한 B를 만나거나 연결이 끊긴 지점에 도달할 수 있다.

탐색 방문 수 비교

items = DoublyLinkedList()
for key in (4, 3, 2, 1):
    items.push_front(Node(key, key))

for key in (1, 4, 9):
    before = items.visits
    items.find(key)
    print(items.visits - before)
# 출력:
# 1
# 4
# 4

실제 순서는 1, 2, 3, 4다. 없는 키도 네 데이터 노드를 모두 확인해야 한다. 마지막 데이터 뒤에서 tail을 만나는 검사는 방문 계수에 포함하지 않으므로 두 경우 모두 4다. 마지막 키는 노드를 반환하고 없는 키는 None을 반환한다는 차이가 있다.

용량이 하나인 캐시

cache = LRUCache(1)
cache.put(1, "A")
print(cache.items.text())
cache.put(1, "AA")
print(cache.items.text())
cache.put(2, "B")
print(cache.items.text())
print(cache.get(1))
print(cache.get(2))
# 출력:
# 1:A
# 1:AA
# 2:B
# None
# B

기존 키 갱신은 원소 수를 늘리지 않는다. 용량이 하나이면 갱신 대상은 이미 맨 앞이므로 이동의 연결 대입도 0회다. 새 키 2가 들어올 때만 기존 키 1을 퇴출한다.

용량 0에서 현재 put의 가득 참 검사를 그대로 실행하면 빈 리스트의 head를 삭제하려 한다. 이 구현은 생성 시 ValueError로 거부한다. 저장을 항상 무시하는 용량 0 캐시를 따로 설계할 수도 있지만, 그 경우에는 put의 동작과 검사를 함께 바꿔야 한다. 입력 조건, 경계 처리, 연결 불변식을 하나의 약속으로 맞추는 일이 구현을 마무리하는 기준이다.