从问题本身可以看出，查询链接列表时会出现O（n）操作问题。因此，我们需要替代的数据结构。我们需要能够从HashMap更新项目的上次访问时间，而无需进行搜索。
我们可以保留两个单独的数据结构。 具有（Key，Pointer） 对和 双链表 的 HashMap
将用作删除和存储值的优先级队列。从HashMap，我们可以指向双向链表中的元素并更新其检索时间。因为我们直接从HashMap转到列表中的项目，所以我们的时间复杂度保持在O（1）
例如，我们的双向链表如下所示：
least_recently_used -> A <-> B <-> C <-> D <-> E <- most_recently_used
我们需要保持指向LRU和MRU项目的指针。条目的值将存储在列表中，当我们查询HashMap时，我们将获得一个指向列表的指针。在get（）上，我们需要将该项目放在列表的最右侧。在put（key，value）上，如果缓存已满，则需要从列表和HashMap中删除列表最左侧的项目。
以下是Java中的示例实现：
public class LRUCache<K, V>{ // Define Node with pointers to the previous and next items and a key, value pair class Node<T, U> { Node<T, U> previous; Node<T, U> next; T key; U value; public Node(Node<T, U> previous, Node<T, U> next, T key, U value){ this.previous = previous; this.next = next; this.key = key; this.value = value; } } private HashMap<K, Node<K, V>> cache; private Node<K, V> leastRecentlyUsed; private Node<K, V> mostRecentlyUsed; private int maxSize; private int currentSize; public LRUCache(int maxSize){ this.maxSize = maxSize; this.currentSize = 0; leastRecentlyUsed = new Node<K, V>(null, null, null, null); mostRecentlyUsed = leastRecentlyUsed; cache = new HashMap<K, Node<K, V>>(); } public V get(K key){ Node<K, V> tempNode = cache.get(key); if (tempNode == null){ return null; } // If MRU leave the list as it is else if (tempNode.key == mostRecentlyUsed.key){ return mostRecentlyUsed.value; } // Get the next and previous nodes Node<K, V> nextNode = tempNode.next; Node<K, V> previousNode = tempNode.previous; // If at the left-most, we update LRU if (tempNode.key == leastRecentlyUsed.key){ nextNode.previous = null; leastRecentlyUsed = nextNode; } // If we are in the middle, we need to update the items before and after our item else if (tempNode.key != mostRecentlyUsed.key){ previousNode.next = nextNode; nextNode.previous = previousNode; } // Finally move our item to the MRU tempNode.previous = mostRecentlyUsed; mostRecentlyUsed.next = tempNode; mostRecentlyUsed = tempNode; mostRecentlyUsed.next = null; return tempNode.value; } public void put(K key, V value){ if (cache.containsKey(key)){ return; } // Put the new node at the right-most end of the linked-list Node<K, V> myNode = new Node<K, V>(mostRecentlyUsed, null, key, value); mostRecentlyUsed.next = myNode; cache.put(key, myNode); mostRecentlyUsed = myNode; // Delete the left-most entry and update the LRU pointer if (currentSize == maxSize){ cache.remove(leastRecentlyUsed.key); leastRecentlyUsed = leastRecentlyUsed.next; leastRecentlyUsed.previous = null; } // Update cache size, for the first added entry update the LRU pointer else if (currentSize < maxSize){ if (currentSize == 0){ leastRecentlyUsed = myNode; } currentSize++; } }}
