实现案例二
不依赖 jdk
数据结构示意：
思路解释：
1、 参照 HashMap 的做法先创建一个, Node 节点对象，包含 k, v 属性 和前驱，后继对象指针。
2、 构建一个双端链表 DoubleLinkList 实现缓存数据链表结构。主要包含 addHead 添加到头节点，作用是用来更新新访问的 Node， 还有一个就是 removeNode 删除节点。以及 getLastNode 获取尾部节点。
3、通过 Map 和 DoubleLinkList 联合起来共同组建一个 LRU 结构。整体如上图所示
public class Q149_1 { // map 负责查找，构建一个虚拟的双向链表， 它里面安装的就是一个 Node 节点，作为数据的载体 // 1 构造一个 Node 节点，作为数据的载体 class Node<K, V> { K key; V value; Node<K, V> prev; Node<K, V> next; public Node() { this.prev = this.next = null; } public Node(K key, V value) { this.key = key; this.value = value; this.prev = this.next = null; } } //2 构建一个双向队列，里面存放的就是我们的 Node class DoubleLinkList<K, V> { Node<K, V> head; Node<K, V> tail; // 2.1 构造方法 public DoubleLinkList() { this.head = new Node<>(); this.tail = new Node<>(); this.head.next = this.tail; this.tail.prev = this.head; } // 2.2 添加到头 public void addHead(Node<K, V> node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; } //2.3 删除节点 public void removeNode(Node<K, V> node) { node.next.prev = node.prev; node.prev.next = node.next; node.prev = null; node.next = null; } //2.4 获得最后一个节点 public Node<K, V> getLast() { return tail.prev; } } private int cacheSize; private Map<Integer, Node<Integer, Integer>> map; private DoubleLinkList<Integer, Integer> doubleLinkList; public Q149_1(int cacheSize) { this.cacheSize = cacheSize; this.map = new HashMap<>(); doubleLinkList = new DoubleLinkList<>(); } public int get(int key) { if (!map.containsKey(key)) { return -1; } Node<Integer, Integer> node = map.get(key); doubleLinkList.removeNode(node); doubleLinkList.addHead(node); return node.value; } // save of update method public void put(int key, int value) { // update if (map.containsKey(key)) { Node<Integer, Integer> node = map.get(key); node.value = value; map.put(key, node); doubleLinkList.removeNode(node); doubleLinkList.addHead(node); } else { if (map.size() == cacheSize) { Node<Integer, Integer> lastNode = doubleLinkList.getLast(); map.remove(lastNode.key); doubleLinkList.removeNode(lastNode); } // 新增 Node<Integer, Integer> newNode = new Node<>(key, value); map.put(key, newNode); doubleLinkList.addHead(newNode); } } public static void main(String[] args) { Q149_1 q149 = new Q149_1(3); q149.put(1, 1); q149.put(2, 2); q149.put(3, 3); System.out.println(q149.map.keySet()); q149.put(1, 2); q149.put(2, 1); System.out.println(q149.map.keySet()); } }
