JavaScript LRU 캐시: Map과 이중 연결 리스트의 불변식

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

문제 상황과 API 계약

작은 지도 앱에서 최근 읽은 타일만 메모리에 남긴다고 합시다. 캐시가 가득 차면 가장 오래 사용하지 않은 항목을 버려야 합니다. 배열로 최근 사용 순서를 유지하면 중간 항목을 찾아 맨 앞으로 옮길 때 O(c)가 걸립니다. Map으로 노드를 바로 찾고 연결 리스트에서 이웃 포인터만 고치면 위치 이동에 필요한 탐색을 없앨 수 있습니다.

get(key)는 값을 반환하면서 해당 항목을 가장 최근 위치로 옮깁니다. 누락은 undefined이며 이 값은 저장할 수 없도록 예약했습니다. put(key,value)는 삽입 또는 교체이고 둘 다 최근 사용으로 취급합니다. keys()는 가장 최근부터 가장 오래된 순서의 스냅샷 배열을 반환합니다. get은 데이터를 읽는 듯 보여도 내부 순서를 변경합니다.

capacity는 항목 수 기준 0~1,000,000 정수입니다. 0이면 put은 아무것도 저장하지 않습니다. Map 키는 JavaScript Map의 동등성 규칙을 따르며 객체 키는 내용이 아니라 참조로 구분합니다. 예제와 창작 문제는 문자열 키를 써 이 차이를 피하지만 범용 클래스의 계약은 알아 두어야 합니다.

정확성을 지키는 불변식

head와 tail은 실제 데이터를 담지 않는 센티널입니다. head.next가 MRU, tail.prev가 LRU입니다. 비었을 때 head.next===tail, tail.prev===head입니다. 실제 노드마다 node.prev.next===node, node.next.prev===node가 유지되어야 어느 위치든 같은 두 줄로 제거할 수 있습니다.

Map의 각 값은 리스트에 정확히 한 번 등장하는 같은 노드 객체입니다. 리스트에서만 퇴출하면 Map에 오래된 항목이 남고, Map에서만 지우면 리스트 길이가 용량을 넘습니다. 따라서 퇴출은 detach와 map.delete를 같이 수행합니다.

기존 키를 put할 때 새 노드를 만들지 않습니다. old.value만 바꾸고 노드의 위치를 앞쪽으로 옮깁니다. 새로운 키를 넣을 때 가득 차 있으면 tail.prev를 먼저 퇴출한 뒤 새 노드를 넣습니다. 이렇게 동일 키 교체가 불필요한 다른 항목 퇴출을 일으키지 않습니다.

전체 구현과 실행

Node.js 24의 CommonJS 환경을 기준으로 합니다. 아래 전체 코드를 lru.cjs로 저장하고 파일이 있는 폴더에서 node lru.cjs를 실행하세요. 외부 패키지는 필요하지 않습니다. module.exports는 다른 파일에서 가져올 때 사용하며 require.main 조건 안의 호출은 직접 실행할 때만 작동합니다.

class LRUCache {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity < 0 || capacity > 1_000_000) {
      throw new RangeError('용량은 0~1,000,000 정수여야 합니다.');
    }
    this.capacity = capacity;
    this.map = new Map();
    this.head = { prev: null, next: null };
    this.tail = { prev: this.head, next: null };
    this.head.next = this.tail;
  }
  detach(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
  }
  attachFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.detach(node);
    this.attachFront(node);
    return node.value;
  }
  put(key, value) {
    if (value === undefined) throw new TypeError('undefined는 누락 표시로 예약합니다.');
    if (this.capacity === 0) return;
    const old = this.map.get(key);
    if (old) {
      old.value = value;
      this.detach(old);
      this.attachFront(old);
      return;
    }
    if (this.map.size === this.capacity) {
      const victim = this.tail.prev;
      this.detach(victim);
      this.map.delete(victim.key);
    }
    const node = { key, value, prev: null, next: null };
    this.map.set(key, node);
    this.attachFront(node);
  }
  keys() {
    const result = [];
    for (let node = this.head.next; node !== this.tail; node = node.next) result.push(node.key);
    return result;
  }
}

module.exports = { LRUCache };

if (require.main === module) {
  const c = new LRUCache(2);
  c.put('a', 1);
  c.put('b', 2);
  c.get('a');
  c.put('c', 3);
  console.log(JSON.stringify(c.keys()));
  console.log(c.get('b'));
}

직접 실행 출력:

["c","a"]
undefined

detach는 먼저 양쪽 이웃을 서로 연결한 다음 자신의 prev,next를 null로 만듭니다. attachFront는 head 바로 뒤의 네 참조를 이어 붙입니다. 센티널 덕분에 노드가 처음·중간·마지막인 경우를 나누지 않습니다. 이 두 메서드는 내부용이며 센티널이나 연결되지 않은 외부 객체를 전달하지 않습니다.

get에서 this.map.get(key)가 반환하는 값은 저장 payload가 아니라 노드입니다. 값 0이나 false를 저장해도 노드 객체는 존재하므로 정상 조회됩니다. undefined는 miss와 충돌하므로 put 초입에서 거부합니다.

예제의 출력 keys는 ["c","a"]이고 b 조회는 undefined입니다. keys 자체는 모든 노드를 훑는 O(c) 진단용 스냅샷입니다. 이를 매 요청마다 호출하면서 “캐시 요청 전체 O(1)”이라고 주장하면 반환 목록 생성 비용을 빠뜨리게 됩니다.

상태 변화 따라가기

복잡도와 적용하지 말아야 할 경우

Map 명세는 평균적으로 원소 수에 대해 선형보다 나은 접근을 요구하지만 특정 해시 구현이나 최악 O(1)을 보장하지 않습니다. 해시 테이블 모델에서는 조회는 기대 O(1), 재할당을 포함한 삽입은 보통 기대 상환 O(1)로 설명합니다. 해시 충돌이나 재할당이 있는 한 연산을 무조건 상수 시간이라고 단정하지 마세요.

퇴출된 노드는 Map과 리스트 양쪽에서 끊어 외부 참조가 없다면 가비지 컬렉션 대상이 됩니다. 실제 메모리가 바로 줄어드는 시점은 GC가 정합니다. value를 바꿀 때 옛 payload 참조는 캐시에서 떨어지지만 다른 곳이 참조하면 계속 남습니다. c개 객체라고 c바이트가 아니므로 대형 이미지 캐시에는 바이트 예산과 해제 정책이 따로 필요합니다.

TTL 만료, 동시 비동기 요청 중복 제거, 영속 저장, 스레드 안전성, 자원 dispose는 없습니다. 만료 시간 기준 퇴출이나 전체 항목의 단순 FIFO가 요구되는 상황에 LRU를 그대로 적용하면 정책 자체가 틀립니다. Map의 삽입 순서를 이용한 짧은 LRU도 가능하지만 이번 구현은 순서와 조회를 분리해 포인터 불변식을 학습하기 위한 선택입니다.

연습으로 확인하기

타일 요청마다 이미 캐시에 있었는지를 기록하고 마지막 사용 순서를 반환해 보세요. 같은 타일을 연속 요청하거나 용량을 0으로 바꿔도 정책을 일관되게 적용해야 합니다.

[창작 문제] 지도 타일의 재사용 기록

LeetCode 146 – LRU Cache — LRU 조회와 갱신을 연습하는 공식 문제입니다. 해당 문제의 누락 반환값과 용량 제약은 이 글의 undefined·용량 0 계약과 다릅니다.

공식 자료

공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.

• MDN Map: 키 비교와 접근 복잡도 요구
• LeetCode 146 – LRU Cache