前文讲述了数组、单链表来实现缓存的数据结构，一步一步地反映出 LRU 是如何被改进的。至今我们没有放下改进的脚步。在上一例单链表中遇到的一个问题是，提供泛型的 T 为单一记录值，无法处理 Key/Value 结构。通过百度，我们找到一仁兄的资源，比较不错，解决了该问题，并且在单链表的思路与上例更不一样，却更为简洁。
public class LRUCache_2<K, V> { int cap; int size = 0; private Node<K, V> head; private Node<K, V> tail; /** * 设定容量 * @param cap 设定容量 * @param db */ public LRUCache_2(int cap) { this.cap = cap; } public V get(K key) { Node<K, V> previous = null; // ahead 是之前的那个节点 Node<K, V> temp = head; while (temp != null) { if (temp.key.equals(key)) { if (temp.next != null) // 找到了匹配的缓存 moveToLast(previous, temp); return temp.value; } previous = temp; temp = temp.next; } return null; } private void moveToLast(Node<K, V> previous, Node<K, V> target) { if (target == tail) return; if (head == target) { head = target.next;// 头部不当头了，后面的上 } else { previous.next = target.next; // target 被抽出来了，后面的接上 } tail.next = target;// 续上新的， 放在最后插入 tail = target; target.next = null; } public V put(K key, V value) { if (head == null) { // 空，直接插入 tail = head = new Node<>(key, value); size++; return value; } Node<K, V> temp = head; while (temp != null) { if (temp.key.equals(key)) { // 已经存在 if (temp.value.equals(value)) { // 没有不同 return value; } else { V oldValue = temp.value; // 进行了值的替换 temp.value = value; return oldValue; } } temp = temp.next; } // 找不到，是新成员 temp = new Node<>(key, value); tail.next = temp;// 加入到尾部 tail = temp; size++; checkCap(); return value; } private void checkCap() { if (size > cap) { // 进行淘汰,摘除开头 head = head.next; size--; } } public Node<K, V> peek() { return head; } public static class Node<K, V> { K key; V value; Node<K, V> next; Node(K key, V value) { this.key = key; this.value = value; } } @Override public String toString() { StringBuilder sb = new StringBuilder(); while (head != null) { sb.append(head.key + " " + head.value); head = head.next; } return sb.toString(); } }笔者修改了几处地方，不影响主干意思。通过代码可见，该例并没有分离单链表类和 LRU 类，而是合二为一。另外类声明中除了 head 头部元素外，还给出了 tail 尾部元素，使得在执行 moveToLast() 时候无须遍历链表，改进了性能。
值得一提的是，该链表都是尾部加入新元素，在头部删除老元素——这一点与前面的例子刚好相反。删除的方法也直观简单：
if (size > cap) { head = head.next;// 进行淘汰,摘除开头 size--; }1、既然谈到优化问题，我们不妨再继续讨论。我们考察 moveToLast()，原本需要前驱节点 previous 参数，现在可否只需要一个 target 参数无须 previous？
private void moveToLast(Node<K, V> previous, Node<K, V> target) { if (target == tail) return; if (head == target) { head = target.next;// 头部不当头了，后面的上 } else { previous.next = target.next; // target 被抽出来了，后面的接上 } tail.next = target;// 续上新的， 放在最后插入 tail = target; target.next = null; }传统思维，如上例，是要获取到被删除结点前面的那一个结点的指针 next， 修过它为 target.next 才可以的，比如一个链表 A->B->C->D->E->F->G。如果我们要删除结点 E，那么我们只需要让结点D的指针指向结点 F 即可。但是因为限于单链表，是没有前驱节点的，所以要靠遍历链表获取前一个节点，显然这种方法是不能在 O(1) 时间内调整节点的。
我们能否换个思路？这里有个巧妙的方法，被删除结点E的后一个结点指针是很容易得到的，也就是 target.next，下一级也容易得到，即 target.next.next。于是当前节点对象不变，但 data 数据拷贝自下一个节点，并且 next 指向 target.next.next，那样等于“架空”了 target.next，却又保留 target.next 的数据，完成删除动作。moveToLast() 也是同理，如法炮制。
2、考察 get 方法，要获取匹配的 value 仍需要经过 while 循环，时间复杂度为 O(n)
public V get(K key) { Node<K, V> previous = null; // ahead 是之前的那个节点 Node<K, V> temp = head; while (temp != null) { if (temp.key.equals(key)) { if (temp.next != null) // 找到了匹配的缓存 moveToLast(previous, temp); return temp.value; } previous = temp; temp = temp.next; } return null; }有没有办法可以让复杂度也在O(1)？ 实际上 moveToLast() 的操作是 O(1)时间复杂度，因为提供了 tail 尾部指针，这已经有点 双向链表的意味了。——没错，使用双向链表，所有操作都是 O(1) 时间复杂度（除了遍历）。下一节深入讨论。
文章贡献：https://www.cnblogs.com/dolphin0520/p/3741519.html
