LRU缓存

思路：

利用链表的删除和添加时间复杂度 $O(1)$ 和 哈希表的存取的平均时间复杂度 $O(1)$ 的特性实现

定义：

class LRUCache {
    public LRUCache(int capacity) {
    }
    
    public int get(int key) {
    }
    
    public void put(int key, int value) {
    }
}

定义双端队列实现数据的顺序存储，最近访问的数据放到队头

static class ListNode {
    int key;
    int val;
    ListNode next;
    ListNode prev;

    public ListNode(int key) {
      this.key = key;
    }
}

成员属性和构造方法

int capacity;   //容量
Map<Integer, ListNode> cache; //节点缓存，快速定位节点位置
ListNode head; //头指针
ListNode tail; //尾指针

public LRUCache(int capacity) {
  	this.capacity = capacity;
  	this.cache = new HashMap<>(capacity);
}

put

public void put(int key, int value) {
    if (capacity <= 0) {
      	return;
    }
    ListNode node = cache.get(key);
    if (node == null) {
        //数据不存在，新增节点
        node = new ListNode(key);
        if (cache.size() == capacity) {
            //超出容量，移除队尾元素
            cache.remove(tail.key);
            if (tail.prev == null) {
                //capacity == 1
                this.head = node;
                this.tail = node;
            } else {
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
        } else if (cache.size() == 0) {
            this.head = node;
            this.tail = node;
        }
        cache.put(key, node);
    }
    node.val = value;
    if (node != head) {
        //把新增/更新之后的节点挪动到队头
        ListNode prev = node.prev;
        ListNode next = node.next;
        if (prev != null) {
            prev.next = next;
        }
        if (next != null) {
            next.prev = prev;
        }
        if (node == tail) {
            tail = prev;
        }
        node.prev = null;
        node.next = head;
        head.prev = node;
        head = node;
    }
}

get

public int get(int key) {
    if (capacity <= 0) {
      return -1;
    }
  	//数据不存在
    ListNode node = cache.get(key);
    if (node == null) {
      	return -1;
    }
    if (node != head) {
      	//不是队头，还需要将节点挪动到队头
        ListNode prev = node.prev;
        ListNode next = node.next;
        prev.next = next;
        if (next != null) {
          	next.prev = prev;
        }
        if (node == tail) {
          	tail = prev;
        }
        node.prev = null;
        node.next = head;
        head.prev = node;
        head = node;
    }
    return node.val;
}