[leetcode] LRU Cache

https://leetcode.com/problems/lru-cache/

 

기본적인 전략은 값을 리스트 형태로 저장하고 PUT 또는 GET을 실행할 때마다 해당 값을 맨 앞으로 옮기고 ( 리스트의 앞에 있을수록 가장 최근의 사용한 값을 의미), 만약 리스트의 노드 수가 capacity를 넘으면 마지막 노드를 제거하여 capacity를 유지한다.  노드의 위치를 변경하기 위해서는 ArrayList보다, Linked List가 적합하고 노드의 앞뒤 탐색을 위해 Double LinkedList를 쓰기로 한다. 그리고 실행 시 O(1)의 시간 복잡도를 요구하고 있기 때문에 Map을 활용하여 값을 탐색하기로 한다. (만약 Map없이 Linked List만으로 구현을 하게되면 시간 복잡도는 O(N)이 된다.)

 

GET

• Map의 값이 없다면 바로 -1 리턴.
• 값이 존재하면 노드를 HEAD로 이동.

// 노드를 리스트로부터 제거
node.prev.next = node.next  // Previous ======> Next Node        
node.next.prev = node.prev  // Previous <====== Next Node

// 노드를 헤더 다음으로 이동
node.prev = this.head       // Head <======= Node
node.next = this.head.next  // Node =======> Next 
this.head.next.prev = node  // Node <======= Next        
this.head.next = node       // Head =======> Node

 

PUT

• Map에 값이 있는지 조회.
• 값이 없으면 새 노드를 HEAD로 위치. ( Map에 노드를 추가 )

// 새로운 노드를 생성
const newNode = { key: key, value : value, prev: null, next: null }
this.map.set(key,newNode)

// HEAD로 위치
newNode.prev = this.head       // Head     <======== New Node
newNode.next = this.head.next  // New Node ========> Next Node
this.head.next.prev = newNode  // New Node <======== Next Node
this.head.next = newNode       // Head     ========> New Node

• 리스트의 길이가 capacity를 넘으면 TAIL 노드를 제거. ( Map에서 노드 제거 )

// Tail 노드 삭제
const lastNode = this.tail.prev
node.prev.next = node.next  // Previous ======> Tail
node.next.prev = node.prev  // Previous <====== Tail

this.map.delete(lastNode.key)

 

전체 코드

var LRUCache = function(capacity) {
    this.size = capacity
    this.map = new Map()
    
    this.head = { prev: null, next: null, value: 'head' }
    this.tail = { prev: null, next: null, value:'tail' }
    this.head.next = this.tail
    this.tail.prev = this.head
};

LRUCache.prototype.get = function(key) {
    
    
    const node = this.map.get(key)
    
    if(!node) return -1
    
    node.prev.next = node.next
    node.next.prev = node.prev
    
    node.prev = this.head     
    node.next = this.head.next

    this.head.next.prev = node
    this.head.next = node
    
    return node.value
};

LRUCache.prototype.put = function(key, value) {
    
    const node = this.map.get(key)
    
    if(!node) {
        
        const newNode = { key: key, value : value, prev: null, next: null }
        this.map.set(key,newNode)
        
        newNode.prev = this.head
        newNode.next = this.head.next
        
        this.head.next.prev = newNode
        this.head.next = newNode
        
        if( this.map.size > this.size ) {
            
            const lastNode = this.tail.prev
            
            lastNode.prev.next = lastNode.next
            lastNode.next.prev = lastNode.prev
            
            this.map.delete(lastNode.key)
        }
    }else {        
        node.value = value
        
        node.prev.next = node.next
        node.next.prev = node.prev
        
        node.prev = this.head     
        node.next = this.head.next
        
        this.head.next.prev = node
        this.head.next = node
    }
};