• LRU Cache

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
* get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
* set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution:
1. public class LRUCache {
2. 3. int capacity;
4. Map map;
5. ListNode head;
6. ListNode tail;
7. 8. public LRUCache(int cap) {
9. capacity = cap;
10. map = new HashMap<>();
11. head = new ListNode(0, 0);
12. tail = new ListNode(0, 0);
13. head.next = tail;
14. tail.prev = head;
15. }
16. 17. public int get(int key) {
18. if (!map.containsKey(key)) {
19. return -1;
20. }
21. 22. ListNode node = map.get(key);
23. promote(node);
24. return node.val;
25. }
26. 27. public void set(int key, int val) {
28. ListNode node;
29. 30. if (map.containsKey(key)) {
31. node = map.get(key);
32. promote(node);
33. node.val = val;
34. return;
35. }
36. 37. if (map.size() == capacity) {
38. ListNode last = tail.prev;
39. map.remove(last.key);
40. remove(last);
41. }
42. 43. node = new ListNode(key, val);
44. map.put(key, node);
45. insert(node);
46. }
47. 48. void remove(ListNode node) {
49. node.prev.next = node.next;
50. node.next.prev = node.prev;
51. }
52. 53. void insert(ListNode node) {
54. node.prev = head;
55. node.next = head.next;
56. head.next.prev = node;
57. head.next = node;
58. }
59. 60. void promote(ListNode node) {
61. remove(node);
62. insert(node);
63. }
64. 65. class ListNode {
66. int key;
67. int val;
68. ListNode prev = null;
69. ListNode next = null;
70. 71. public ListNode(int k, int v) {
72. key = k;
73. val = v;
74. }
75. }
76. 77. }