Advertisement
Guest User

Grokking Newsletter 218

a guest
May 11th, 2022
95
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class LRUCache {
  2.  
  3. int capacity;
  4. int size;
  5.  
  6. Map<Integer, Node> table;
  7. Node dummyHead;
  8. Node dummyTail;
  9.  
  10. public LRUCache(int capacity) {
  11. this.capacity = capacity;
  12. this.size = 0;
  13.  
  14. table = new HashMap<Integer, Node>();
  15.  
  16. // Use dummy head, dummy tail to reduce checking null conditions.
  17. dummyHead = new Node();
  18. dummyTail = new Node();
  19.  
  20. dummyHead.next = dummyTail;
  21. dummyTail.prev = dummyHead;
  22. }
  23.  
  24. public int get(int key) {
  25. Node node = table.get(key);
  26.  
  27. if (node == null) {
  28. return -1;
  29. }
  30.  
  31. // node is most recently used value, so move to head of linked list
  32. moveToHead(node);
  33.  
  34. return node.value;
  35. }
  36.  
  37. public void put(int key, int value) {
  38. Node node = table.get(key);
  39.  
  40. if (node == null) {
  41. // if key doesn't exist, put new value node head of linked list
  42. Node newNode = new Node();
  43. newNode.key = key;
  44. newNode.value = value;
  45.  
  46. table.put(key, newNode);
  47. addNodeToHead(newNode);
  48.  
  49. ++size;
  50.  
  51. // evict least recently used item if current size is greater than capacity
  52. if (size > capacity) {
  53. Node tail = removeTail();
  54. table.remove(tail.key);
  55. --size;
  56. }
  57. } else {
  58. // if key exists, just update value
  59. node.value = value;
  60. moveToHead(node);
  61. }
  62. }
  63.  
  64. private void moveToHead(Node node) {
  65. removeNode(node);
  66. addNodeToHead(node);
  67. }
  68.  
  69. private void addNodeToHead(Node node) {
  70. node.next = dummyHead.next;
  71. node.prev = dummyHead;
  72.  
  73. dummyHead.next.prev = node;
  74. dummyHead.next = node;
  75. }
  76.  
  77. private Node removeTail() {
  78. Node ans = dummyTail.prev;
  79. removeNode(ans);
  80.  
  81. return ans;
  82. }
  83.  
  84. private void removeNode(Node node) {
  85. node.next.prev = node.prev;
  86. node.prev.next = node.next;
  87. }
  88.  
  89. // Doubly linked-list node
  90. class Node {
  91. int key;
  92. int value;
  93. Node prev;
  94. Node next;
  95. }
  96.  
  97. }
Advertisement
RAW Paste Data Copied
Advertisement