HashMap과 Doubly Linked List 결합을 통한 O(1) 시간 복잡도의 LRU Cache 구현

Context

백엔드 데이터베이스의 물리적 접근 속도 한계로 인한 성능 병목 현상 발생. 한정된 Cache 메모리 자원 내에서 효율적인 데이터 유지 및 삭제 전략이 필요한 상황.

Technical Solution

• 데이터 조회 속도 최적화를 위해 Key-Value 쌍을 저장하는 HashMap 도입
• 데이터의 시간적 순서를 추적하고 빈번한 위치 변경을 지원하는 Doubly Linked List 구조 설계
• HashMap의 빠른 Lookup 기능과 Linked List의 순서 제어 기능을 결합한 하이브리드 아키텍처 구축
• 데이터 접근 시 해당 노드를 즉시 Head 위치로 이동시켜 Most Recently Used 상태 유지
• 메모리 임계치 도달 시 Tail 노드를 즉시 삭제하는 Eviction 정책을 통한 공간 확보
• 포인터 조작을 통한 노드 이동 및 삭제 로직 구현으로 모든 작업의 O(1) 시간 복잡도 달성