從結(jié)構(gòu)上來看，雙向鏈表可以支持O(1)時間復(fù)雜度的情況下找到前驅(qū)結(jié)點，正是這樣的特點，使得雙向鏈表在某些情況下的插入、刪除操作比單鏈表更加高效。

我們已經(jīng)找到要刪除的結(jié)點，但是刪除某個結(jié)點q，需要其前驅(qū)結(jié)點，而單鏈表不支持直接獲得前驅(qū)結(jié)點，所以為了找到前驅(qū)結(jié)點，需要從頭開始遍歷鏈表，直到p<-next=q，說明p是q的前驅(qū)結(jié)點。對于雙向鏈表來說，這種情況就比較有優(yōu)勢。因為雙向鏈表已經(jīng)保存了前驅(qū)結(jié)點的指針，不需要像單鏈表那樣遍歷。單鏈表刪除操作需要O(n)的時間復(fù)雜度，而雙鏈表只需要O(1)的時間復(fù)雜度。

題目描述：

實現(xiàn) LRUCache 類：
LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
void set(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。當緩存容量達到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

示例：

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 該操作會使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

/* 4.設(shè)計LRU緩存結(jié)構(gòu)
 題目描述：
 
 實現(xiàn) LRUCache 類：
    LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
    int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。
    void set(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。當緩存容量達到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

 示例：

 輸入
 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 輸出
 [null, null, null, 1, null, -1, null, -1, 3, 4]

 解釋
 LRUCache lRUCache = new LRUCache(2);
 lRUCache.put(1, 1); // 緩存是 {1=1}
 lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
 lRUCache.get(1);    // 返回 1
 lRUCache.put(3, 3); // 該操作會使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
 lRUCache.get(2);    // 返回 -1 (未找到)
 lRUCache.put(4, 4); // 該操作會使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
 lRUCache.get(1);    // 返回 -1 (未找到)
 lRUCache.get(3);    // 返回 3
 lRUCache.get(4);    // 返回 4
 
 */

// 方法一：哈希表 + 雙向鏈表

// LRU 緩存算法的核心數(shù)據(jù)結(jié)構(gòu)就是哈希鏈表，雙向鏈表和哈希表的結(jié)合體。

// 雙鏈表: head -> 最常用node -> node -> 最不常用node -> tail

public class LRUCache {
   
    // 節(jié)點
    class DlinkNode {
        let key: Int
        var value: Int
        
        var prev: DlinkNode?
        var next: DlinkNode?
     
        init(_ key: Int, _ value: Int) {
            self.key = key
            self.value = value
        }
    }
    
    // 雙鏈表
    class DoubleLinkedList {
        // 偽頭部節(jié)點head， 偽尾部節(jié)點tail
        var head, tail : DlinkNode?
        // 鏈表元素數(shù) (不包含 頭尾的偽節(jié)點)
        var size: Int = 0
        init() {
            // 使用一個偽頭部（dummy head）和偽尾部（dummy tail）標記界限，這樣在添加節(jié)點和刪除節(jié)點的時候就不需要檢查相鄰的節(jié)點是否存在。
            //  head -> 最常用node -> node -> 最不常用node -> tail
            head = DlinkNode(-1, -1)
            tail = DlinkNode(-1, -1)
            head?.next = tail
            tail?.prev = head
        }
        
        // 在鏈表頭部添加節(jié)點 （每次在head后面添加!）
        func addNodeBehindHead(_ node: DlinkNode) {
            node.next = head?.next
            head?.next?.prev = node
            head?.next = node
            node.prev = head
            size += 1
        }
        
        // 刪除鏈表中的節(jié)點（node一定存在）
        func remove(_ node: DlinkNode) {
            node.prev?.next = node.next
            node.next?.prev = node.prev
           size -= 1
        }
        
        // 刪除鏈表中的最后一個節(jié)點, 并返回該節(jié)點
        func removeLastNode() -> DlinkNode {
            if size > 0 {
                if  let lastNode = tail?.prev {
                    remove(lastNode)
                    return lastNode
                }
            }
            return DlinkNode(-1, -1)
        }
    }
    
    // Hash表
    private var map: [Int : DlinkNode] = [:]
    // 最大容量
    private var capacity: Int = 0
    // 雙鏈表
    // 雙向鏈表 按照被使用的順序存儲了這些鍵值對，靠近頭部的鍵值對是最近使用的
    private var linkList: DoubleLinkedList?
    
    init (_ capacity: Int) {
        self.capacity = capacity
        linkList = DoubleLinkedList()
    }
    
    func get(_ key: Int) -> Int {
        // 對于 get 操作，首先判斷 key 是否存在
        guard let node: DlinkNode = map[key]  else {
             // 如果 key 不存在，則返回 -1
            print("輸出 -1")
            return -1
        }
        // 如果 key 存在，則 key 對應(yīng)的節(jié)點是最近被使用的節(jié)點。
        print("輸出\(node.value)")
        // 通過哈希表定位到該節(jié)點在雙向鏈表中的位置，并將其移動到雙向鏈表的頭部，
        put(key, node.value)
        // 最后返回該節(jié)點的值
        return node.value
    }
    
    func put(_ key: Int, _ value: Int) {
        // 對于 put 操作，首先判斷 key 是否存在
        if let node: DlinkNode = map[key] {
            // 如果 key 存在，則與 get 操作類似，先通過哈希表定位，再將對應(yīng)的節(jié)點的值更新為 value，并將該節(jié)點移到雙向鏈表的頭部。
            // 如果 key 存在，先創(chuàng)建一個新的節(jié)點。
            let newNode = DlinkNode(key, value)
            // 刪除該舊節(jié)點
            linkList?.remove(node)
            // 在雙向鏈表的頭部添加新節(jié)點，這樣每次更常用的數(shù)據(jù)再鏈表的前面， 靠近尾部的節(jié)點是最不常使用的數(shù)據(jù)
            linkList?.addNodeBehindHead(newNode)
            // 更新該節(jié)點的值
            map.updateValue(newNode, forKey: key)

        } else {
            // 如果 key 不存在，使用 key 和 value 創(chuàng)建一個新的節(jié)點，在雙向鏈表的頭部添加該節(jié)點
            if capacity == linkList?.size {
                // 判斷雙向鏈表的節(jié)點數(shù)是否達到最大容量，如果達到最大容量，則刪除雙向鏈表的尾部節(jié)點，
                let lastDeleteNode = linkList?.removeLastNode()
                // 并刪除哈希表中對應(yīng)的項；
                map.removeValue(forKey: lastDeleteNode?.key ?? -1)
            }
            let newNode = DlinkNode(key, value)
            // 在雙向鏈表的頭部添加該節(jié)點
            linkList?.addNodeBehindHead(newNode)
            // 并將 key 和該節(jié)點添加進哈希表中
            map.updateValue(newNode, forKey: key)
        }
    }
}

let lRUCache: LRUCache = LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
/*
輸出1
輸出 -1
輸出 -1
輸出3
輸出4
 */


/* 4.設(shè)計LRU緩存結(jié)構(gòu)
 
 題目描述：
 
 設(shè)計LRU緩存結(jié)構(gòu)，該結(jié)構(gòu)在構(gòu)造時確定大小，假設(shè)大小為K，并有如下兩個功能
 
 set(key, value)：將記錄(key, value)插入該結(jié)構(gòu)
 get(key)：返回key對應(yīng)的value值
 
 [要求]
 set和get方法的時間復(fù)雜度為O(1)
 某個key的set或get操作一旦發(fā)生，認為這個key的記錄成了最常使用的。
 當緩存的大小超過K時，移除最不經(jīng)常使用的記錄，即set或get最久遠的。
 
 若opt=1，接下來兩個整數(shù)x, y，表示set(x, y)
 若opt=2，接下來一個整數(shù)x，表示get(x)，若x未出現(xiàn)過或已被移除，則返回-1
 對于每個操作2，輸出一個答案
 
 
 示例1
 
 輸入
 [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
 
 返回值
 [1,-1]
 
 說明：
 第一次操作后：最常使用的記錄為("1", 1)
 第二次操作后：最常使用的記錄為("2", 2)，("1", 1)變?yōu)樽畈怀Ｓ玫? 第三次操作后：最常使用的記錄為("3", 2)，("1", 1)還是最不常用的
 第四次操作后：最常用的記錄為("1", 1)，("2", 2)變?yōu)樽畈怀Ｓ玫? 第五次操作后：大小超過了3，所以移除此時最不常使用的記錄("2", 2)，加入記錄("4", 4)，并且為最常使用的記錄，然后("3", 2)變?yōu)樽畈怀Ｊ褂玫挠涗? 
 */


public class Solution {
    /**
       方法一：哈希表 + 數(shù)組
     * @param operators int整型二維數(shù)組   [[opt],[opt]]
     * @param k int整型  , 大小為K
     * @return int整型一維數(shù)組
     */
    func LRU ( _ operators: [[Int]],  _ k: Int) -> [Int] {
        
        var dict: [Int : Int] = [:]
        var keys: [Int] = [] // 用來記錄操作的key，按照順序記錄
        var results: [Int] = []  // 記錄輸出結(jié)果
        
        for nums in operators {
            print("nums：\(nums)")
            if nums.isEmpty {
                continue
            }
            let opt = nums.first
            if opt == 1 { // 若opt=1， 接下來兩個整數(shù)x, y，表示set(x, y)
                if nums.count > 2 { // 保證至少有3個數(shù)據(jù)， 否則是無效數(shù)據(jù)
                    let x = nums[1]
                    dict.updateValue(nums[2], forKey: x)
                    if keys.contains(x) {
                        if let deleteIndex =  keys.firstIndex(of: x) {
                            // 曾經(jīng)處理過該數(shù)據(jù)，把之前處理的記錄刪除，再把當前的數(shù)據(jù)記錄在keys最后面
                            keys.remove(at: deleteIndex)
                        }
                    }
                    keys.append(x)
                    print("set(\(x), \(nums[2]))   keys:\(keys) , dict:\(dict)")
                    if dict.count > k { // 當緩存的大小超過K時，移除最不經(jīng)常使用的記錄，即set或get最久遠的。
                        // keys按照順序記錄了操作的所有key, 第一個數(shù)據(jù)就是最不常用的數(shù)據(jù)
                        dict.removeValue(forKey: keys[0])
                        // 緩存的大小超過k，移除第一個數(shù)據(jù)（也就是最不常用的數(shù)據(jù)）
                        keys.remove(at: 0)
                        print("緩存的大小超過\(k), 移除第一個數(shù)據(jù)后， keys:\(keys) , dict:\(dict)")
                    }
                } else {
                    continue
                }
            } else if (opt == 2) { // 若opt=2，接下來一個整數(shù)x，表示get(x)，
                if nums.count > 1 { // 保證至少有2個數(shù)據(jù)， 否則是無效數(shù)據(jù)
                    let x = nums[1]
                    if dict.keys.contains(x) {
                        if keys.contains(x) {
                            if let deleteIndex =  keys.firstIndex(of: x) {
                                // 曾經(jīng)處理過該數(shù)據(jù)，把之前處理的記錄刪除，再把當前的數(shù)據(jù)記錄在keys最后面
                                keys.remove(at: deleteIndex)
                            }
                        }
                        results.append(dict[x] ?? -1)
                        keys.append(x)
                    } else { // 若x未出現(xiàn)過或已被移除，則返回-1
                        results.append(-1)
                    }
                    print("get(\(x), \(dict[x] ?? -1))   keys:\(keys) , dict:\(dict)")
                } else {
                    continue
                }
            }
        }
        return results
    }
}

var operators = [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]]
var reult = Solution().LRU(operators, 3)
print("輸出：\(reult)")