Java Solution: Hash Table + Doubly Linked List


  • 0

    public class LRUCache {

    static class Node {
        int key;
        int val;
        Node prev;
        Node next;
        
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
        
        void update(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    private int capacity;
    private Node head;
    private Node tail;
    private Map<Integer, Node> map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<Integer, Node>();
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        remove(node);
        append(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        Node node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.val = value;
            remove(node);
        } else if (map.size() < capacity) {
            node = new Node(key, value);   
        } else {
            node = tail;
            remove(node);
            node.update(key, value);
        }
        append(node);
    }
    
    private Node remove(Node node) {
        map.remove(node.key);
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (node == head) {
            head = node.next;
        }
        if (node == tail) {
            tail = node.prev;
        }
        node.prev = node.next = null;
        return node;
    }
    
    private Node append(Node node) {
        map.put(node.key, node);
        if (head == null) {
            head = tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
        return node;
    }
    

    }

    /**

    • 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);
      */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.