lintcode-LRU缓存策略

使用双链表和hashtable数据结构，双链表负责更新最近访问的数据节点到头部，hashtable负责查找、修改或添加、删除

import java.util.*;

public class Solution {
    private int capacity;
    private int currentSize;
    private Hashtable nodes;
    private CacheNode first;
    private CacheNode last;
    
    class CacheNode {
        CacheNode prev;
        CacheNode next;
        int key;
        int value;
        
        CacheNode() { 
            this.prev = this.next = null;
        }
    };

    // @param capacity, an integer
    public Solution(int capacity) {
        // write your code here
        this.capacity = capacity;
        this.currentSize = 0;
        this.nodes = new Hashtable(capacity);
        this.first = null;
        this.last = null;
    }

    // @return an integer
    public int get(int key) {
        // write your code here
        CacheNode node = (CacheNode)nodes.get(key);
        if(node != null) {
            moveToHead(node);
            return node.value;
        }
        
        return -1;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        // write your code here
        CacheNode node = (CacheNode)nodes.get(key);
        
        if(node == null) {
            if(currentSize < capacity) {
                currentSize++;
            } else {
                if(last != null) {
                    nodes.remove(last.key);
                    removeLast();
                }
            }
            
            node = new CacheNode();
        }
        
        node.key = key;
        node.value = value;
        moveToHead(node);
        nodes.put(key, node);
    }
    
    
    public void moveToHead(CacheNode node) {
        if(first == node) {
            return;
        }
        
        if(node.prev != null) {
            node.prev.next = node.next;
        }
        
        if(node.next != null) {
            node.next.prev = node.prev;
        }
        
        if(last == node) {
            last = node.prev;
        }
        
        if(first != null) {
            node.next = first;
            first.prev = node;
        }
        
        first = node;
        node.prev = null;
        
        if(last == null) {
            last = first;
        }
        
    }
    
    public void removeLast() {
        if(first == last) {
            first = last = null;
        } else {
            if(last.prev != null) {
                last.prev.next = null;
                last = last.prev;
            }
        }
    }
}