1+ class LRUCache {
2+
3+ private Map <Integer ,Node >cache ;
4+ private int capacity ;
5+
6+ private Node left ;
7+ private Node right ;
8+
9+ public LRUCache (int capacity ) {
10+ this .capacity =capacity ;
11+ cache =new HashMap <>();
12+
13+ //left = LRU , right = most recent
14+ this .left =new Node (0 ,0 );
15+ this .right =new Node (0 ,0 );
16+ this .left .next =this .right ;
17+ this .right .prev =this .left ;
18+
19+ }
20+
21+ public int get (int key ) {
22+
23+ if (cache .containsKey (key )){
24+ remove (cache .get (key ));
25+ insert (cache .get (key ));
26+ return cache .get (key ).val ;
27+
28+ }else {
29+ return -1 ;
30+ }
31+
32+ }
33+
34+ public void put (int key ,int value ) {
35+
36+ if (cache .containsKey (key )){
37+ remove (cache .get (key ));
38+ }
39+ cache .put (key ,new Node (key ,value ));
40+ insert (cache .get (key ));
41+
42+ if (cache .size () >capacity ){
43+ // remove from the list and delte the LRU from the hashmap
44+ Node lru =this .left .next ;
45+ remove (lru );
46+ cache .remove (lru .key );
47+
48+ }
49+
50+
51+ }
52+
53+ // remove node from list
54+ public void remove (Node node ) {
55+
56+ Node prev =node .prev ;
57+ Node next =node .next ;
58+
59+ prev .next =next ;
60+ next .prev =prev ;
61+ }
62+
63+ // insert node at right
64+ public void insert (Node node ) {
65+
66+ Node prev =this .right .prev ;
67+ Node next =this .right ;
68+
69+
70+ prev .next =node ;
71+ next .prev =node ;
72+
73+ node .next =next ;
74+ node .prev =prev ;
75+
76+
77+
78+ }
79+ private class Node {
80+ private int key ;
81+ private int val ;
82+
83+ Node next ;
84+ Node prev ;
85+
86+ public Node (int key ,int val ){
87+ this .key =key ;
88+ this .val =val ;
89+ }
90+ }
91+ }