LRU Cache

貌似最直接的方法还是用自己实现的LinkedList来做，需要注意的是能不能根据Node找到map的key值 --- 为了达到这一目的，我决定在Node 中同时存储key / value .

1. 
   
2. import java.util.*;
   
3. 
   
4. class ListNode {
   
5.     int key, val;
   
6.     ListNode prev, next;
   
7.     public ListNode(int k, int v) {
   
8.         key = k;
   
9.             val = v;
   
10.     }
    
11. }
    
12. 
    
13. public class LRUCache {
    
14.     static int size, maxSize;
    
15.     ListNode head, tail;
    
16.     HashMap<Integer, ListNode> map;
    
17.     // initialize LRUCache in constructor
    
18.     public LRUCache(int capacity) {
    
19.         size = 0;
    
20.         maxSize = capacity;
    
21.         map = new HashMap<>();
    
22.         head = new ListNode(0, 0);
    
23.         tail = new ListNode(0, 0);
    
24.         head.next = tail;
    
25.         tail.prev = head;
    
26.     }
    
27.    
    
28.     public int get(int key) {
    
29.         if (map.containsKey(key)) {
    
30.             ListNode node = map.get(key);
    
31.             moveToFirst(node);
    
32.             return node.val;
    
33.         } else {
    
34.             return -1;
    
35.         }
    
36.     }
    
37.    
    
38.     public void set(int key, int value) {
    
39.         if (maxSize == 0) {
    
40.             return;
    
41.         }
    
42.         if (map.containsKey(key)) {
    
43.             ListNode node = map.get(key);
    
44.             node.val = value;
    
45.             moveToFirst(node);
    
46.         } else {
    
47.             // this key doesn't exsit in the map's keySet;
    
48.             
    
49.             // if the cache is full, exclude the last one node;
    
50.             if (size == maxSize) {
    
51.                     ListNode toBeDeleted = tail.prev;
    
52.                 map.remove(toBeDeleted.key);
    
53.                 tail.prev = tail.prev.prev;
    
54.                 tail.prev.next = tail;
    
55.                 size--;
    
56.             }   
    
57.             ListNode oldNext = head.next;
    
58.             ListNode newNext = new ListNode(key, value);
    
59.             head.next = newNext;
    
60.             newNext.next = oldNext;
    
61.             oldNext.prev = newNext;
    
62.             newNext.prev = head;
    
63.             map.put(key, newNext);
    
64.             size++;
    
65.         }
    
66. 
    
67. 
    
68.     }
    
69.     private void moveToFirst(ListNode node) {
    
70.         // get the node out of list
    
71.         ListNode p = node.prev;
    
72.         ListNode n = node.next;
    
73.         p.next = n;
    
74.         n.prev = p;
    
75.         // put node at the head of list;
    
76.         head.next.prev = node;
    
77.         node.prev = head;
    
78.         node.next = head.next;
    
79.         head.next = node;
    
80.     }
    
81.         public static void main(String[] args) {
    
82.                 LRUCache cache = new LRUCache(1);
    
83.                 cache.set(2, 1);
    
84.                 System.out.println(cache.get(2));
    
85.                 cache.set(3, 2);
    
86.                 System.out.println(cache.get(2));
    
87.                 System.out.println(cache.get(3));
    
88.         }
    
89. 
    
90. }

复制代码