Leetcode: LRU Cache 了解分析

題目大意：設計一個資料結構實作LRU（Least Recently Used）緩存機制，必須實作以下兩個操作：get和set

get(key) -- 如果key存在，傳回key所對應的value（為正數）；否則傳回-1；

set(key, value) -- key不存在時，設定或插入這個(key, value)對，當cache的容量已滿時，插入前應該移除least recently used元素。

了解：1）題目要求設計并實作一個cache，使用LRU排程機制來進行存儲管理。LRU排程是指當存儲滿時，選擇最近最少使用的元素移除緩存，我們知道LRU排程最新調用或使用的對象都會放在第一個，随着時間的推移，當存儲滿時，排在最後個那個元素就是最長時間沒有被再次使用的，就是該被移除的那個。

2）設計的資料結構要滿足插入、删除和移動很容易，所有很容易想到用連結清單，為滿足插入首節點和删除最後一個元素很簡單，我們同時為連結清單增加首節點（head）和尾節點（tail），并使用雙向連結清單。隻需要實作對連結清單的三種操作：插入首節點，移除尾節點和将某個給定節點移到首位（表示最新使用）。

實作：

public class LRUCache {
    private int capacity;
    
    class node { // 節點類型
        int key;
        int val;
        node next;
        node pre;
        private node(int key, int val) {
            this.key = key;
            this.val = val;
            this.next = null;
            this.pre = null;
        }
    }
    
    private class cacheList { // 内部類 實作對雙向連結清單的插入、删除和移動的操作
        private node head, tail; // 增加首尾節點，友善插入首節點和删除尾節點
        private cacheList() {
            head = new node(0, 0);
            tail = new node(0, 0);
            head.next = tail;
            tail.pre = head;
        }
        
        private void insertFirst(node p) { // 插入到第一個節點位置
            p.next = head.next;
            head.next.pre = p;
            p.pre = head;
            head.next = p;
        }
        
        private node removeLast() { // 删除最後一個節點，并傳回被删除的節點
            node last = tail.pre;
            last.next.pre = last.pre;
            last.pre.next = last.next;
            
            return last;
        }
        
        private void removeToFirst(node p) { // 将特定節點移動到第一個節點位置
            p.pre.next = p.next;
            p.next.pre = p.pre;
            this.insertFirst(p);
        }
    }
    
    private cacheList cachelist;
    public HashMap<Integer, node> map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cachelist = new cacheList();
        map = new HashMap<Integer, node>();
    }
    
    public int get(int key) { // 查找某個key對應的value，若不存在則傳回-1
        node res = map.get(key);
        if(res != null) {
            cachelist.removeToFirst(res);
            return res.val;
        }
        return -1;
    }
    
    public void set(int key, int value) { // 插入一(key, value)對
        if(map.containsKey(key)) { // 若該key已存在，則更新其對應的value，并移動到第一個節點位置
            node res = map.get(key);
            res.val = value;
            map.put(key, res);
            cachelist.removeToFirst(res);
        }
        else { // 不存在，則将(key, value)對插入到第一個節點位置
            if(map.size() == capacity) { // 若cache容量已滿，則移除LRU節點，即連結清單的最後一個節點
                node last = cachelist.removeLast();
                map.remove(last.key);
            }
            node q = new node(key, value);
            cachelist.insertFirst(q);
            map.put(key, q);
        }
    }
}