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.
1 public class LRUCache { 2 private HashMap<Integer,Element> map; 3 private int capacity; 4 private int used; 5 public class Element{ 6 int value, key; 7 Element next, pre; 8 public Element(int key, int value){ 9 this.value = value; 10 this.key = key; 11 next = null; 12 pre = null; 13 } 14 } 15 private Element header; 16 public LRUCache(int capacity) { 17 map = new HashMap<Integer,Element>(); 18 this.capacity = capacity; 19 used = 0; 20 header = new Element(-1,-1); 21 header.pre = header; 22 header.next = header; 23 } 24 private Element add(Element n){ 25 //add to the tail of doublelinkedlist, header is both the header and tail of list 26 header.pre.next = n; 27 n.next = header; 28 n.pre = header.pre; 29 header.pre = n; 30 used ++; 31 return n; 32 } 33 private Element remove(Element n){ 34 //remove certain element 35 n.pre.next = n.next; 36 n.next.pre = n.pre; 37 n.pre = null; 38 n.next = null; 39 used --; 40 return n; 41 } 42 public int get(int key) { 43 if(map.containsKey(key)){ 44 Element tmp = map.get(key); 45 tmp.pre.next = tmp.next; 46 tmp.next.pre = tmp.pre; 47 remove(tmp);//这个要先remove 才能保证used的值是正确的。 48 Element add = add(tmp); 49 map.put(key, add); 50 return map.get(key).value; 51 } 52 return -1; 53 } 54 public void set(int key, int value) { 55 if(key < 1) return; 56 if(map.containsKey(key)){ 57 Element tmp = map.get(key); 58 tmp = remove(tmp); 59 }else if(used == capacity){ 60 Element lruKey = remove(header.next); 61 map.remove(lruKey.key); 62 } 63 Element add = add(new Element(key, value)); 64 map.put(key, add); 65 } 66 }
第二遍：
1 public class LRUCache { 2 public class Element{ 3 int key; 4 int value; 5 Element prev, next; 6 public Element(int key, int value){ 7 this.key = key; 8 this.value = value; 9 this.prev = null; 10 this.next = null; 11 } 12 } 13 private int capacity; 14 private int used; 15 private Element header; 16 private HashMap<Integer, Element> map; 17 18 public LRUCache(int capacity) { 19 this.capacity = capacity; 20 this.used = 0; 21 this.map = new HashMap<Integer, Element>(); 22 this.header = new Element(-1, -1);//header for double linked list 23 header.prev = header; 24 header.next = header; 25 } 26 27 private Element add(Element node){//add to the tail 28 used ++; 29 node.next = header; 30 node.prev = header.prev; 31 header.prev.next = node; 32 header.prev = node; 33 return node; 34 } 35 36 private Element remove(Element node){//remove node in any position 37 used --; 38 node.prev.next = node.next; 39 node.next.prev = node.prev; 40 node.next = null; 41 node.prev = null; 42 return node; 43 } 44 45 public int get(int key) { 46 if(map.containsKey(key)){ 47 Element tmp = add(remove(map.get(key))); 48 map.put(key, tmp); 49 return tmp.value; 50 } 51 return -1; 52 } 53 54 public void set(int key, int value) { 55 if(used == capacity || map.containsKey(key)){ 56 Element tmp = (map.containsKey(key) ? map.get(key) : header.next);// 这里只能是判断map.containsKey,因为可能出现 map.containsKey 和 used == capaity 同时满足的情况！ 57 map.remove(tmp.key); 58 remove(tmp); 59 } 60 Element tmp = add(new Element(key, value)); 61 map.put(key, tmp); 62 } 63 }