2025.09.03 lru cache

 

LRU Cache (Part II- implementation)

 
구현 시 head와 tail에 더미 노드를 넣는다.
null로도 구현할 수 있는데, 예외 처리등이 들어가고 코드가 복잡해진다.
첫 노드를 넣을 때 head와 tail이 모두 동일 노드가 되고, 잘 처리하지 않으면 루프에 갇히게 된다.
 
이런 것을 처리하기보다 더미 노드를 넣어 버그를 줄일 수 있다. 이걸 sentinel node라고 부르더라.
고집하기보다 더 좋은 방향이 있다면 선택을 해야 한다.
 
linked list로 처리하면 헤드와 테일에 추가할 때 O(1)이 된다.
이 구조로 LRU를 알 수 있다.
linked list만으로는 값을 찾을 때 O(N)이 되므로 Map을 사용해 O(1)을 충족하도록 한다.
 
 
요구사항

• get으로 값을 가져올 수 있다. 그 값은 가장 최근 사용되 것이다.
• put으로 값을 넣을 수 있다. 수용할 수 있는 값을 벗어나면 가장 오래전에 사용한 값을 지운다.

 
 
 

GitHub - choigiseong/LRU: LRU cache