力扣：146. LRU 緩存機制

題目轉載自：力扣

https://leetcode-cn.com/problems/lru-cache/

解答：

public class LRUCache {

    class CacheNode {
        Integer key;
        Integer value;
        CacheNode prePointer;
        CacheNode nextPointer;

        public CacheNode(Integer key, Integer value, CacheNode prePointer, CacheNode nextPointer) {
            this.key = key;
            this.value = value;
            this.prePointer = prePointer;
            this.nextPointer = nextPointer;
        }
    }

    private int capacity;

    private Map<Integer, CacheNode> cache;

    private CacheNode head;

    private CacheNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
        this.head = new CacheNode(Integer.MIN_VALUE, Integer.MIN_VALUE, null, null);
        this.tail = new CacheNode(Integer.MAX_VALUE, Integer.MAX_VALUE, head, null);
        head.nextPointer = tail;
    }

    public int get(int key) {
        CacheNode cacheNode = cache.get(key);
        if (cacheNode == null) {
            return -1;
        }
        if (cacheNode.prePointer == head) {
            return cacheNode.value;
        }
        // 先把這個結點拆下來
        cacheNode.prePointer.nextPointer = cacheNode.nextPointer;
        cacheNode.nextPointer.prePointer = cacheNode.prePointer;
        // 把這個結點放到頭部
        CacheNode tempNode = head.nextPointer;
        head.nextPointer = cacheNode;
        cacheNode.prePointer = head;
        tempNode.prePointer = cacheNode;
        cacheNode.nextPointer = tempNode;
        return cacheNode.value;
    }

    public void put(int key, int value) {
        CacheNode cacheNode = cache.get(key);
        if (cacheNode == null) {
            // put
            if (cache.size() == capacity) {
                // 删除尾部的結點
                CacheNode lastNode = tail.prePointer;
                CacheNode lastPreNode = lastNode.prePointer;
                lastPreNode.nextPointer = tail;
                tail.prePointer = lastPreNode;
                cache.remove(lastNode.key);
                lastNode.nextPointer = null;
                lastNode.prePointer = null;
                lastNode = null;
            }
            // insert
            CacheNode newNode = new CacheNode(key, value, null, null);
            CacheNode tempNode = head.nextPointer;
            head.nextPointer = newNode;
            newNode.prePointer = head;
            tempNode.prePointer = newNode;
            newNode.nextPointer = tempNode;
            cache.put(key, newNode);
            return;
        }
        // update
        // 删除原來的結點
        CacheNode cacheNodePrePointer = cacheNode.prePointer;
        cacheNodePrePointer.nextPointer = cacheNode.nextPointer;
        cacheNode.nextPointer.prePointer = cacheNode.prePointer;
        // 移到頭部
        cacheNode.value = value;
        CacheNode tempNode = head.nextPointer;
        head.nextPointer = cacheNode;
        cacheNode.prePointer = head;
        tempNode.prePointer = cacheNode;
        cacheNode.nextPointer = tempNode;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(2, 1);
        lruCache.put(1, 1);
        lruCache.put(2, 3);
        lruCache.put(4, 1);
        int i = lruCache.get(1);
        System.out.println(i);
        i = lruCache.get(2);
        System.out.println(i);
    }
}