LRU Cache 134

Question

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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(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.

Solution

用HashMap来存key和和其对应的node，便于之后检索key是否已经存在。用双向链表，便于操作数组中间的元素移动和删除。

get()：如果key不存在，则返回－1；如果key存在，则将该key对应的node移到链表尾部。

set()：如果key存在，则将修改过value的该key对应node移到链表尾部；如果key不存在，分两种情况：1）若chache已经达到其capacity，则删去链表第一个node（least recently used item），再加入该key的node；2）若chache还没达到其capacity，则在链表尾部加入该key的node。

代码如下：

public class Solution {
    //双向链表
    private class Node{
        Node next;
        Node pre;
        int key;
        int value;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
            next = pre = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> map = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    // @param capacity, an integer
    public Solution(int capacity) {
        // write your code here
        this.capacity = capacity;
        head.next = tail;
        tail.pre = head;
    }

    // @return an integer
    public int get(int key) {
        // write your code here
        if(!map.containsKey(key)){
            return -1;
        }

        Node current = map.get(key);
        current.pre.next = current.next;
        current.next.pre = current.pre;

        moveToTail(current);

        return current.value;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        // write your code here
        if(map.containsKey(key)){
            map.get(key).value = value;
            Node current = map.get(key);
            current.pre.next = current.next;
            current.next.pre = current.pre;

            moveToTail(current);
            return;
        }

        if(map.size() == capacity){
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.pre = head;
        }

        Node newNode = new Node(key, value);
        map.put(key, newNode);
        moveToTail(newNode);
    }

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