Efficient LRU Cache in Java
Updated on Feb 17 2018 at 04:25 UTC
DISCLAIMER : Expressed views on this blog are my own.
Fun fun stuff to do in lintcode. I mean we can always incur a linear traversal using a LinkedList if one wanted a simple way to do LRU, but why not challenge myself.public class LRUCache { public class LRUNode { Integer key; Integer data; LRUNode prev; LRUNode next; public LRUNode(int key, int data) { this.key = key; this.data = data; } } LRUNode head; LRUNode tail; Map nodeMap = new HashMap(); int maxCap; /* * @param capacity: An integer */public LRUCache(int capacity) { // do intialization if necessary this.maxCap = capacity; } /* * @param key: An integer * @return: An integer */ public int get(int key) { // write your code here LRUNode node = nodeMap.get(key); if(node != null) { this.remove(node); this.push(node); return node.data; } return -1; } /* * @param key: An integer * @param value: An integer * @return: nothing */ public void set(int key, int value) { // write your code here if(nodeMap.containsKey(key)) { LRUNode oldNode = this.nodeMap.get(key); this.remove(oldNode); } LRUNode node = new LRUNode(key, value); this.push(node); if(nodeMap.size() > this.maxCap) { this.removeOld(); } } private void push(LRUNode newHead) { if(this.head != null) { newHead.prev = null; newHead.next = this.head; this.head.prev = newHead; } if(this.tail == null) { this.tail = newHead; } this.head = newHead; this.nodeMap.put(newHead.key, newHead); } private void removeOld() { if(this.tail == null) { return; } this.remove(this.tail); } private void remove(LRUNode node) { if(node.prev != null) { node.prev.next = node.next; } if(node.next != null) { node.next.prev = node.prev; } if(node.equals(this.head)) { this.head = node.next; } if(node.equals(this.tail)) { this.tail = node.prev; } node.next = null; node.prev = null; this.nodeMap.remove(node.key); } }
You just read "Efficient LRU Cache in Java ". Please share if you liked it!
You can read more recent posts here .