Created
February 27, 2017 09:45
-
-
Save eduzol/32692ffce09727ee7257ef848693ef20 to your computer and use it in GitHub Desktop.
LRUCache implemented in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.zola.algorithms; | |
import java.util.HashMap; | |
public class LRUCache{ | |
public static void main(String... args){ | |
LRUCache cache = new LRUCache( 2 /* capacity */ ); | |
cache.put(1, 1); | |
System.out.println(cache); | |
cache.put(2, 2); | |
System.out.println(cache); | |
cache.get(1); // returns 1 | |
System.out.println(cache); | |
cache.put(3, 3); // evicts key 2 | |
System.out.println(cache); | |
System.out.println(cache.get(2)); // returns -1 (not found) | |
System.out.println(cache); | |
cache.put(4, 4); // evicts key 1 | |
System.out.println(cache); | |
System.out.println(cache.get(1)); // returns -1 (not found) | |
System.out.println(cache); | |
System.out.println(cache.get(3)); // returns 3 | |
System.out.println(cache); | |
System.out.println(cache.get(4)); // returns 4 | |
System.out.println(cache); | |
} | |
class Node { | |
public int key; | |
public int value; | |
public Node prev; | |
public Node next; | |
public Node(int key, int value , Node prev, Node next){ | |
this.key = key; | |
this.value = value; | |
this.prev = prev; | |
this.next = next; | |
} | |
public String toString(){ | |
StringBuilder builder = new StringBuilder(); | |
builder.append("{"+this.key +"=>" +this.value+"}"); | |
return builder.toString(); | |
} | |
} | |
private int capacity = 0; | |
private HashMap<Integer, Node> cache = new HashMap<Integer, Node>(); | |
private Node head; | |
private Node tail; | |
private int size = 0; | |
public LRUCache(int capacity) { | |
this.capacity = capacity; | |
this.head = new Node(0 ,0, null, null ); | |
this.tail = new Node(0 ,0, head, null ); | |
this.head.next = tail; | |
} | |
private int size(){ | |
return size; | |
} | |
private Node addBetween(int key, int value , Node prev, Node next){ | |
Node node = new Node(key, value, prev, next); | |
prev.next = node; | |
next.prev = node; | |
size++; | |
return node; | |
} | |
private Node remove(Node node){ | |
Node prev = node.prev; | |
Node next = node.next; | |
next.prev = prev; | |
prev.next = next; | |
size--; | |
return node; | |
} | |
private Node addFirst(int key, int value ){ | |
Node added = addBetween( key, value, this.head, this.head.next); | |
return added; | |
} | |
private Node removeLast( ){ | |
Node removed = remove ( this.tail.prev ); | |
return removed; | |
} | |
public int get(int key) { | |
Node entry = cache.get(key); | |
if ( entry != null ){ | |
//move to top of the queue | |
remove(entry); | |
addFirst(entry.key , entry.value); | |
return entry.value; | |
}else{ | |
return -1; | |
} | |
} | |
public void put(int key, int value) { | |
Node entry = cache.get(key); | |
if ( entry == null ){ | |
Node added = addFirst(key, value); | |
cache.put(key,added); | |
if ( size() > capacity ){ | |
Node removed = removeLast(); | |
cache.remove(removed.key); | |
} | |
}else{ | |
remove(entry); | |
Node added = addFirst(key, value); | |
cache.put(key, added); | |
} | |
} | |
@Override | |
public String toString(){ | |
StringBuilder builder = new StringBuilder(); | |
Node nav = this.head; | |
builder.append("["); | |
while(nav.next != null && nav.next != this.tail ){ | |
nav = nav.next; | |
builder.append(nav); | |
if ( nav.next != this.tail ){ | |
builder.append(","); | |
} | |
} | |
builder.append("]"); | |
return builder.toString(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment