Implement LRU Cache

class LRUCache { int capacity = 0; Map<Integer,Integer> map; public LRUCache(int capacity) { map= new LinkedHashMap<>(); this.capacity = capacity; } public int get(int key) { int val = -1; if(map.containsKey(key)) { val = map.get(key); map.remove(key); map.put(key,val); } return val; } public void put(int key, int value) { if(map.containsKey(key)) map.remove(key); if(map.size() == this.capacity) map.remove(map.entrySet().iterator().next().getKey()); map.put(key,value); } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */ 

class LRUCache { DLinkedList head = null; DLinkedList tail = null; int capacity = 0; Map<Integer, DLinkedList> map = new HashMap<>(); public LRUCache(int capacity) { this.capacity = capacity; } public int get(int key) { DLinkedList node = map.getOrDefault(key, null); if (node == null) return -1; // Move the accessed node to the end (most recently used) remove(node); addToTail(node); return node.value; } public void put(int key, int value) { if (map.containsKey(key)) { // Key exists; update value and move to the end DLinkedList node = map.get(key); node.value = value; remove(node); addToTail(node); } else { // Key doesn't exist; create a new node if (map.size() == capacity) { // Evict the least recently used (head node) map.remove(head.key); remove(head); } DLinkedList newNode = new DLinkedList(key, value); addToTail(newNode); map.put(key, newNode); } } private void remove(DLinkedList node) { if (node.prev != null) { node.prev.next = node.next; } else { // Node is head head = node.next; } if (node.next != null) { node.next.prev = node.prev; } else { // Node is tail tail = node.prev; } node.prev = null; node.next = null; } private void addToTail(DLinkedList node) { if (tail == null) { // List is empty head = tail = node; } else { // Add to end of the list tail.next = node; node.prev = tail; tail = node; } } public void traverse() { DLinkedList n = head; while (n != null) { System.out.print(n.prev + "<--[" + n.key + "," + n.value + "]-->" + n.next); n = n.next; } System.out.println(); } } class DLinkedList { DLinkedList prev; DLinkedList next; int key; int value; public DLinkedList(int k, int v) { this.key = k; this.value = v; } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */