1. The cache is implemented by a doubly linked list and a hash map.
2. The cache has fixed capacity.
3. The constructor initialize a cache with head (-1, -1 )links to tail (-1, -1).
4. All nodes are inserted between head and tail and stored in the hash map with key equals to its key value.
5. Get the node from the map takes O(1) time, then moves the node before tail since it's the most recently accessed node.
6. If the map contains the node that needs to be set, alter the value of the node. Otherwise insert the node before the tail and remove the node next to head if the capacity of the cache is full.
public class LRUCache { private class Node { Node prev; Node next; int key; int val; public Node (int key, int val) { this.key = key; this.val = val; this.prev = null; this.next = null; } } private int capacity; private HashMaphm = new HashMap (); private Node head = new Node(-1, -1); private Node tail = new Node(-1, -1); public LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } public int get(int key) { if (!hm.containsKey(key)) return -1; Node curr = hm.get(key); curr.prev.next = curr.next; curr.next.prev = curr.prev; MoveToTail(curr); return hm.get(key).val; } public void set(int key, int value) { if (get(key) != -1) { hm.get(key).val = value; return; } if (hm.size() == capacity) { hm.remove(head.next.key); head.next = head.next.next; head.next.prev = head; } Node newNode = new Node(key, value); hm.put(key, newNode); MoveToTail(newNode); } private void MoveToTail(Node node) { node.prev = tail.prev; tail.prev = node; node.next = tail; node.prev.next = node; } }
No comments:
Post a Comment