Leetcode 146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key)

• Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  put(key, value)
• Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:Could you do both operations in O(1) time complexity?

题意：实现一个简单的LRU cache，仅需要支持get和put，能否用O(1)的时间复杂度实现。

思路：用一个双端链表记录所有节点，有操作的节点就移到链表尾部，那么最近最少使用的节点就位于链表头部。通过哈希表来做key到链表节点的映射。

private int max;
private Map<Integer, DListNode> map = new HashMap<>();
private DListNode head = new DListNode(0, 0);
private DListNode tail = new DListNode(0, 0);

public EP_LRUCache(int capacity) {
    max = capacity;
    head.next = tail;
    tail.pre = head;
}

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

    this.moveToTail(map.get(key));
    return map.get(key).val;
}

public void put(int key, int value) {
    if (!map.containsKey(key) && map.size() >= max) {
        this.removeLeastUse();
    }

    if (map.containsKey(key)) {
        this.moveToTail(map.get(key));
        map.get(key).val = value;
    } else {
        DListNode newNode = new DListNode(key, value);
        map.put(key, newNode);

        DListNode pre = this.tail.pre;
        newNode.next = this.tail;
        this.tail.pre = newNode;
        newNode.pre = pre;
        pre.next = newNode;
    }
}

private void removeLeastUse() {
    if (this.map.size() <= 0) {
        return;
    }

    DListNode lease = this.head.next;
    this.head.next = lease.next;
    lease.next.pre = this.head;
    map.remove(lease.key);
}

private void moveToTail(DListNode node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;

    DListNode pre = this.tail.pre;
    node.next = this.tail;
    this.tail.pre = node;
    node.pre = pre;
    pre.next = node;
}