Problem Statement:
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise -1.
put(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.Follow up:
Could you do both operations in O(1) time complexity?
I have a Java implementation that utilizes Hashtable and LinkedList. I am looking for feedbacks on how to write better, more elegant code. Any suggestions on >style, simplicity, comments, etc., are welcome.
My code:
import java.util.Map;
import java.util.HashMap;
//Not thread safe!
class LRUCache {
private Map<Integer, Node> nodeMap;
private DoubleLinkedList lruList;
private int size;
private int capacity;
class Node {
private int key;
private int value;
private Node prev = null;
private Node next = null;
Node(int key, int value){
this.key = key;
this.value = value;
}
}
class DoubleLinkedList{
private Node head;
private Node tail;
DoubleLinkedList(){
head = null;
tail = null;
}
void remove(Node node){
if(node.prev == null){
assert head == node;
head = node.next;
}else{
node.prev.next = node.next;
}
if(node.next == null){
assert tail == node;
tail = node.prev;
}else{
node.next.prev = node.prev;
}
node.prev = node.next = null;
}
void addToHead(Node node){
if(head == null){
assert tail == null;
head = tail = node;
return;
}
node.next = head;
head.prev = node;
head = node;
}
Node removeFromTail(){
if(tail == null) throw new IllegalStateException("List is empty, cannot remove from it");
Node removed = tail;
Node new_tail = tail.prev;
if(new_tail == null){
head = tail = null;
removed.prev = removed.next = null;
return removed;
}
new_tail.next = null;
tail = new_tail;
removed.prev = removed.next = null;
return removed;
}
}
public LRUCache(int capacity) {
assert capacity > 0;
this.nodeMap = new HashMap<Integer, Node>();
this.lruList = new DoubleLinkedList();
this.size = 0;
this.capacity = capacity;
}
public int get(int key) {
Node node = nodeMap.get(key);
if(node == null) return -1;
assert node.key == key;
moveToMRU(node);
return node.value;
}
public void put(int key, int value) {
//first see if key already exists in cahce
Node node = nodeMap.get(key);
if(node != null){
node.value = value;
moveToMRU(node);
return;
}
//have to insert
if(size == capacity) evict();
node = new Node(key, value);
nodeMap.put(key, node);
//newly inserted item is put to the MRU end
lruList.addToHead(node);
size += 1;
}
private void moveToMRU(Node node){
lruList.remove(node);
lruList.addToHead(node);
}
private void evict(){
Node node = lruList.removeFromTail();
assert node != null;
nodeMap.remove(node.key);
size -= 1;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
