LRU 缓存机制 - 数据结构的实现

  1. class LRUCache {
  2.     class Node{
  3.         int key;
  4.         int val;
  5.         Node next;
  6.         Node pre;
  7.         Node(){}
  8.         Node(int key, int val){
  9.             this.key = key;
  10.             this.val = val;
  11.         }
  12.     }
  13.     Node first;
  14.     Node last;
  15.     Map<Integer, Node> map;
  16.     int capacity;
  17.     public LRUCache(int capacity) {
  18.         this.first = new Node();
  19.         this.last = new Node();
  20.         first.next = last;
  21.         last.pre = first;
  22.         this.map = new HashMap<>();
  23.         this.capacity = capacity;
  24.     }
  26.     public int get(int key) {
  27.         Node node = map.get(key);
  28.         if(node == null) return -1;
  29.         getNode(node);
  30.         moveToHead(node);
  31.         return node.val;
  32.     }
  34.     public void put(int key, int value) {
  35.         Node node = map.get(key);
  36.         if(node != null){
  37.             node.val = value;
  38.             getNode(node);
  39.             moveToHead(node);
  40.         }else{
  41.             if(map.size() == capacity){
  42.                 map.remove(last.pre.key);
  43.                 getNode(last.pre);
  44.             }
  45.             node = new Node(key, value);
  46.             map.put(key, node);
  47.             moveToHead(node);
  48.         }
  49.     }
  51.     public void getNode(Node node){
  52.         node.pre.next = node.next;
  53.         node.next.pre = node.pre;
  54.     }
  56.     public void moveToHead(Node node){
  57.         node.next = first.next;
  58.         first.next.pre = node;
  59.         node.pre = first;
  60.         first.next = node;
  61.     }
  62. }

自己处理输入输出

[

](https://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61?tpId=188&&tqId=35312&rp=1&ru=/ta/job-code-high-week&qru=/ta/job-code-high-week/question-ranking)