Ch.5 연결 리스트

이중 연결리스트 & LRU Cache

이중 연결리스트(Doubly Linked List)의 구조와 장점을 이해한다HashMap + DLL로 O(1) LRU Cache를 설계한다

뒤로 갈 수 없으면 불편하다

단일 연결리스트는 next만 있어서 앞으로만 갈 수 있습니다. 이중 연결리스트는 prev도 있어서 양방향 이동이 가능합니다. 이 구조가 LRU Cache의 핵심입니다.

가장 오래 안 쓴 데이터를 O(1)에 찾아 삭제하려면?

HashMap으로 O(1) 조회 + DLL로 O(1) 삽입/삭제 = LRU Cache의 완성입니다.

lightbulb

핵심 개념

Doubly Linked List

각 노드가 prev와 next 두 포인터를 가지는 리스트

LRU Cache

Least Recently Used — 가장 오래 안 쓴 데이터를 제거하는 캐시

article

핵심 내용

이중 연결리스트는 prev + next 두 방향의 포인터를 가집니다

class DLLNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

이중 연결리스트 장점 O(1) 삭제: 노드 자체를 알면 prev/next 연결만 바꿔서 삭제 양방향 순회: 앞뒤로 자유롭게 이동 가능

캐시가 꽉 찼을 때 가장 오래 안 쓴 데이터를 삭제합니다

최근 사용한 데이터는 앞으로, 오래된 데이터는 뒤로 밀립니다

LRU에 필요한 연산: get O(1) + put O(1) + 삭제 O(1) → HashMap + DLL!

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # key → DLLNode
        # dummy head & tail
        self.head = DLLNode()
        self.tail = DLLNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)  # 최근 사용
        return node.val
    
    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = DLLNode(key, value)
        self.cache[key] = node
        self._add_to_front(node)
        if len(self.cache) > self.cap:
            lru = self.tail.prev  # 가장 오래된 노드
            self._remove(lru)
            del self.cache[lru.key]

Python에는 OrderedDict가 있어서 LRU를 간결하게 구현할 수 있습니다

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.cap = capacity
    
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # 최근 사용
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # 가장 오래된 것 삭제

면접에서는 HashMap + DLL 직접 구현을 요구합니다. OrderedDict는 '더 간단한 방법도 있다'고 언급만!

LRU Cache가 실무에서 어떻게 쓰이는지 봅시다

LRU Cache 실무 활용 웹 브라우저: 최근 방문 페이지 캐싱 DB 쿼리 캐시: 자주 쓰는 쿼리 결과 저장 CDN: 인기 콘텐츠 우선 캐싱 운영체제: 페이지 교체 알고리즘

면접 팁: LRU를 설명할 때 실무 사례를 하나 언급하면 가산점!

# LRU Cache 연산 정리
# put(key, val): O(1)
#   1. cache에 key 있으면 → remove(기존 노드)
#   2. 새 노드 생성 → add_to_front
#   3. 용량 초과 → tail.prev 삭제
#
# get(key): O(1)
#   1. cache에 없으면 → return -1
#   2. remove(노드) → add_to_front → return val

LRU Cache에서 HashMap의 역할은?

이중 연결리스트에서 특정 노드를 삭제하는 시간 복잡도는 O(1)이다 (노드 참조가 주어졌을 때)

LRU Cache는 ___과 DLL을 조합하여 O(1) 연산을 달성한다

DLL & LRU Cache 마스터!

edit_note

정리 노트

이중 연결리스트 & LRU Cache

이중 연결리스트

구조: 각 노드에 prev + next 포인터
장점: 노드 참조가 있으면 O(1) 삭제

LRU Cache

자료구조: HashMap + DLL
get: HashMap 조회 → DLL 앞으로 이동 → O(1)
put: HashMap 저장 → DLL 앞에 삽입, 초과 시 tail 삭제 → O(1)

★

LRU Cache는 FAANG 면접 빈출 Top 5 문제! 구현을 외울 게 아니라 원리를 이해하자.

image

시각 자료

다이어그램: ds-d39

다이어그램: ds-d41

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작