연결 리스트의 노드·링크·소유권을 설명하고 단일·이중 연결 구현, 역순 변환, 순환 검출, 정렬 병합과 LRU 캐시를 예제 및 기준 모델 대조로 살펴본다.
개요: 위치를 링크로 표현하는 순서 자료구조
연결 리스트(linked list)는 값과 다음 노드의 위치를 묶은 노드들을 연결하여 순서를 표현하는 자료구조다. 배열에서는 시작 주소와 원소 크기로 i번째 위치를 계산하지만, 연결 리스트에서는 앞 노드가 다음 노드를 가리킨다. 논리적으로 이웃인 원소가 메모리에서도 이웃일 필요는 없다.
재생 목록 A→B→C를 생각하면, A와 B 사이에 X를 넣을 때 뒤쪽 모든 값을 한 칸씩 이동하는 대신 A→X→B로 연결을 바꿀 수 있다. 그러나 A가 어디에 있는지 모르면 먼저 찾아야 한다. 이 위치 탐색과 실제 연결 변경을 분리해야 성능을 올바르게 이해할 수 있다.
단일 연결 리스트는 다음 링크 하나, 이중 연결 리스트는 이전·다음 링크를 가진다. 마지막이 첫 노드로 돌아가는 원형 구조도 있다. 이들은 서로 대체 가능한 동일 구현이 아니라 필요한 연산과 불변식이 다른 변형이다.
이 문서는 노드의 정체성과 값의 차이부터 직접 구현, 역순 변환, 순환 검출, 정렬된 목록 병합과 LRU 캐시까지 설명한다. Python 예제는 3.9.6에서 실행했다. 교육용 구현의 정확성 검증과 실제 서비스의 동시성·메모리 관리 보장은 구분한다.
최소 노드와 순회 구현
Node는 value와 next를 가진다. head는 첫 노드이고 None은 끝을 뜻한다. build는 입력 시퀀스를 뒤에서부터 읽으며 앞에 붙이므로 최종 순서는 입력과 같다. 입력이 뒤집을 수 없는 일회용 이터레이터라면 이 함수의 계약과 맞지 않는다.
values_of는 next를 따라가며 값을 새 Python 목록에 담는다. 연결 리스트를 출력하거나 기준 자료와 비교하려는 보조 함수이며 O(n) 시간과 O(n) 출력 공간이 든다. 값을 읽기만 하는 순회는 결과 목록을 만들지 않고 노드 하나씩 처리할 수 있다.
None은 링크의 끝 표시이고 노드에 저장한 값 None과 다르다. Node(None)도 정상 노드이므로 while current.value 같은 조건으로 순회하면 안 된다. 0이나 빈 문자열도 정상 값이다. 연결의 존재 여부를 검사해야 한다.
아래 세 값이 출력되는 것은 값 복사가 아니라 노드 간 링크 순서가 10→20→30이기 때문이다. build는 새 노드들을 만들지만 값이 가변 객체라면 값 객체 자체까지 깊게 복사하는 것은 아니다.
예제 코드
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def build(values):
head = None
for value in reversed(values):
head = Node(value, head)
return head
def values_of(head):
result = []
while head is not None:
result.append(head.value)
head = head.next
return result
head = build([10, 20, 30])
print(head.value, head.next.value)
print(values_of(head))
print(values_of(build([None, 0, ''])))
실행 결과
10 20
[10, 20, 30]
[None, 0, '']값이 같아도 노드는 다를 수 있다
두 노드가 모두 7을 저장해도 같은 노드인 것은 아니다. 값 비교는 자료의 내용에 대한 비교이고 객체 동일성은 정확히 같은 저장 단위를 가리키는지에 대한 비교다. 순환 검출이나 공유 꼬리 판별에서는 동일성을 사용해야 한다.
아래 a와 b의 값은 같지만 a is b는 False다. alias는 a의 또 다른 참조이므로 alias를 통해 값을 바꾸면 a에서도 보인다. 연결 리스트를 다른 변수에 대입하는 것만으로 복제된 목록이 생기지 않는다.
실제로는 노드에 고유 식별자를 두거나 메모리 주소·참조를 사용한다. 값이 중복될 수 있는 자료구조에서 “이 값의 노드를 삭제”와 “이 특정 노드를 삭제”는 서로 다른 API다. 전자는 검색 조건과 중복 정책이 필요하고 후자는 유효한 노드 참조가 필요하다.
노드 참조를 외부에 공개하면 외부 코드가 오래된 참조를 계속 보관할 수 있다. 이후 삭제·이동한 노드를 다시 사용하는 것을 허용하는지, 거부하는지 계약이 필요하다. 뒤의 이중 연결 구현은 소속 정보를 사용해 잘못된 삭제를 거부한다.
예제 코드
a, b = Node(7), Node(7)
alias = a
print(a.value == b.value, a is b, alias is a)
alias.value = 9
print(a.value, b.value)
실행 결과
True False True
9 7삽입은 새 연결을 먼저 준비한다
A 다음에 X를 삽입할 때 먼저 X.next를 기존 A.next로 정하고, 그 다음 A.next를 X로 바꾼다. 새 노드가 나머지 목록을 이어받은 다음 앞부분과 연결되므로 기존 꼬리로 가는 길을 잃지 않는다.
순서를 잘못 바꾸어 A.next=X부터 실행한 뒤 X.next=A.next로 쓰면 X.next가 X 자신이 된다. 원래 B로 가는 링크를 덮어 버렸기 때문에 X에서 빠져나오지 못하는 순환을 만든다. 문장 두 개의 순서가 구조의 의미를 바꾸는 사례다.
아래는 A→B를 A→X→B로 바꾼다. head는 그대로이고 B 노드도 그대로다. 새 노드 하나와 링크 두 개만 필요하다는 말은 삽입 위치 A를 이미 알고 있고 값 생성·노드 할당의 비용을 별도로 본다는 전제다.
앞에 삽입할 때는 new.next=head, head=new로 첫 노드 참조를 교체한다. 함수 내부의 지역 head를 바꾸는 것만으로 호출자의 변수가 자동 변경되지는 않으므로 새 head를 반환하거나 이를 보관하는 컨테이너 객체를 사용한다.
예제 코드
head = build(['A', 'B'])
new = Node('X', head.next)
head.next = new
print(values_of(head))
head = Node('START', head)
print(values_of(head))
실행 결과
['A', 'X', 'B']
['START', 'A', 'X', 'B']삭제에는 앞 노드가 필요한 이유
단일 연결 목록에서 A→B→C의 B를 제거하려면 A.next를 C로 바꾼다. B의 next만 바꿔서는 A가 계속 B를 가리키므로 B가 목록에서 사라지지 않는다. 특정 노드 B만 알고 이전 노드를 모르는 상황과 이전 노드 A를 이미 알고 있는 상황의 비용이 다르다.
삭제 후 B.next를 None으로 비우면 남아 있는 B 참조가 전체 꼬리를 붙잡는 것을 줄일 수 있다. 그러나 이는 소유권 계약에 따른 선택이다. 다른 목록이 같은 B를 공유하고 있다면 링크 변경이 그 목록도 바꾼다. 이 문서의 변경 알고리즘은 외부에서 구조를 공유하지 않는다는 전제를 둔다.
B의 다음 값을 B에 복사하고 다음 노드를 지우는 기법은 모든 삭제의 일반 해법이 아니다. 마지막 노드에는 다음 값이 없으며 노드의 정체성, 외부 참조와 값 이동 비용도 달라진다. “노드만 알면 단일 연결 삭제 O(1)”이라고 무조건 일반화하면 안 된다.
아래 예제에서는 두 번째 노드 참조를 따로 보관한 뒤 목록에서 분리한다. 남은 순서는 A,C이며 분리된 노드의 값 B 자체는 읽을 수 있다. 메모리 관리 언어에서는 실제 해제 후 사용은 별도 오류가 된다.
예제 코드
head = build(['A', 'B', 'C'])
removed = head.next
head.next = removed.next
removed.next = None
print(values_of(head))
print(removed.value, removed.next)
실행 결과
['A', 'C']
B None탐색 비용과 수정 비용을 합쳐 계산한다
길이 n의 단일 연결 리스트에서 i번째 노드를 얻으려면 head에서 i번 링크를 따라가므로 O(i+1)이다. 끝 위치는 O(n)이다. 이중 연결은 가까운 끝에서 출발해 이동 수를 줄일 수 있지만 가운데 접근의 선형 성질은 사라지지 않는다.
인덱스 i에 삽입하는 전체 작업은 위치 탐색 O(n)과 연결 변경 O(1)의 합이다. 이미 커서나 노드 참조를 가지고 반복적으로 이웃에서 작업하는 상황에서는 연결 변경의 장점이 드러날 수 있다. 입력이 매번 인덱스뿐이라면 그 장점을 그대로 기대하기 어렵다.
get(0), get(1), …, get(n-1)을 각각 head부터 구현하면 이동 수의 합이 0+1+…+(n-1)이 되어 O(n²)이다. 목록 전체를 한 번 따라가는 반복자는 O(n)이다. 같은 데이터를 순서대로 출력하는 코드도 접근 인터페이스에 따라 비용이 바뀐다.
n=5일 때 독립 인덱스 조회의 링크 이동 합은 10이고 한 번의 전체 순회는 각 노드에서 다음으로 5번 이동한다. 이 작은 수치를 속도 벤치마크로 해석하지 않는다. 비교의 핵심은 n이 커질 때 반복되는 탐색 작업의 증가 방식이다.
예제 코드
n = 5
print(sum(range(n)))
head = build(list(range(n)))
steps = 0
while head is not None:
steps += 1
head = head.next
print(steps)
실행 결과
10
5head·tail·size를 함께 유지하는 큐
head와 tail을 함께 저장하면 뒤 추가와 앞 제거로 FIFO 큐를 만들 수 있다. 새 노드는 기존 tail 다음에 연결하고 tail을 갱신한다. 빈 큐에서는 head도 새 노드가 되어야 한다. 마지막 노드를 제거하면 head와 tail을 모두 None으로 돌려놓는다.
tail이 있다고 뒤 제거까지 상수 시간이 되는 것은 아니다. 단일 연결에서는 마지막 노드의 이전 노드를 다시 찾아야 하기 때문이다. 스택은 head에서 넣고 빼는 방식으로, 큐는 tail에 넣고 head에서 빼는 방식으로 설계하면 필요한 연산을 효율적으로 지원한다.
아래 구현에서 size는 유효 노드 수다. size=0이면 head와 tail이 모두 None이고, size>0이면 tail.next가 None이어야 한다. 매 수정 때 이 관계를 보존해야 다음 연산이 올바르게 동작한다.
빈 제거는 IndexError를 발생시킨다. None은 정상 값이므로 빈 상태를 None 반환만으로 표현하지 않았다. 이 구현은 단일 스레드이며 대기·역압·영속성 같은 작업 큐 기능은 제공하지 않는다.
예제 코드
class LinkedQueue:
def __init__(self):
self.head = self.tail = None
self.size = 0
def append(self, value):
node = Node(value)
if self.tail is None:
self.head = node
else:
self.tail.next = node
self.tail = node
self.size += 1
def popleft(self):
if self.head is None:
raise IndexError('queue empty')
old = self.head
self.head = old.next
old.next = None
self.size -= 1
if self.head is None:
self.tail = None
return old.value
q = LinkedQueue()
q.append('A'); q.append('B')
print(q.popleft(), q.popleft())
print(q.size, q.head is None, q.tail is None)
q.append('C')
print(q.popleft())
실행 결과
A B
0 True True
C빈 상태와 원소 하나가 구현을 흔드는 지점
여러 원소가 있을 때는 head를 다음으로 옮기기만 해도 충분해 보이지만 마지막 원소를 제거한 뒤 tail을 그대로 두면 문제가 생긴다. 다음 append가 사라진 옛 노드 뒤에 새 노드를 연결하고 head는 None으로 남을 수 있다. 길이만 갱신하면 더 발견하기 어려워진다.
빈 상태에서 반복 제거해도 이미 비어 있는 상태는 바뀌지 않아야 한다. 하나 넣고 하나 빼기를 여러 번 반복하는 검사는 처음 한 번만 비우는 검사보다 재사용 경로를 더 잘 확인한다. 중간 값에 None과 중복을 넣어 표시값 혼동도 확인한다.
삭제한 노드를 따로 보관하는 테스트에서는 그 노드와 아직 유효한 목록의 연결을 끊었는지 검사할 수 있다. 다만 메모리 회수 시점 자체는 런타임과 다른 참조에 따라 달라지므로 next=None을 했다고 운영체제에 즉시 반환되었다고 말하지 않는다.
아래 검사는 빈 제거의 예외를 확인한 다음 0, None, 2를 각각 넣고 꺼낸다. 각 단계에서 세 상태 변수의 관계를 검사한다. 정상 값과 빈 표시를 분리한 계약이 실제 코드에도 적용되는지 확인하는 예다.
예제 코드
q = LinkedQueue()
try:
q.popleft()
except IndexError:
print('empty rejected')
for value in [0, None, 2]:
q.append(value)
assert q.popleft() == value
assert q.size == 0 and q.head is None and q.tail is None
print('reuse passed')
실행 결과
empty rejected
reuse passed역순 변환: 남은 꼬리를 잃지 않는 세 변수
연결 리스트를 역순으로 만들려면 각 노드의 next 방향을 바꾼다. current.next를 previous로 덮기 전에 following에 원래 다음 노드를 보관한다. 그 다음 previous=current, current=following으로 경계를 한 칸 이동한다.
반복의 불변식은 previous가 이미 뒤집은 앞부분, current가 아직 처리하지 않은 뒷부분의 첫 노드라는 것이다. 두 부분을 합치면 원래 모든 노드가 정확히 한 번 포함된다. current가 None이 되면 전체가 뒤집혔고 previous가 새 head다.
시간은 O(n), 노드 참조 변수의 보조 공간은 O(1)이다. 기존 노드를 재사용하므로 값 복사는 없다. 그러나 출력 확인용 values_of는 별도로 O(n) 공간을 사용한다. 알고리즘 자체와 테스트·출력 도구의 공간을 섞지 않는다.
외부 코드가 기존 head를 계속 보관하면 그 노드는 이제 마지막 노드다. 새 시작점을 반환값으로 받아야 한다. 공유 꼬리가 있으면 다른 목록에도 영향을 주므로 이 함수는 독립된 유한 비순환 목록에 적용한다.
예제 코드
def reverse_links(head):
previous = None
current = head
while current is not None:
following = current.next
current.next = previous
previous = current
current = following
return previous
head = build([1, 2, 3, 4])
old_head = head
head = reverse_links(head)
print(values_of(head))
print(old_head.value, old_head.next)
print(values_of(reverse_links(head)))
실행 결과
[4, 3, 2, 1]
1 None
[1, 2, 3, 4]더미 노드로 머리 삭제를 일반화하기
특정 값과 같은 모든 노드를 삭제한다고 하자. 첫 노드를 지우면 head가 바뀌지만 중간 노드를 지우면 이전 노드의 next가 바뀐다. 더미 노드를 head 앞에 두면 첫 노드에도 이전 노드가 생겨 같은 규칙으로 처리할 수 있다.
previous.next가 삭제 대상이면 그 링크를 다음으로 우회시키고 previous는 그대로 둔다. 연속된 삭제 대상이 다음에 또 올 수 있기 때문이다. 삭제하지 않을 때만 previous를 전진한다. 매번 전진하면 [2,2,3]에서 두 번째 2를 건너뛸 수 있다.
dummy의 값은 검색 대상이 아니다. None을 저장해도 실제 None 값 노드와 혼동하지 않도록 dummy 자체는 결과에서 제외한다. 마지막에는 dummy.next를 반환해 변경된 첫 노드를 돌려준다.
아래 함수는 모든 노드를 한 번씩 검사하므로 O(n)이고 더미 노드 하나 외에 길이에 비례하는 보조 저장소를 만들지 않는다. 삭제한 노드의 next를 끊으므로 구조 공유가 없는 목록이라는 전제가 여기에도 필요하다.
예제 코드
def remove_all(head, target):
dummy = Node(None, head)
previous = dummy
while previous.next is not None:
current = previous.next
if current.value == target:
previous.next = current.next
current.next = None
else:
previous = current
return dummy.next
for data in [[2, 2, 3, 2], [2], [], [1, 3]]:
print(values_of(remove_all(build(data), 2)))
실행 결과
[3]
[]
[]
[1, 3]순환은 값의 반복이 아니라 노드 재방문이다
1→2→1처럼 값이 반복되는 정상 목록과 어떤 노드가 자기 이전 노드로 돌아가는 순환 목록은 다르다. 값의 집합에 이미 들어 있는지만 검사하면 중복 값이 있는 정상 목록을 순환으로 오판한다. 노드 동일성을 추적해야 한다.
방문한 노드의 집합을 저장하면 다시 등장한 동일 노드를 찾을 수 있다. 구현이 쉽지만 O(n) 보조 공간이 든다. 순환 없는 입력만 받는 values_of를 순환 목록에 그대로 실행하면 끝나지 않으므로 디버깅 출력에도 방문 제한이 필요하다.
아래에서는 값 1인 서로 다른 두 노드를 사용한다. 처음에는 끝이 None이라 순환이 없고, 마지막 노드의 next를 head로 연결하면 순환이 생긴다. 출력 함수가 아니라 별도 검출 함수로 확인한다.
이 문서의 Node는 기본 객체 동일성 해시를 사용한다. 값 기반 동등성·해시를 따로 정의한 클래스를 쓰면 집합 검출의 의미도 검토해야 한다. 뒤의 두 포인터 방식은 is로 정확한 노드 동일성을 비교한다.
예제 코드
def has_cycle_set(head):
seen = set()
while head is not None:
if head in seen:
return True
seen.add(head)
head = head.next
return False
head = build([1, 2, 1])
print(has_cycle_set(head))
head.next.next.next = head
print(has_cycle_set(head))
실행 결과
False
TrueFloyd 방식으로 순환의 입구 찾기
slow는 한 칸, fast는 두 칸씩 이동한다. 순환이 없으면 fast나 fast.next가 None이 된다. 순환이 있으면 두 포인터가 모두 순환 안에 들어간 이후 상대 위치가 매 단계 한 칸씩 바뀌므로 결국 같은 노드에서 만난다.
입구 이전 길이를 μ, 순환 길이를 λ라고 하자. 만날 때 slow가 이동한 총 거리 t와 fast의 2t 차이는 순환 길이의 배수이므로 t≡0 (mod λ)다. slow의 순환 내부 위치는 t−μ≡−μ (mod λ)다. 한 포인터를 head로 옮겨 둘 다 한 칸씩 μ번 이동하면 입구에서 만난다.
아래 cycle_entry는 순환이 없으면 None, 있으면 입구 노드 자체를 반환한다. 값만 반환하면 같은 값을 가진 여러 노드를 구분하지 못하므로 노드 참조를 반환한다. 시간은 O(μ+λ), 보조 참조 공간은 O(1)이다.
검사 중 다른 코드가 링크를 변경하면 이동 경로가 바뀌므로 이 증명이 그대로 적용되지 않는다. 동시 수정 없는 구조를 전제로 한다. 검출은 순환을 알려 줄 뿐 어떤 링크를 끊어 복구해야 하는지 업무 의도까지 결정하지 않는다.
예제 코드
def cycle_entry(head):
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:
seeker = head
while seeker is not slow:
seeker = seeker.next
slow = slow.next
return seeker
return None
nodes = [Node(x) for x in ['A', 'B', 'C', 'D']]
for a, b in zip(nodes, nodes[1:]):
a.next = b
nodes[-1].next = nodes[1]
print(cycle_entry(nodes[0]).value)
print(cycle_entry(build([1, 1, 1])) is None)
self_loop = Node('X')
self_loop.next = self_loop
print(cycle_entry(self_loop) is self_loop)
실행 결과
B
True
True중간 노드와 빠른 포인터의 경계 계약
slow와 fast를 함께 쓰는 패턴은 순환뿐 아니라 중간 위치를 찾는 데도 쓰인다. 매번 slow 한 칸, fast 두 칸을 이동하면 fast가 끝날 때 slow는 가운데에 있다. 다만 짝수 길이에서는 가운데가 두 개라 어느 쪽을 반환하는지 정해야 한다.
아래 구현은 길이 4에서 인덱스 2의 세 번째 원소를 반환한다. 즉 뒤쪽 가운데다. 빈 목록은 None이며 길이 1은 유일한 노드다. 연결 리스트 병합 정렬을 위해 앞부분을 끊는 코드에서는 앞쪽 가운데가 필요할 수도 있으므로 같은 코드를 무작정 재사용하지 않는다.
fast.next.next 접근 전에 fast와 fast.next가 존재하는지 확인한다. 조건 검사 순서가 중요하다. 종료 조건을 한 칸 잘못 정하면 None의 next에 접근하거나 짝수 길이에서 다른 위치를 돌려줄 수 있다.
이 방법은 전체 길이를 먼저 계산하지 않아도 되지만 시간은 여전히 O(n)이다. 길이를 이미 가지고 있다고 해도 중간 노드로 즉시 점프할 수는 없다. “한 번의 순회”와 “상수 시간”은 다른 표현이다.
예제 코드
def middle(head):
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow
for length in range(5):
node = middle(build(list(range(length))))
print(length, None if node is None else node.value)
실행 결과
0 None
1 0
2 1
3 1
4 2정렬된 두 목록을 노드 이동으로 병합하기
두 목록이 각각 오름차순이면 앞 노드 둘 중 더 작은 것을 결과 꼬리에 붙이고 해당 입력 포인터를 전진한다. 둘 중 하나가 끝나면 다른 목록의 남은 꼬리를 통째로 연결할 수 있다. 각 노드를 최대 한 번 선택하므로 O(n+m)이다.
아래 함수는 새 데이터 노드를 만들지 않고 기존 링크를 바꾼다. 더미 노드와 몇 개의 참조만 사용하므로 보조 공간은 O(1)이다. 함수 호출 후 입력 두 목록을 서로 독립된 원본처럼 다시 사용하면 안 된다. 비파괴 병합이 필요하면 새 노드를 만드는 방식과 그 비용을 선택한다.
동일한 값에서는 왼쪽 노드를 먼저 선택하는 <= 규칙을 사용한다. 각 입력 내부 순서를 보존하면서 왼쪽에 우선권을 주는 안정적인 병합이다. 값 비교가 일관적인 전순서를 이룬다는 전제가 있으며 NaN 같은 특별값은 별도 처리 정책이 필요할 수 있다.
입력 목록 두 개가 같은 꼬리를 공유하거나 순환을 포함하면 이 구현의 계약을 벗어난다. 특히 공유 노드를 중복해서 연결하면 자기 순환이 생길 수 있다. 서로 독립적인 비순환 정렬 목록이라는 조건을 명시해야 한다.
예제 코드
def merge_sorted(left, right):
dummy = Node(None)
tail = dummy
while left is not None and right is not None:
if left.value <= right.value:
chosen, left = left, left.next
else:
chosen, right = right, right.next
tail.next = chosen
tail = chosen
tail.next = left if left is not None else right
return dummy.next
left = build([1, 3, 5])
right = build([1, 2, 6])
print(values_of(merge_sorted(left, right)))
print(values_of(merge_sorted(None, build([2, 4]))))
실행 결과
[1, 1, 2, 3, 5, 6]
[2, 4]이중 연결과 원형 센티널의 불변식
이중 연결 노드는 prev와 next를 함께 보관한다. A↔B↔C에서 B를 삭제하려면 A.next=C, C.prev=A를 모두 수정한다. 한쪽만 바꾸면 정방향 결과는 맞아 보여도 역방향 순회가 삭제된 노드를 다시 방문할 수 있다.
센티널 root를 앞뒤 경계에 공통으로 쓰면 빈 목록에서 root.next=root.prev=root다. 원소가 있으면 root.next가 첫 노드, root.prev가 마지막 노드이며 양끝은 root로 돌아온다. 이 원형 구조는 의도된 표현이므로 None까지 순회하는 방식으로는 종료되지 않는다.
모든 연결된 노드 x에 대해 x.next.prev is x와 x.prev.next is x가 성립해야 한다. 센티널도 같은 관계를 따른다. 이 불변식은 삽입·삭제의 구현과 검증을 단순하게 만든다.
더미 노드라고 해서 메모리가 없는 가상의 표식은 아니다. 실제 노드 하나를 추가하고 그 값은 일반 자료로 취급하지 않는 것이다. 순회 종료 조건은 값이 None인지가 아니라 현재 노드가 root와 같은지다.
소속 검사를 포함한 이중 연결 구현
DList는 지정 노드 앞 삽입과 알려진 노드 삭제를 제공한다. root 앞 삽입은 뒤 추가, root.next 앞 삽입은 앞 추가가 된다. insert_before가 돌려주는 노드 참조를 저장하면 나중에 위치 검색 없이 삭제할 수 있다.
owner는 노드의 소속 목록을 나타낸다. 다른 목록의 노드 앞에 삽입하거나 이미 삭제한 노드를 또 삭제하려는 시도를 ValueError로 거부한다. root 자체도 일반 원소처럼 삭제할 수 없다. 구조의 공개 필드를 임의로 조작하는 공격까지 방어하는 구현은 아니다.
삭제 후 노드는 자신을 가리키게 하고 owner=None으로 만든다. 순회 함수는 root를 만나면 멈추며 정방향과 역방향을 모두 제공한다. values는 출력 목록을 만들므로 O(n)이고 연결 변경 자체의 O(1) 비용과 구분한다.
원소 값 생성과 노드 할당, 값 객체의 수명에 따른 비용은 별도다. 이 코드의 고정 개수 링크 변경을 근거로 임의 객체의 생성·파괴까지 항상 일정한 시간이 걸린다고 설명하지 않는다.
예제 코드
class DNode:
def __init__(self, value=None):
self.value = value
self.prev = self.next = self
self.owner = None
class DList:
def __init__(self):
self.root = DNode()
self.root.owner = self
self.size = 0
def insert_before(self, position, value):
if position.owner is not self:
raise ValueError('foreign position')
node = DNode(value)
before = position.prev
node.prev, node.next = before, position
before.next, position.prev = node, node
node.owner = self
self.size += 1
return node
def remove(self, node):
if node is self.root or node.owner is not self:
raise ValueError('invalid node')
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
node.prev = node.next = node
node.owner = None
return node.value
def values(self, backward=False):
result = []
current = self.root.prev if backward else self.root.next
while current is not self.root:
result.append(current.value)
current = current.prev if backward else current.next
return result
items = DList()
a = items.insert_before(items.root, 'A')
c = items.insert_before(items.root, 'C')
b = items.insert_before(c, 'B')
print(items.values(), items.values(True))
print(items.remove(b), items.values())
try:
items.remove(b)
except ValueError:
print('double removal rejected')
실행 결과
['A', 'B', 'C'] ['C', 'B', 'A']
B ['A', 'C']
double removal rejected원소와 범위 이동, O(1)이라는 말의 범위
이중 연결에서 이미 알려진 노드 하나를 떼어 다른 위치에 붙이는 작업은 고정 개수의 링크 변경으로 표현할 수 있다. 객체 값 전체를 복사하지 않고 순서만 바꿀 수 있는 점이 유용하다. 외부에 노드 참조가 있으면 같은 노드라는 정체성도 유지할 수 있다.
하지만 임의의 구간을 다른 목록으로 옮기는 모든 구현이 O(1)인 것은 아니다. 길이 카운터 갱신을 위해 구간 원소 수를 세거나, 각 노드의 owner를 새 목록으로 바꾸거나, 할당자 호환성을 확인해야 할 수 있다. 링크를 몇 개 바꾼다는 설명만으로 전체 API 비용을 결정하지 않는다.
이 문서의 DList에 범위 splice를 추가하면서 owner를 정확히 유지하려면 이동한 노드들의 소속도 갱신해야 한다. 단일 노드의 같은 목록 내 이동은 그 문제가 없지만 서로 다른 목록 간 이동은 별도 계약이다. 센티널과 이동 위치가 구간 안에 있는지 같은 경계도 검토해야 한다.
C++ std::list에는 splice 같은 연산이 있지만 정확한 비용과 전제는 오버로드별 계약을 따른다. Rust LinkedList의 기능도 해당 표준 라이브러리 계약으로 확인한다. 교육용 그림과 실제 API를 동일한 것으로 취급하지 않는다.
LRU 캐시: 해시 조회와 연결 순서의 결합
LRU는 가장 오래 사용하지 않은 항목을 먼저 내보내는 교체 정책이다. 캐시에서 키로 항목을 찾는 일과 최근 사용 순서를 바꾸는 일은 서로 다른 요구다. 이중 연결 목록만 쓰면 키 검색이 느리고, 사전만 쓰면 가장 오래된 사용 순서를 별도로 관리해야 한다.
키→노드 사전을 두고 목록 앞을 가장 오래된 항목, 뒤를 가장 최근 항목으로 사용하면 두 역할을 결합할 수 있다. get 성공 시 해당 노드를 뒤로 이동하고 put으로 새 키를 넣으면 뒤에 추가한다. 용량을 초과하면 맨 앞 노드를 제거하고 사전에서도 삭제한다.
아래 구현은 dict의 평균적 조회·수정 비용을 가정할 때 get과 put의 구조 작업을 평균 O(1)로 설명할 수 있다. 해시 충돌의 최악 경우, 사용자 정의 해시 함수와 객체 비용까지 최악 O(1)이라고 주장하지 않는다. 용량 k에 대해 노드와 사전 항목은 O(k)다.
캐시에 없는 키는 KeyError이고 양의 항목 수 용량만 받는다. 바이트 용량, 만료 시간, 디스크 저장, 여러 스레드의 동시 접근은 포함하지 않았다. 단순 LRU의 자료구조 원리를 이해하기 위한 구현이다.
예제 코드
class LRUCache:
def __init__(self, capacity):
if capacity < 1:
raise ValueError('positive capacity required')
self.capacity = capacity
self.nodes = {}
self.order = DList()
def _touch(self, node):
if node.next is self.order.root:
return
node.prev.next = node.next
node.next.prev = node.prev
last = self.order.root.prev
node.prev, node.next = last, self.order.root
last.next = node
self.order.root.prev = node
def get(self, key):
node = self.nodes[key]
self._touch(node)
return node.value[1]
def put(self, key, value):
if key in self.nodes:
node = self.nodes[key]
node.value = (key, value)
self._touch(node)
return
node = self.order.insert_before(self.order.root, (key, value))
self.nodes[key] = node
if len(self.nodes) > self.capacity:
old_key, _ = self.order.remove(self.order.root.next)
del self.nodes[old_key]
cache = LRUCache(2)
cache.put('A', 10); cache.put('B', 20)
print(cache.get('A'))
cache.put('C', 30)
print(cache.order.values())
try:
cache.get('B')
except KeyError:
print('B evicted')
cache.put('A', 11)
print(cache.order.values())
실행 결과
10
[('A', 10), ('C', 30)]
B evicted
[('C', 30), ('A', 11)]LRU에서 링크와 사전을 함께 유지해야 한다
사전에서만 지우고 목록에 노드를 남기면 오래된 항목이 계속 순서를 차지한다. 목록에서만 지우고 사전에 남기면 이미 분리된 노드를 get이 다시 만질 수 있다. 두 구조는 같은 키 집합을 표현해야 하며 길이도 같아야 한다.
기존 키의 값을 바꿀 때 새 노드를 중복 추가하면 같은 키가 목록에 여러 번 생긴다. 위 구현은 기존 노드의 값을 바꾸고 그 노드를 뒤로 옮긴다. 현재 맨 뒤라면 이동할 필요가 없으므로 먼저 검사한다. 노드의 owner와 목록 길이는 같은 목록 안의 재배치에서 바뀌지 않는다.
항목 수 2인 캐시라도 값 하나가 큰 파일 버퍼면 메모리를 많이 보유할 수 있다. LRU 순서 정책과 메모리 예산은 다른 문제다. 바이트 용량이 필요하면 값의 크기와 공유 참조를 고려한 계량 및 여러 항목 퇴출 규칙이 필요하다.
순차 스캔으로 한 번만 읽는 키들이 몰려오면 자주 쓰던 항목까지 밀어낼 수 있다. LRU는 모든 접근 패턴에서 최적이라는 뜻이 아니다. 여기서는 정책의 성능 우열보다 사전과 연결 목록으로 그 정책을 정확하게 구현하는 방법에 초점을 맞춘다.
메모리 지역성과 실제 성능
연결 리스트는 뒤쪽 원소를 밀지 않아도 되지만 노드마다 링크와 관리 정보가 필요하다. 노드가 메모리에 흩어져 있으면 다음 주소를 읽은 뒤 그 위치를 다시 읽는 의존적 접근이 이어진다. 배열의 연속 접근과는 CPU 캐시·미리 읽기의 조건이 다르다.
작은 값 여러 개를 저장하는 상황에서 값보다 링크와 객체 헤더가 더 큰 비중을 차지할 수 있다. 구체적인 바이트 수는 언어, 포인터 크기, 런타임과 정렬 규칙에 따라 달라지므로 모든 연결 리스트가 원소당 특정 바이트를 쓴다고 고정하지 않는다.
“삭제가 많으니 연결 리스트가 무조건 빠르다”는 결론은 부족하다. 삭제 대상을 찾는 비용, 전체 순회 빈도, 노드 할당, 외부 참조 안정성 요구를 함께 보아야 한다. 연속 배열에서 블록을 이동하는 비용이 있어도 실제 워크로드에서는 더 빠를 수 있다.
성능 실험을 한다면 같은 연산 계약, 같은 입력 크기와 분포로 비교하고 준비·할당·출력 시간을 분리한다. 한 번의 짧은 측정을 복잡도 증명이나 모든 환경의 순위로 제시하지 않는다. 이 문서의 예제 검사는 정확성 검사이며 속도 우위를 측정한 벤치마크가 아니다.
언어별 이름과 실제 계약
Python list는 이름에 list가 있어도 여기서 구현한 노드 연결 목록과 같은 자료형이 아니다. 양끝 큐 연산이 필요하면 collections.deque 같은 표준 컨테이너를 먼저 검토할 수 있다. 알고리즘을 배우려고 Node를 직접 만드는 것과 일상 코드에서 가장 적절한 도구를 고르는 것은 구분한다.
Java LinkedList는 List와 Deque 인터페이스를 구현하는 이중 연결 구조다. 인덱스 연산은 가까운 끝에서 이동하므로 배열과 같은 상수 시간 임의 접근을 기대하면 안 된다. 구조 변경을 포함한 동시 사용은 별도 동기화가 필요하며 fail-fast 반복자를 동시성 보장으로 사용하지 않는다.
C++ std::list는 양방향 반복자를 제공하며 vector처럼 operator[]로 임의 접근하는 컨테이너가 아니다. 삽입·삭제, 반복자 유효성과 splice의 전제는 각 연산의 표준 계약을 확인한다. 값의 복사·이동·파괴가 예외를 던질 수 있는지도 실제 코드에서는 중요하다.
Rust LinkedList는 소유한 노드의 이중 연결 목록이다. 표준 문서 자체도 일반적인 선택으로 Vec나 VecDeque를 검토하도록 안내한다. 소유권과 빌림 규칙 안에서 API를 써야 하며 Python의 자유로운 next 변경 예제를 그대로 옮기는 방식은 맞지 않는다.
침입형 목록과 객체 수명
일반적인 설명은 값 바깥에 별도 노드가 있는 모습을 사용하지만 객체 자체에 연결 필드를 넣는 침입형 목록도 있다. Linux 커널의 list_head 방식은 실제 객체 안에 링크를 포함하는 대표적인 예다. 같은 객체가 여러 목록에 참여하려면 각 참여 관계에 대응하는 링크 필드를 구분할 수 있다.
별도 래퍼 노드가 필요 없는 장점이 있지만 객체의 수명과 목록의 관계를 코드가 정확히 관리해야 한다. 객체가 해제되었는데 목록에 링크가 남아 있으면 잘못된 메모리 접근으로 이어질 수 있다. 목록에서 떼는 것과 객체를 해제하는 것은 서로 다른 행위다.
다른 노드로 이동하기 전에 현재 노드를 해제하는 순회는 다음 위치를 잃을 수 있다. 삭제하면서 순회하는 전용 API나 다음 참조를 미리 보관하는 패턴이 필요하다. 다만 다음 노드도 다른 실행 주체가 삭제할 수 있다면 단순 보관만으로 동시 안전성이 생기지 않는다.
이 문서의 Python 예제는 커널 목록 구현이 아니며 참조를 안전하게 회수하는 RCU나 hazard pointer 같은 동시 자료구조 기법을 구현하지 않는다. 그 주제는 메모리 모델·동기화·회수 규칙을 별도로 학습해야 한다.
변경 중 순회와 소유권 계약
순회 중 현재 노드를 삭제하면 다음 노드로 어떻게 이동할지 정해야 한다. next를 None으로 지우는 구현에서 삭제 후 current=current.next를 하면 순회가 끝나 버린다. 삭제 전 다음 참조를 보관하거나, previous.next를 반복해서 검사하는 방식으로 계약에 맞게 작성한다.
값이 가변 객체일 때 노드 복사와 값 복사도 다르다. 새 Node들을 만들면서 같은 value 객체를 넣으면 링크 구조는 독립적이어도 값의 변경은 공유된다. 완전한 독립 복제가 필요하면 값의 깊은 복사 가능성, 순환 참조와 사용자 정의 복사 규칙까지 고려한다.
반복자가 유지되는지 여부는 언어와 컨테이너 연산별로 다르다. 일부 연결 컨테이너에서 다른 노드 삽입이 기존 참조를 유지하더라도 제거한 노드의 참조까지 유효하다는 뜻은 아니다. “연결 리스트는 포인터가 안정적”이라는 한 문장으로 모든 연산을 설명하지 않는다.
연결 변경 두세 줄이 원자적으로 실행되는 것도 아니다. 다른 스레드가 그 중간 상태를 읽을 수 있다면 잠금이나 전문적인 동시 알고리즘이 필요하다. 다음 검증은 단일 스레드에서 구조의 순서·연결 관계를 검사한 것으로 범위를 제한한다.
큐와 이중 연결 구조의 상태 대조 검사
아래 검사는 LinkedQueue를 deque와, DList를 Python 목록과 비교한다. 고정 시드의 3,000단계 동안 삽입·삭제를 섞고 매 단계 결과 순서와 크기를 검사한다. DList는 반환된 노드 참조를 별도 목록에 보관해 임의 위치 삽입과 알려진 노드 삭제를 수행한다.
정방향만 검사하면 prev 갱신 누락을 놓칠 수 있으므로 역방향 값도 비교한다. root부터 실제 링크를 따라가며 next.prev와 prev.next의 양방향 관계를 확인하고 노드 수가 size와 일치하는지도 확인한다.
테스트의 참조 목록에서 위치를 선택하는 비용은 검증 도구의 비용이다. 이 비용을 실제 DList.insert_before가 인덱스를 검색하는 것으로 해석하지 않는다. 테스트는 유효한 노드 참조를 이미 얻은 상태의 연산을 비교한다.
고정 난수 검사는 모든 가능한 연산열의 증명은 아니지만 빈 상태, 재사용, 중간 수정과 앞뒤 연결 갱신 오류를 드러내는 데 유용하다. 더미 삭제·다른 목록 노드·중복 삭제 같은 잘못된 입력도 별도로 검사한다.
예제 코드
from collections import deque
from random import Random
rng = Random(47)
q, expected_q = LinkedQueue(), deque()
d, handles, expected = DList(), [], []
for _ in range(3000):
if not expected_q or rng.randrange(2):
value = rng.choice([None, 0, 1, 9])
q.append(value); expected_q.append(value)
else:
assert q.popleft() == expected_q.popleft()
assert values_of(q.head) == list(expected_q)
assert q.size == len(expected_q)
assert (q.tail is None) == (q.size == 0)
if q.tail is not None:
assert q.tail.next is None
if not handles or rng.randrange(2):
index = rng.randrange(len(handles) + 1)
value = rng.randrange(7)
position = handles[index] if index < len(handles) else d.root
handles.insert(index, d.insert_before(position, value))
expected.insert(index, value)
else:
index = rng.randrange(len(handles))
assert d.remove(handles.pop(index)) == expected.pop(index)
assert d.values() == expected
assert d.values(True) == expected[::-1]
assert d.size == len(expected)
node = d.root
for _ in range(d.size + 1):
assert node.next.prev is node and node.prev.next is node
node = node.next
assert node is d.root
for invalid in [d.root, DList().root, DNode('unused')]:
try:
d.remove(invalid)
except ValueError:
pass
else:
raise AssertionError('invalid removal accepted')
print('queue 3000; doubly linked 3000; invalid removals 3')
실행 결과
queue 3000; doubly linked 3000; invalid removals 3역순·삭제·순환·병합의 독립 대조
역순과 값 삭제는 값 0,1,2의 길이 0부터 6까지 모든 배열로 만든 목록을 검사한다. 기준 결과는 Python 시퀀스 역순과 조건 필터다. 빈 입력, 모두 같은 값, 연속 삭제와 양끝 삭제가 모두 포함된다.
순환 검사는 길이 0부터 10까지 직선 목록을 만들고, 마지막 노드를 각 가능한 위치로 연결하거나 그대로 None으로 둔다. 기대 입구 노드를 직접 알고 있으므로 값이 아니라 is로 비교한다. 이 범위에서 66개의 구조를 검사한다.
병합은 0,1,2로 만들 수 있는 길이 0부터 4까지의 모든 비감소 시퀀스 쌍을 만든다. 35개 시퀀스의 모든 쌍 1,225개를 비교하며 입력마다 새 노드를 만들어 이전 병합의 파괴적 변경이 다음 테스트에 섞이지 않게 한다.
테스트가 통과한다는 사실과 알고리즘의 일반 증명은 다르다. 역순의 부분목록 불변식, 병합의 최소 앞 원소 선택과 순환 포인터의 거리 관계가 정확성의 근거이며 작은 전수 대조는 실제 구현의 실수를 찾는 보조 수단이다.
예제 코드
from itertools import product, combinations_with_replacement
sequence_cases = 0
for length in range(7):
for values in product(range(3), repeat=length):
assert values_of(reverse_links(build(values))) == list(values[::-1])
for target in range(3):
assert values_of(remove_all(build(values), target)) == [x for x in values if x != target]
sequence_cases += 1
cycle_cases = 0
for length in range(11):
for entry in range(-1, length):
nodes = [Node(0) for _ in range(length)]
for a, b in zip(nodes, nodes[1:]):
a.next = b
if entry >= 0:
nodes[-1].next = nodes[entry]
head = nodes[0] if nodes else None
expected = nodes[entry] if entry >= 0 else None
assert cycle_entry(head) is expected
cycle_cases += 1
sequences = [x for n in range(5) for x in combinations_with_replacement(range(3), n)]
merge_cases = 0
for left in sequences:
for right in sequences:
assert values_of(merge_sorted(build(left), build(right))) == sorted(left + right)
merge_cases += 1
print(sequence_cases, cycle_cases, merge_cases)
실행 결과
1093 66 1225LRU 캐시를 OrderedDict 기준 모델과 비교하기
OrderedDict는 키를 끝으로 이동하고 오래된 항목을 꺼내는 API가 있으므로 LRU의 기준 모델로 사용할 수 있다. 아래는 용량 1,2,5에서 각각 1,000번의 put/get을 실행한다. 키는 작은 범위에서 반복하여 갱신·적중·실패·퇴출이 자주 발생하게 한다.
get 실패가 났을 때는 양쪽 모두 키가 없어야 하며 성공하면 같은 값을 반환하고 같은 최근 사용 순서를 가져야 한다. put은 기존 키를 갱신하거나 새 키를 넣고 용량을 넘으면 가장 오래된 항목을 지운다.
매 단계 키 집합, 값과 순서, 목록 크기를 비교한다. “같은 값을 반환했다”만 확인하면 캐시의 순서 오류가 다음 퇴출에서 드러날 때까지 놓칠 수 있으므로 내부 정책의 관찰 가능한 결과까지 대조한다.
이 검사는 3,000회의 단일 스레드 연산에서 정책과 자료구조가 일치하는지 확인한다. 메모리 부족, 악의적인 사용자 정의 해시 객체, 동시 요청과 만료 시간 처리는 대상이 아니다. 운영 캐시에 필요한 별도 기능을 구현했다고 주장하지 않는다.
예제 코드
from collections import OrderedDict
from random import Random
rng = Random(51)
checks = 0
for capacity in [1, 2, 5]:
actual = LRUCache(capacity)
expected = OrderedDict()
for _ in range(1000):
key = rng.randrange(8)
if rng.randrange(2):
value = rng.randrange(100)
actual.put(key, value)
expected[key] = value
expected.move_to_end(key)
if len(expected) > capacity:
expected.popitem(last=False)
elif key in expected:
assert actual.get(key) == expected[key]
expected.move_to_end(key)
else:
try:
actual.get(key)
except KeyError:
pass
else:
raise AssertionError('missing key accepted')
assert actual.order.values() == list(expected.items())
assert set(actual.nodes) == set(expected)
assert actual.order.size == len(expected)
checks += 1
print(checks)
실행 결과
3000선택 기준과 이어서 학습할 주제
연결 리스트가 적합한지 판단하려면 위치를 어떻게 얻는지부터 확인한다. 이미 노드 참조를 보유하고 그 주변의 삽입·삭제·이동이 핵심인지, 매번 인덱스로 조회하거나 전체를 순회하는지에 따라 결과가 달라진다. 노드 참조 안정성이 실제 요구사항인지도 확인한다.
단일 연결은 링크가 적지만 이전 위치를 알기 어렵고, 이중 연결은 양방향 이동과 알려진 노드 삭제가 편리한 대신 링크와 불변식이 늘어난다. 센티널은 경계 코드를 단순화하지만 의도된 원형 구조의 종료 조건을 정확히 지켜야 한다.
직접 구현할 때는 빈 상태·원소 하나·양끝 수정·중복 값·삭제 후 재사용을 먼저 검증한다. 값, 노드 정체성, 소속과 소유권을 구분하고 기준 컨테이너와 연산열을 대조하면 눈으로 놓치기 쉬운 연결 오류를 찾는 데 도움이 된다.
학습은 동적 배열과 덱의 비용 비교, 해시 테이블과 결합한 LRU, 병합 정렬과 반복자 설계로 이어질 수 있다. 연결 리스트를 외운다는 것은 화살표를 그리는 데서 끝나지 않고 어떤 링크가 언제 바뀌며 어떤 참조가 계속 유효한지 설명할 수 있다는 뜻이다.