//
//  LRUCache.swift
//  LRUCache
//
//  Created by wangjin on 2021/10/27.
//


//LRU（ Least Recently Used 最近使用過數(shù)據(jù)）

//目的：計算機的緩存容量有限，如果緩存滿了就要刪除一些內(nèi)容，給新內(nèi)容騰位置，解決刪除哪些數(shù)據(jù)的算法
//算法核心：雙向鏈表和哈希表的結(jié)合體。是讓時間復雜度為 O(1)
//工作流程：緩存淘汰策略
//大體思想：
//1.設(shè)置一個最大容量 capacity
//2.實現(xiàn)兩個接口 一個是 put(key,val)方法 存入鍵值 一個是get(key) 方法取出對應val
//3.cache 中查找鍵是否已存在；如果容量滿了要刪除最后一個數(shù)據(jù)；每次訪問還要把數(shù)據(jù)插入到隊頭。


///代碼 步驟：
///1.創(chuàng)建一個雙鏈表節(jié)點
 class Node {
    /// 存時候的key string類型
     var key : String?
    /// 存的值 任意值
     var val : Any?
    /// 下一個節(jié)點
     var next : Node?
    /// 上一個節(jié)點
     var prev : Node?
    
    /// 節(jié)點初始化 傳入 key 和val
    init(key:String?,val:Any?) {
        self.key = key
        self.val = val
    }
}

/// 創(chuàng)建一個雙鏈表
 class DoubleList {
    /// 頭尾虛節(jié)點
    /// 頭節(jié)點
    var head : Node?
    /// 尾節(jié)點
    var tail : Node?
    /// 鏈表長度
    var size : Int = 0
    
    init() {
        head = Node(key: nil, val: nil)
        tail = Node(key: nil, val: nil)
        size = 0
        
        /// 頭指尾 尾指頭 循環(huán)起來
        head?.next = tail
        tail?.next = head
        
    }
    
    /// 鏈表頭部添加節(jié)點 node
    func addFirst(node:Node) {
        
        /// 這個得自己畫圖
        /// 當前節(jié)點下一個 指向 頭節(jié)點下一個
        /// 當前節(jié)點上一個 指向頭節(jié)點
        /// 頭節(jié)點下一個節(jié)點的上一個節(jié)點 指向當前節(jié)點
        /// 頭節(jié)點下一個節(jié)點 指向當前節(jié)點

        node.next = head?.next
        node.prev = head
        head?.next?.prev = node
        head?.next = node
        /// 元素數(shù)加1
        size += 1
        
    }
    
    /// 刪除鏈表中某個節(jié)點 node 必須有節(jié)點
    func removeNode(node:Node){
        ///這個自己畫
        node.prev?.next = node.next
        node.next?.prev = node.prev
        /// 元素減1
        size -= 1
        
    }
    
    /// 刪除最后一個節(jié)點 并返回該節(jié)點
    func removeLast() -> Node? {
        if size == 0 {
            return nil
        }
        let last = tail?.prev
        removeNode(node:last!)
        return last
    }
    
}



public class LRUCache {
    
    /// 哈希map
   private var map : [String? : Node?]
    /// 雙向鏈表
   private var doubleList : DoubleList
    /// 最大容量 傳入
   private var capacity : Int
    
    init(capacity : Int) {
        self.capacity = capacity
        self.map = [:]
        self.doubleList = DoubleList.init()
    }
    
    
   public func get(key : String) -> Any? {

        if map[key] == nil {
            return nil
        }
        
        let val = (map[key] as? Node)?.val
        //這里是為了把數(shù)據(jù)提前
        put(key: key, val: val)
        return val
    }
    
  public  func put(key:String,val:Any?) {
        
        let node = Node.init(key: key, val: val)
        if map[key] != nil {
            //刪除舊節(jié)點
            doubleList.removeNode(node: (map[key] as? Node)!)
            //插入新節(jié)點
            doubleList.addFirst(node: node)
            //更新map數(shù)據(jù)
            map[key] = node
        }else {
            
            if capacity == doubleList.size {
                //刪除最后一個節(jié)點
                guard let last = doubleList.removeLast() else {
                    return
                }
                map.removeValue(forKey: last.key)
            }
            // 添加到頭部
            doubleList.addFirst(node: node)
            //更新map
            map[key] = node
        }
    }
    
}

下面是調(diào)用

import UIKit

class ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        // Do any additional setup after loading the view.
        
        let cache = LRUCache.init(capacity: 2)
        cache.put(key: "1", val: 1)
        cache.put(key: "2", val: 2)
        let val = cache.get(key: "1")
        print(val)
        cache.put(key: "3", val: 3)
       let val2 = cache.get(key: "2")
        print(val2)
        
    }


}

結(jié)果

image.png