LRU Cache 解答

Question

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution

My first thought is to use a linked list and a hashmap. But remove and add element for linked list is O(n) per step.

So, the final idea is to implement a bi-directional linked list.

details

For this question, I submitted over 10 times and finally got accepted.

There are many details we need to check.

1. When deleting a node, we should modify both prev and next attributes of its neighbors.

2. Every time when we add a new node, we should check whether it is the first node.

3. When input capacity is 1, we should deal with it separately.

  1 // Construct double list node
  2 class Node {
  3     public Node prev;
  4     public Node next;
  5     private int val;
  6     private int key;
  7     public Node(int key, int val) {
  8         this.key = key;
  9         this.val = val;
 10     }
 11     public void setValue(int val) {
 12         this.val = val;
 13     }
 14     public int getKey() {
 15         return key;
 16     }
 17     public int getValue() {
 18         return val;
 19     }
 20 }
 21 
 22 
 23 public class LRUCache {
 24     private int capacity;
 25     private Map<Integer, Node> map;
 26     private Node head;
 27     private Node tail;
 28     
 29     public LRUCache(int capacity) {
 30         this.capacity = capacity;
 31         map = new HashMap<Integer, Node>();
 32     }
 33     
 34     private void moveToHead(Node target) {
 35         // Check whether target is already at head
 36         if (target.prev == null)
 37             return;
 38         // Check whether target is at tail
 39         if (target == tail)
 40             tail = target.prev;
 41         Node prev = target.prev;
 42         Node next = target.next;
 43         if (prev != null)
 44         prev.next = next;
 45         if (next != null)
 46             next.prev = prev;
 47         
 48         Node oldHead = head;
 49         target.prev = null;
 50         target.next = oldHead;
 51         oldHead.prev = target;
 52         head = target;
 53     }
 54     
 55     public int get(int key) {
 56         if (!map.containsKey(key))
 57             return -1;
 58         Node current = map.get(key);
 59         // Move found node to head
 60         moveToHead(current);
 61         return current.getValue();
 62     }
 63     
 64     public void set(int key, int value) {
 65         if (map.containsKey(key)) {
 66             Node current = map.get(key);
 67             current.setValue(value);
 68             // Move found node to head
 69             moveToHead(current);
 70             
 71         } else {
 72             Node current = new Node(key, value);
 73             // Add new node to map
 74             map.put(key, current);
 75             
 76             // Check whether map size is bigger than capacity
 77             if (map.size() > capacity) {
 78                 // Move farest used element out
 79                 Node last = tail;
 80                 map.remove(last.getKey());
 81                 // Remove from list
 82                 if (map.size() == 1) {
 83                     head = current;
 84                     tail = current;
 85                 } else {
 86                     Node oldHead = head;
 87                     current.next = oldHead;
 88                     oldHead.prev = current;
 89                     head = current;
 90                     tail = tail.prev;
 91                     tail.next = null;
 92                 }
 93                 
 94             } else {
 95                 // Add new node to list
 96                 if (map.size() == 1) {
 97                     head = current;
 98                     tail = current;
 99                 } else {
100                     Node oldHead = head;
101                     current.next = oldHead;
102                     oldHead.prev = current;
103                     head = current;
104                 }
105             }
106         }
107     }
108 }