Created
March 10, 2017 11:20
-
-
Save CoXier/eba20a7927c069d7b857c17d3827cbda to your computer and use it in GitHub Desktop.
A simple solution for LRUCache
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
import java.util.HashMap; | |
/** | |
* Created by coxier on 17-3-10. | |
*/ | |
public class LRUCache<K,V> { | |
private final class Node { | |
Node next; | |
Node pre; | |
K key; | |
V value; | |
public Node(K key, V value) { | |
this.key = key; | |
this.value = value; | |
} | |
public Node(){ | |
} | |
} | |
private HashMap<K, Node> nodeMap; | |
private Node head; | |
private Node tail; | |
private int cap; | |
public LRUCache(int capacity) { | |
nodeMap = new HashMap<>(capacity); | |
cap = capacity; | |
head = new Node(); | |
tail = new Node(); | |
head.pre = null; | |
head.next = tail; | |
tail.next = null; | |
tail.pre = head; | |
} | |
private void deleteNode(Node node) { | |
Node next = node.next; | |
Node pre = node.pre; | |
next.pre = pre; | |
pre.next = next; | |
} | |
private void addNodeToHead(Node node) { | |
Node realHead = head.next; | |
realHead.pre = node; | |
head.next = node; | |
node.next = realHead; | |
node.pre = head; | |
} | |
public V get(K key) { | |
Node node = nodeMap.get(key); | |
if (node != null) { | |
deleteNode(node); | |
addNodeToHead(node); | |
return node.value; | |
} | |
throw new IllegalArgumentException("No value match this key"); | |
} | |
public void put(K key, V value) { | |
Node node = nodeMap.get(key); | |
if (node != null) { | |
node.value = value; | |
deleteNode(node); | |
addNodeToHead(node); | |
return; | |
} else if (nodeMap.size() == cap) { | |
nodeMap.remove(tail.pre.key); | |
deleteNode(tail.pre); | |
} | |
node = new Node(key, value); | |
addNodeToHead(node); | |
nodeMap.put(key, node); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment