연결 리스트의 구조와 선택 기준
연결 리스트의 노드·포인터 구조, 배열과의 성능 차이, 동시성 제어와 LRU 캐시·커널 큐 활용 시 선택 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
연결을 바꿔 데이터를 다루는 자료구조
연결 리스트는 노드를 동적으로 할당하고 포인터로 이어 붙이는 선형 자료구조다. 각 노드는 데이터 필드와 다음 노드의 참조를 가지며, 구조에 따라 이전 노드 참조도 함께 둔다.
메모리에서 연속된 영역을 확보할 필요가 없고 크기를 가변적으로 늘릴 수 있다. 반대로 인덱스로 바로 찾아가는 랜덤 액세스는 제공하지 않으므로, 접근은 앞에서부터 따라가는 순차 탐색이 중심이 된다.
단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 대표적이다. 양방향 탐색이 필요한지, 순환 작업을 다루는지에 따라 형태를 고른다.
노드와 링크를 다룰 때 생기는 조건들
노드는 데이터 필드와 next[, prev] 링크 필드로 구성된다. 64-bit 환경에서는 포인터 1개당 일반적으로 8바이트 오버헤드가 발생한다.
head와 tail을 관리하면 앞과 뒤에서 O(1) 삽입·삭제 경로를 만들 수 있다. 다만 빈 리스트, 노드가 하나뿐인 리스트, 여러 노드가 연결된 리스트는 각각 경계 처리가 필요하다. 삽입 시에는 이전 노드를 찾고 새 노드를 할당한 뒤 링크를 재배치하며, head와 tail 변경 여부를 반영한다. 인덱스 범위 초과와 메모리 부족도 처리 대상이다.
삭제는 대상 이전 노드를 확인한 뒤 링크가 대상 노드를 건너뛰도록 바꾼다. 이후 가비지 컬렉션에 맡기거나 명시적으로 해제한다. 반복자 무효화와 동시 수정 위험도 함께 관리해야 한다.
단일·이중·원형 구조의 차이
단일 연결 리스트는 포인터 오버헤드를 최소화하면서 단방향 순회에 맞춘 구조다. 역방향 탐색은 할 수 없다.
이중 연결 리스트는 prev 포인터를 추가해 양방향 탐색을 제공한다. 노드 포인터를 보유하고 있다면 O(1) 삭제도 가능하지만, 포인터 2개를 유지하는 비용이 따른다.
원형 연결 리스트는 마지막 노드가 첫 노드를 가리킨다. 라운드로빈 스케줄링이나 순환 버퍼 처리처럼 끝없이 이어지는 흐름에 맞는다.
배열과 비교할 때 드러나는 특성
| 핵심 지표 | 배열(Array) | 연결 리스트(Linked List) |
|---|---|---|
| 성능 | 임의 접근 O(1), 중간 삽입/삭제 O(n) | 임의 접근 O(n), 노드 포인터 보유 시 삽입/삭제 O(1) |
| 확장성 | 크기 변경 시 재할당/복사 비용 발생 | 노드 단위 증감으로 점진 확장 용이 |
| 일관성 | 인덱스 기반 접근 일관성 우수 | 포인터 무결성 필요, 경계/널 체크 필수 |
| 안정성 | 캐시 로컬리티 우수, 단편화 낮음 | 메모리 단편화 가능, 캐시 미스 증가 가능 |
| 운영 편의 | 단순 구조, 디버깅 용이 | 포인터 버그/유실 노드 추적 난도 상승 |
분산 할당 방식은 대용량 데이터에서 전체 재배치를 피할 수 있게 한다. 그러나 노드가 비연속적으로 배치되므로 캐시 로컬리티가 떨어지고, 포인터 추적 비용과 브랜치 미스가 늘 수 있다. 순차 순회 성능은 배열보다 불리한 경향이 있다.
위치 삽입에서 확인할 흐름
캐시와 커널 큐에서의 활용
LRU 캐시는 HashMap과 Doubly Linked List를 결합해 O(1) 조회·삽입·퇴출을 구현한다. 최근 사용한 항목을 앞쪽으로 옮기고, 용량을 넘으면 꼬리 노드를 제거한다. 캐시 미스가 빈번한 환경에서는 배열의 재배치 비용을 피하는 방식이 된다.
패킷 큐, 작업 스케줄러, 파일시스템 디렉터리 엔트리에서는 원형 또는 침투형(Intrusive) 리스트를 활용한다. 메모리 파편화에 대응하면서 상수 시간 연산을 보장하는 목적이다. 잠금 경합을 줄이기 위해 per-CPU 리스트나 RCU 기반 읽기 최적화 패턴을 적용할 수 있다.
가변 길이 버퍼 체인으로 구성하는 실시간 스트리밍 파이프라인에도 맞는다. 노드를 교체하는 방식으로 지연을 최소화하고 백프레셔를 제어하기 쉽다.
Python으로 보는 단일 연결 리스트
# 환경: Python 3.10+
# 목적: 단일 연결 리스트의 기본 연산 구현 (삽입, 삭제, 탐색)
from __future__ import annotations
from typing import Optional, Iterator, Any
class Node:
__slots__ = ("value", "next")
def __init__(self, value: Any, next: Optional["Node"] = None):
self.value = value
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head: Optional[Node] = None
def insert_at(self, index: int, value: Any) -> None:
if index < 0:
raise IndexError("negative index")
if index == 0:
self.head = Node(value, self.head)
return
prev = self.head
k = 0
while prev and k < index - 1:
prev = prev.next
k += 1
if prev is None:
raise IndexError("index out of range")
prev.next = Node(value, prev.next)
def delete_value(self, value: Any) -> bool:
prev = None
cur = self.head
while cur:
if cur.value == value:
if prev is None:
self.head = cur.next
else:
prev.next = cur.next
return True
prev, cur = cur, cur.next
return False
def find(self, value: Any) -> Optional[Node]:
cur = self.head
while cur:
if cur.value == value:
return cur
cur = cur.next
return None
def __iter__(self) -> Iterator[Any]:
cur = self.head
while cur:
yield cur.value
cur = cur.next
# 사용 예
lst = SinglyLinkedList()
lst.insert_at(0, "A")
lst.insert_at(1, "B")
lst.insert_at(1, "X")
lst.delete_value("A")
print(list(lst)) # ['X', 'B']성능과 메모리 비용을 함께 계산한다
노드 참조를 보유한 상태라면 임의 위치 삽입과 삭제는 O(1)로 처리할 수 있지만, 위치 탐색에는 O(n)이 수반된다. 중간 삽입과 삭제가 대량으로 발생하는 경우 전체 비용을 줄일 수 있다.
메모리 측면에서는 64-bit 기준 포인터 1개당 8바이트가 들고, Doubly 구조는 최소 16바이트의 포인터 오버헤드를 가진다. 정수 4바이트를 저장하는 n개 노드라면 Singly 기준 최소 오버헤드는 ≈ 8n바이트, Doubly 기준은 ≈ 16n바이트이며 언어별 객체 헤더가 추가될 수 있다.
재할당을 피하면 다운타임과 스톨을 줄이고, 구조 변경 시 데이터 복사도 최소화할 수 있다. GC 환경에서는 연결 해제만으로 회수 경로가 단순해지며, 수동 메모리 환경에서는 해제 책임을 명확히 나눠야 한다.
동시성 환경에서는 링크 갱신만으로 끝나지 않는다
Mutex나 스핀락으로 구간을 보호하면 일관성을 유지할 수 있다. 단일 리스트 전체를 잠그는 방식보다 노드 단위로 락을 세분화하면 확장성을 높일 수 있다.
CAS 기반 lock-free 기법도 적용할 수 있다. 이 경우 ABA 문제를 막기 위한 태깅 포인터와 Hazard Pointer, RCU 같은 안전한 메모리 재사용 기법을 병행해야 한다.
연결 리스트는 중간 삽입·삭제가 빈번하고 크기 변화가 큰 워크로드, 큐·캐시·스케줄링 같은 스트리밍 패턴에 적합하다. 고성능 순차 처리나 벡터화가 중요한 워크로드라면 배열이나 연속 컨테이너를 우선 검토하는 편이 맞다.