LRU算法—Swift代码实现

Swift

需要用到哈希表和双向链表进行实现。
哈希表可以快速查找，双向链表能够通过自身从链表中删除自身

class DLinkedNode {
    // 这个是，删除尾节点，要同步哈希表。哈希表也要对应删除的时候，用到
    let key: Int
    var val: Int
    var pre: DLinkedNode?
    var next: DLinkedNode?
    
    init(_ key: Int, value: Int) {
        self.key = key
        val = value
    }
}

class LRUCache {
    var capacity: Int
    var head = DLinkedNode(-1, value: -1)
    var tail = DLinkedNode(-1, value: -1)
    var container  = [Int: DLinkedNode]()
    var hasCount = 0

    init(_ capacity: Int) {
        self.capacity = capacity
        head.next = tail
        tail.pre = head
    }

    func get(_ key: Int) -> Int {
        // 有一个刷新机制
        if let node = container[key]{
            deleteNode(node)
            insertHead(node)
            return node.val
        }
        else{
            return -1
        }
    }

    func put(_ key: Int, _ value: Int) {
        if let node = container[key]{
            // 包含，就换顺序 还有一个更新操作
            node.val = value
            deleteNode(node)
            insertHead(node)
        } else {
            if hasCount >= capacity{
                // 超过，就处理
                hasCount -= 1
                deleteTail()
            }
            hasCount += 1
            // 不包含，就插入头节点
            let node = DLinkedNode(key, value: value)
            insertHead(node)
            container[key] = node
        }
    }

    private func insertHead(_ node: DLinkedNode) {
        let temp = head.next
        temp?.pre = node
        head.next = node
        node.pre = head
        node.next = temp
        container[node.key] = node
    }

    private func deleteNode(_ node: DLinkedNode) {
        node.pre?.next = node.next
        node.next?.pre = node.pre
        node.pre = nil
        node.next = nil
        container.removeValue(forKey: node.key)
    }

    private func deleteTail() {
        if let toDel = tail.pre {
            toDel.pre?.next = tail
            tail.pre = toDel.pre
            container.removeValue(forKey: toDel.key)
        }
    }
}