Created
November 5, 2019 15:08
-
-
Save chenminhua/7921b8802a57fcc8a9f09a14469f0538 to your computer and use it in GitHub Desktop.
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
public class LRUCache { | |
class DLinkedNode { | |
int key; | |
int value; | |
DLinkedNode prev; | |
DLinkedNode next; | |
} | |
private DLinkedNode head, tail; | |
private HashMap<Integer, DLinkedNode> cache = new HashMap<>(); | |
private int size; | |
private int capacity; | |
private void addNode(DLinkedNode node) { | |
/*always add node right after head*/ | |
node.prev = head; | |
node.next = head.next; | |
head.next = node; | |
node.next.prev = node; | |
} | |
private void removeNode(DLinkedNode node) { | |
/*remove an existing node*/ | |
DLinkedNode prev = node.prev; | |
DLinkedNode next = node.next; | |
prev.next = next; | |
next.prev = prev; | |
} | |
private void moveToHead(DLinkedNode node) { | |
removeNode(node); | |
addNode(node); | |
} | |
private DLinkedNode popTail() { | |
DLinkedNode res = tail.prev; | |
removeNode(res); | |
return res; | |
} | |
public LRUCache(int capacity) { | |
this.size = 0; | |
this.capacity = capacity; | |
head = new DLinkedNode(); | |
tail = new DLinkedNode(); | |
head.next = tail; | |
tail.prev = head; | |
} | |
public int get(int key) { | |
DLinkedNode node = cache.get(key); | |
if (node == null) { | |
return -1; | |
} | |
moveToHead(node); | |
return node.value; | |
} | |
public void put(int key, int value) { | |
DLinkedNode node = cache.get(key); | |
if (node == null) { | |
DLinkedNode newNode = new DLinkedNode(); | |
newNode.key = key; | |
newNode.value = value; | |
cache.put(key, newNode); | |
addNode(newNode); | |
size++; | |
if (size > capacity) { | |
DLinkedNode tail = popTail(); | |
cache.remove(tail.key); | |
--size; | |
} | |
} else { | |
node.value = value; | |
moveToHead(node); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment