Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
LRU cache - Using doubly linked list (Fast!)
//'main' method must be in a class 'Rextester'. //Compiler version 1.8.0_111 import java.util.*; import java.lang.*; class Node{ int key; int val; Node prev; Node next; public Node(int key,int val){ this.key = key; this.val = val; this.next = null; this.prev = null; } } class LRUCache{ Map<Integer,Node> mp = new HashMap<Integer,Node>(); Node head,tail; int capacity; public LRUCache(int capacity) { this.capacity = capacity; head = new Node(0,0); tail = new Node(0,0); head.next = tail; tail.prev = head; } public int get(int key) { if(!mp.containsKey(key)) return -1; Node node = mp.get(key); remove(node); add(node); return node.val; } public void put(int key, int value) { if(mp.containsKey(key)){ remove(mp.get(key)); } Node newNode = new Node(key,value); add(newNode); mp.put(key,newNode); if(mp.size()>capacity){ Node node = head.next; remove(node); mp.remove(node.key); } } public void add(Node node){ Node prev = tail.prev; prev.next = node; node.prev = prev; node.next = tail; tail.prev = node; } public void remove(Node node){ Node prev = node.prev; Node next = node.next; prev.next = next; next.prev = prev; } public void printDS(){ Node node = head; while(node!=null){ System.out.print(node.key+":"+node.val+"->"); node = node.next; } } } class Rextester { public static void main(String args[]) { System.out.println("Hello, World!"); LRUCache obj = new LRUCache(2); obj.put(1,1); obj.put(2,2); System.out.println(obj.get(1)); obj.put(3,3); System.out.println(obj.get(2)); obj.printDS(); } }
run
|
edit
|
history
|
help
0
Max palindrome string
or You Over the hill
word Ladder
Pattern1
Java programs
Hi Hypotaneous
dfkbzhfvjahfjh
Random and count of even numbers (ver. 2)
SalesmenEarnings
doubt