• 1

• 157
• 8

• 157
• 8

Problem Statement:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

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);
 */