14.LRU

2.27
- 在 put 时，如果超容量了，就 删除 end前的真尾节点 后，取出此 key 再删 cache 的
2.26
- 未写算法14.非静态内部类和静态内部类的区别？

// 1. 这是一个同级类（Sibling Class）
// 注意：不能加 public，只能是默认权限（package-private）
class DLinkedList {
    int key;
    int val;
    DLinkedList prev;
    DLinkedList next;
 
    public DLinkedList() {}
 
    public DLinkedList(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
 
// 2. 这是主类
public class LRUCache {
    private Map<Integer, DLinkedList> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedList head, end;
 
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedList(); // 直接 new，不需要外部类前缀
        end = new DLinkedList();
        head.next = end;
        end.prev = head;
    }
 
    // ... 剩下的 get, put, moveToHead 等方法逻辑不变 ...
}

class DLinkedList{
    int key;
    int value;
    DLinkedList prev;
    DLinkedList next;
    public DLinkedList(){}
    public DLinkedList(int key,int value){this.key = key;this.value = value;}
}
 
class LRUCache {
    int capacity;
    int size;
    DLinkedList head;
    DLinkedList end;
    Map<Integer,DLinkedList> cache = new HashMap<>();
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DLinkedList();
        end = new DLinkedList();
        head.next = end;
        end.prev = head;
        this.size = 0;
    }
    
    public int get(int key) {
        DLinkedList node = cache.get(key);
        if(node!=null){
            moveToHead(node);
            return node.value;
        }else{
            return -1;
        }
    }
    
    public void put(int key, int value) {
        DLinkedList node = cache.get(key);
        if(node==null){
            DLinkedList newNode = new DLinkedList(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            if(size>capacity){
                DLinkedList newNode1= removeEnd();
                cache.remove(newNode1.key);
                size--;
            }
        }else{
            remove(node);
            node.value=value;
            moveToHead(node);
        }
        
    }
 
    public void addToHead(DLinkedList node){
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head; 
    }
 
    public void moveToHead(DLinkedList node){
        remove(node);
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }
    public void remove(DLinkedList node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    public DLinkedList removeEnd(){
        DLinkedList node = end.prev;
        remove(node);
        return node;
    }
}

当你把类挪到外面时，有几个 Java 的“硬规定”你必须知道：

只能有一个 public 类：在一个 .java 文件中，只能有一个类被声明为 public，且文件名必须与这个类名一致。所以 DLinkedList 前面不能加 public。
访问权限变了：现在的 DLinkedList 是“包访问权限”（Package-private）。这意味着，同一个文件夹（包）下的其他类，也能直接看到并使用 DLinkedList。这比写在内部（private）的封装性差了一点。
物理独立，逻辑关联：虽然它在外面，但它依然是一个独立的类。它和 LRUCache 之间没有任何“父子”引用关系，所以它天然就是“静态”的效果（不持有外部类引用）。

现实工程中，常用private static class，为了避免隐式持有外部类引用，节省内存并防止潜在的内存泄漏。

2.11
- 难点 0：先声明DlinkedList 数据结构，之后声明 cache ，容量，最大容量，和头尾哨兵的全局参数，，在初始化时，声明头尾哨兵，和两个容积
- 难点1：put 时需要同步添加或删除 map，不能只是删除 node 节点
- 难点 2：删除尾节点时，需要删除 end。prev

class LRUCache {
 
    class DLinkedList {
        int key;
        int val;
        DLinkedList prev;
        DLinkedList next;
        public DLinkedList(){}
        public DLinkedList(int key,int val){this.key = key;this.val =val;}
    }
 
    private Map<Integer,DLinkedList> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedList head,end;
 
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedList();
        end = new DLinkedList();
        head.next = end;
        end.prev = head;
    }
    
    public int get(int key) {
        DLinkedList node = cache.get(key);
        if(node==null) return -1;
        moveToHead(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        DLinkedList node = cache.get(key);
        if(node==null){
            DLinkedList node1 = new DLinkedList(key,value);
            cache.put(key,node1);
            addToHead(node1);
            size++;
            if(size>capacity){
                DLinkedList tail =  removeEnd();
                cache.remove(tail.key);
                size--;
            }
        }else{
            moveToHead(node);
            node.val = value;
        }
    }
    public void moveToHead(DLinkedList node){
        remove(node);
        addToHead(node);
    }
    public void remove(DLinkedList node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    public DLinkedList removeEnd(){
        DLinkedList res = end.prev;
        remove(res);
        return res;
    }
    public void addToHead(DLinkedList node){
        node.next = head.next;
        node.prev = head;
        head.next = node;
        node.next.prev = node;
    }
}

1.26
- put 时多出一步操作，不为 null，创建一个节点头插后(同样需要插入 cache)，判断容积，删除最后一个节点并删除 cache 中的数据
- 删除尾节点时，注意的到的是尾哨兵节点的 prev 节点
1.25
- 抄了一遍

import java.util.HashMap;
import java.util.Map;
 
class LRUCache {
 
    // 1. 定义双向链表节点
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }
 
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;
 
    // 2. 初始化缓存
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点 (Dummy Nodes)
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
 
    // 3. Get 操作
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到链表头部
        moveToHead(node);
        return node.value;
    }
 
    // 4. Put 操作
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            // 判断是否超出容量
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 同时删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        } else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }
 
    // ===============================================
    // 下面是极其重要的“链表辅助函数”，把操作封装起来
    // ===============================================
 
    // 在链表头部添加新节点 (在 dummy head 之后)
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
 
    // 删除链表中的任意一个节点 (因为是双向链表，所以自己就能断开)
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    // 将已有节点移动到头部 (也就是：先删除，再加到头部)
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
 
    // 删除尾部数据 (在 dummy tail 之前)，并返回该节点
    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res; // 返回它是为了之后从 HashMap 中删除它的 key
    }
}

Dx's Tech Notes

Explorer

14.LRU

Graph View

Backlinks