1. class Node {
    2.     public int key, val;
    3.     public Node next, prev;
    4.     public Node(int k, int v) {
    5.         this.key = k;
    6.         this.val = v;
    7.     }
    8. }
    10. class DoubleList {
    11.     private Node head, tail;
    12.     private int size;
    14.     public void addFirst(Node node) {
    15.         if (head == null) {
    16.             head = tail = node;
    17.         } else {
    18.             Node h = head;
    19.             h.prev = node;
    20.             node.next = h;
    21.             head = node;
    22.         }
    23.         size++;
    24.     }
    26.     public void remove(Node node) {
    27.         if (head == node && tail == node) {
    28.             head = null;
    29.             tail = null;
    30.         } else if (tail == node) {
    31.             node.prev.next = null;
    32.             tail = node.prev;
    33.             node.prev = null;
    34.         } else if (head == node) {
    35.             node.next.prev = null;
    36.             head = node.next;
    37.             node.next = null;
    38.         } else {
    39.             node.prev.next = node.next;
    40.             node.next.prev = node.prev;
    41.             node.next = null;
    42.             node.prev = null;
    43.         }
    44.         size--;
    45.     }
    47.     public Node removeLast() {
    48.         Node node = tail;
    49.         remove(tail);
    50.         return node;
    51.     }
    53.     public int size() {
    54.         return size;
    55.     }
    56. }
    59. class LRUCache {
    60.     private HashMap<Integer, Node> map;
    61.     private DoubleList doubleList;
    62.     private int cap;
    64.     public LRUCache(int capacity) {
    65.         this.cap = capacity;
    66.         map = new HashMap<>();
    67.         doubleList = new DoubleList();
    68.     }
    70.     public int get(int key) {
    71.         if (!map.containsKey(key))
    72.             return -1;
    73.         Node node = map.get(key);
    74.         int val = node.val;
    75.         doubleList.remove(node);
    76.         doubleList.addFirst(node);
    77.         return val;
    78.     }
    80.     public void put(int key, int val) {
    81.         Node x = new Node(key, val);
    82.         if (map.containsKey(key)) {
    83.             doubleList.remove(map.get(key));
    84.         } else {
    85.             if (cap == doubleList.size()) {
    86.                 Node last = doubleList.removeLast();
    87.                 map.remove(last.key);
    88.             }
    89.         }
    90.         doubleList.addFirst(x);
    91.         map.put(key, x);
    92.     }
    93. }