LRU Cache

[huimeich]

Linear time

public class LRUCache {
    private int capacity;
    private int size;
    public class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node (int key, int value) {
            this.key = key;
            this.value = value;
            prev = null;
            next = null;
        }
    }
    public Node head;
    public Node tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        Node temp = head;
        for (int i = 0; i < size; i ++){
            temp = temp.next;
            if (key == temp.key) {
                int value = temp.value;
                remove(temp);
                addFront(key,value);
                return value;
            }
        }
        return -1;
    }
    public void set(int key, int value) {
        Node temp = head;
        for (int i = 0; i < size; i++) {
            //System.out.println("setting key " + key + " value " + value);
            temp = temp.next;
            if (key == temp.key) {
                temp.value = value;
                return;
            }
        }
        if (size == capacity) {
            this.removeBack();
        }
        this.addFront(key, value);

    }

    private void addFront(int key, int value) {
        Node temp = new Node(key,value);
        temp.prev = head;
        temp.next = head.next;
        head.next.prev = temp;
        head.next = temp;
        size ++;
    }

    private void remove(Node temp) {
        temp.next.prev = temp.prev;
        temp.prev.next = temp.next;
        size --;
    }

    private void removeBack(){
        tail.prev.prev.next = tail;
        tail.prev = tail.prev.prev;
        size --;
    }
}

[huimeich]

Correct answer:

import java.util.HashMap;

/**
 * Created by huimei on 4/6/2016.
 */
public class LRUCache {
    private int capacity;
    private int size;
    public HashMap<Integer, Node> map;
    public class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node (int key, int value) {
            this.key = key;
            this.value = value;
            prev = null;
            next = null;
        }
    }
    public Node head;
    public Node tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.prev = head;
        map = new HashMap<Integer, Node>();
    }
    public int get(int key) {
        if (map.containsKey(key)){
            Node temp = map.get(key);
            remove(temp);
            addFront(key,temp.value);
            return temp.value;
        }
        return -1;
    }
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            Node temp = map.get(key);
            this.remove(temp);
        }
        if (size == capacity) {
            this.removeBack();
        }
        this.addFront(key, value);
    }

    private void addFront(int key, int value) {
        Node temp = new Node(key,value);
        temp.prev = head;
        temp.next = head.next;
        head.next.prev = temp;
        head.next = temp;
        size ++;
        map.put(key,temp);

    }

    private void remove(Node temp) {
        temp.next.prev = temp.prev;
        temp.prev.next = temp.next;
        size --;
        map.remove(temp.key);
    }

    private void removeBack(){
        map.remove(tail.prev.key);
        tail.prev.prev.next = tail;
        tail.prev = tail.prev.prev;
        size --;
    }
}