146. LRU Cache

 1 public class LRUCache {
 2     class Node {
 3         int key;
 4         int value;
 5         Node pre;
 6         Node post;
 7     }
 8     
 9     private int count;
10     private int capacity;
11     private Map<Integer, Node> map;
12     private Node head, tail;
13     
14     public LRUCache(int capacity) {
15         this.capacity = capacity;
16         this.count = 0;
17         map = new HashMap<Integer, Node>();
18         head = new Node();
19         head.pre = null;
20         tail = new Node();
21         head.post = tail;
22         tail.pre = head;
23         tail.post = null;
24     }
25     
26     private void removeNode(Node node) {
27         Node preNode = node.pre;
28         Node postNode = node.post;
29         preNode.post = postNode;
30         postNode.pre = preNode;
31     }
32     
33     private void addNode(Node node) {
34         node.pre = head;
35         node.post = head.post;
36         head.post.pre = node;
37         head.post = node;
38     }
39     
40     private Node poll() {
41         Node preNode = tail.pre;
42         this.removeNode(preNode);
43         return preNode;
44     }
45     
46     private void moveNodeToHead(Node node) {
47         this.removeNode(node);
48         this.addNode(node);
49     }
50     
51     public int get(int key) {
52         Node node = map.get(key);
53         if(node != null) {
54             this.moveNodeToHead(node);
55             return node.value;
56         }
57         return -1;
58     }
59     
60     public void set(int key, int value) {
61         if(this.map.containsKey(key)) {
62             Node node = map.get(key);
63             node.value = value;
64             this.moveNodeToHead(node);
65         } else {
66             Node node = new Node();
67             node.key = key;
68             node.value = value;
69             this.map.put(key, node);
70             count++;
71             this.addNode(node);
72             if(count > capacity) {
73                 Node tailNode = this.poll();
74                 this.map.remove(tailNode.key);
75                 count--;
76             } 
77         }
78     }
79 }