[Swift] LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

풀러가기

문제 이해

삽입/삭제가 빈번하기 때문에 doubly linked list 자료구조를 가져간다.
중간에 저장된 데이터도 접근해야 하기 때문에 HashMap 을 사용하여 O(1)로 만들어야 한다.

코드

class LRUCache {
  class CacheItem {
    let key: Int
    var value: Int
    var prev: CacheItem?
    var next: CacheItem?
    
    init(key: Int, value: Int) {
      self.key = key
      self.value = value
    }
  }
  
  var head: CacheItem?
  var tail: CacheItem?
  let capacity: Int
  var map: [Int: CacheItem] = [:]
  init(_ capacity: Int) {
    self.capacity = capacity
  }
  
  func get(_ key: Int) -> Int {
    guard map.contains(where: { $0.key == key }) else { return -1 }
    
    let current = map[key]
    
    if current !== head {
      if current === tail {
        // move tail to one in front
        tail = tail?.prev
      }
      
      // move current to head
      if current?.prev != nil {
        current?.prev?.next = current?.next
      }
      if current?.next != nil {
        current?.next?.prev = current?.prev
      }
      current?.next = head
      head?.prev = current
      current?.prev = nil
      head = current
    }
    
    return current!.value
  }
  
  func put(_ key: Int, _ value: Int) {
    if get(key) == -1 {
      // insert
      let current = CacheItem(key: key, value: value)
      if head == nil {
        head = current
        tail = current
      } else {
        current.next = head
        head?.prev = current
        head = current
      }
      
      map[key] = current
      
      if let tail = tail, map.count > capacity {
        map[tail.key] = nil
        tail.prev?.next = nil
        self.tail = tail.prev
      }
    } else {
      // update
      map[key]?.value = value
    }
  }
}

풀이

-

다른 분의 멋진 코드

class Node{
    var pre: Node?
    var next: Node?
    var key: Int
    var value: Int
    init(_ key: Int, _ value: Int){
        self.key = key
        self.value = value
    }
}

class LRUCache {
    var capacity: Int
    var head: Node?
    var tail: Node?
    var count: Int
    var map: [Int : Node]
    init(_ capacity: Int) {
        self.capacity = capacity
        head = Node(-1, -1)
        tail = Node(-1, -1)
        head?.next = tail
        tail?.pre = head
        count = 0
        map = [Int: Node]()
    }
    
    func moveToHead(_ node: Node?){
        node?.next = head?.next
        head?.next?.pre = node
        node?.pre = head
        head?.next = node
    }
    
    func deleteNode(_ node: Node?){
        node?.next?.pre = node?.pre
        node?.pre?.next = node?.next
    }
    
    func get(_ key: Int) -> Int {
        if(map[key] == nil){
            return -1
        }
        var node = map[key]
        deleteNode(node)
        moveToHead(node)
        return node!.value
    }
    
    func put(_ key: Int, _ value: Int) {
        
        if(map[key] != nil){
            var node = map[key]
            node?.value = value
            deleteNode(node)
            moveToHead(node)
            return
        }
        
        var node = Node(key, value)
        map[key] = node
        if(count == capacity){
            var delete = tail?.pre
            deleteNode(delete)
            map[delete!.key] = nil
            count -= 1
        }
        moveToHead(node)
        count+=1
      
    }
}

잘 배웠습니다.

-