题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

题目分析

使用双向链表来维护数据，使用 HashMap 实现对 key 的 O(1) 访问.
每次访问一个数据（get 或 put），就把其移动到链表的尾部，而链表头部即是最久未访问的元素。当容量超出设定时（put 时判断），将头部元素在链表和 HashMap 中同步移除。
使用虚拟头结点和尾结点，代码写起来更简单。

Java

public class LruCache {

    private class Node {
        int key;
        int value;
        Node pre;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<Integer, Node> map = new HashMap<>();
    // 虚拟头/尾结点
    private Node head = new Node(0, 0); // 旧
    private Node tail = new Node(0, 0); // 新
    private int capacity;

    public LruCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        Node node = map.get(key);
        moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.value = value;
        } else {
            node = new Node(key, value);
            map.put(key, node);
        }
        moveToTail(node);
        if (map.size() > capacity) {
            removeEldest();
        }
    }

    private void moveToTail(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        if (pre != null) {
            pre.next = next;
            next.pre = pre;
        }
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }

    private void removeEldest() {
        map.remove(head.next.key);
        head.next = head.next.next;
        head.next.pre = head;
    }
}

Kotlin

class LruCache(var capacity: Int) {

    private val map = HashMap<Int, Node>()
    private val head = Node(0, 0) // 旧
    private val tail = Node(0, 0) // 新

    init {
        head.next = tail
        tail.pre = head
    }

    fun get(key: Int): Int {
        if (!map.containsKey(key)) {
            return -1
        }
        val node = map[key]!!
        moveToTail(node)
        return node.value
    }

    fun put(key: Int, value: Int) {
        if (map.containsKey(key)) {
            val node = map[key]!!
            node.value = value
            moveToTail(node)
        } else {
            val node = Node(key, value)
            map[key] = node
            moveToTail(node)
            if (map.size > capacity) {
                removeEldest()
            }
        }
    }

    private fun moveToTail(node: Node) {
        if (node.pre != null) {
            val pre = node.pre
            val next = node.next
            pre?.next = next
            next?.pre = pre
        }

        tail.pre?.next = node
        node.pre = tail.pre
        node.next = tail
        tail.pre = node
    }

    private fun removeEldest() {
        val node = head.next
        head.next = node?.next
        head.next?.pre = head
        map.remove(node?.key!!)
    }

    private data class Node(var key: Int, var value: Int, var pre: Node? = null, var next: Node? = null)
}