체크리스트

Cache를 적용하기전 미리 결정한 체크리스트는 다음과 같습니다.

1. 캐시 사이즈 설정: 캐시의 사이즈는 미리 정의할 수 있어야 하며, 이를 통해 캐시의 용량 관리하기
2. 데이터 추가 시 오래된 노드 삭제: 새로운 데이터를 캐시에 담을 시, 캐시 사이즈를 벗어나게 되면 가장 오래된 노드 삭제하기
3. 링크드 리스트와 O(1) 탐색 적용: ****데이터의 순서를 기억하기 위해 링크드 리스트를 사용하되, 탐색 시에는 시간 복잡도 O(1)을 달성하기 위해 해시맵 사용하기
4. get 요청 시 최신 노드 이동: get 요청이 들어올 경우, 해당 노드를 가장 최신으로 이동하기

적용 내역

캐싱을 적용하기 위해 두 개의 주요 클래스를 사용하였습니다: LRUNode와 LRUCache.

LRUNode

class LRUNode {
  key: string;
  value: any;
  prev: LRUNode | null;
  next: LRUNode | null;

  constructor(key: string, value: any) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

• LRUNode는 캐시에 저장되는 각 데이터 항목을 나타내며, 각 노드는 key, value, prev(이전 노드), next(다음 노드)를 속성으로 가집니다.

LRUCache

export default class LRUCache {
  capacity: number;
  hashmap: { [key: string]: LRUNode };
  head: LRUNode;
  tail: LRUNode;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.hashmap = {};
    this.head = new LRUNode('0', 0);
    this.tail = new LRUNode('0', 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  ...
}

• LRUCache는 실제 캐시를 나타내며, head와 tail로 이루어진 더블 링크드 리스트와 hashmap으로 이루어져 있습니다.

핵심 메서드: get, put, delete