@@ -0,0 +1,2800 @@
+public class LRUCache %7B%0A  public class LinkedListNode %7B%0A    LinkedListNode prev;%0A    LinkedListNode next;%0A    int element;%0A    int key;%0A%0A    public LinkedListNode(int key, int t) %7B%0A      this.element = t;%0A      this.key = key;%0A      this.prev = this.next = null;%0A    %7D%0A  %7D%0A%0A  HashMap%3CInteger, LinkedListNode%3E map;%0A  LinkedListNode head;%0A  LinkedListNode tail;%0A  int size;%0A  int capacity;%0A%0A  public LRUCache(int capacity) %7B%0A    map = new HashMap%3CInteger, LinkedListNode%3E();%0A    this.size = 0;%0A    this.capacity = capacity;%0A  %7D%0A%0A  public int get(int key) %7B%0A    LinkedListNode node = this.map.get(key);%0A%0A    if (node == null) return -1;%0A%0A    this.update(node);%0A    return node.element;%0A  %7D%0A%0A  public void put(int key, int value) %7B%0A    if (this.head == null) %7B%0A      this.tail = this.head = new LinkedListNode(key, value);%0A      this.map.put(key, this.head);%0A      this.size ++;%0A      return;%0A    %7D%0A%0A    // Check for duplicates%0A    LinkedListNode node = this.map.get(key);%0A    if (node == null) %7B%0A      // If the key does not exist in the map.%0A      if (this.size %3E= this.capacity) %7B%0A        // Evict the least recently used node (the tail of the list).%0A        LinkedListNode tailNode = this.tail;%0A        if (tailNode.prev != null) tailNode.prev.next = null;%0A        this.tail = tailNode.prev;%0A%0A        // Remove the node from the map as well.%0A        this.map.remove(tailNode.key);%0A        this.size--;%0A      %7D%0A      LinkedListNode newNode = new LinkedListNode(key, value);%0A      this.update(newNode);%0A%0A      // Add the node to the map under the key.%0A      this.map.put(key, newNode);%0A      this.size ++;%0A      return;%0A    %7D%0A    node.element = value;%0A%0A    // The key is already in the map.%0A    // Update the value and move the node to the head of the list.%0A    this.update(node);%0A  %7D%0A%0A  private void update(LinkedListNode node) %7B%0A    // If the node is the head node, then return.%0A    if (node == this.head) return;%0A%0A    // If there is only 1 node in the list.%0A    else if (this.head == this.tail) %7B%0A      node.next = this.tail;%0A      this.tail.prev = node;%0A      this.head = node;%0A      return;%0A    %7D%0A%0A    LinkedListNode prevNode = node.prev;%0A%0A    // If the node does not exist in the list, then add as the head (new node).%0A    if (prevNode == null) %7B%0A      node.next = this.head;%0A      this.head.prev = node;%0A      this.head = node;%0A      return;%0A    %7D%0A%0A    // If the node that is being updated is the tail, then we must set a new tail.%0A    if (this.tail == node) %7B%0A      prevNode.next = null;%0A      this.tail = prevNode;%0A    %7D else %7B%0A      // Otherwise, remove the node from the list.%0A      prevNode.next = node.next;%0A      node.next.prev = prevNode;%0A    %7D%0A%0A    // Now add the node to the front%0A    node.prev = null;%0A    node.next = this.head;%0A    this.head.prev = node;%0A    this.head = node;%0A  %7D%0A%7D%0A

Add lru cache in java