LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);    // 返回 1
    cache.put(3, 3);  // 該操作會使得密鑰 2 作廢

import java.io.*;
import java.util.HashMap;

public class test {

  public static void main(String args[]) throws IOException {

    LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);    // 返回 1
    cache.put(3, 3);  // 該操作會使得密鑰 2 作廢
    cache.get(2);    // 返回 -1 (未找到)
    cache.put(4, 4);  // 該操作會使得密鑰 1 作廢
    cache.get(1);    // 返回 -1 (未找到)
    cache.get(3);    // 返回 3
    cache.get(4);    // 返回 4
  }
}

/**
 * 設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put
 */
class LRUCache {

  private HashMap<Integer,LinkedNode> cache = new HashMap();//方便通過key快速定位結(jié)點(diǎn)
  private int size;
  private int capacity;
  private LinkedNode head,tail;
  class LinkedNode{
    int key;
    int value;
    LinkedNode pre;
    LinkedNode next;
  }
  public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;
    head = new LinkedNode();
    tail = new LinkedNode();
    head.next = tail;
    tail.pre = head;
  }

  /**
   * 移除節(jié)點(diǎn)
   * @param node
   */
  private void removeNode(LinkedNode node) {
    LinkedNode preNode = node.pre;
    LinkedNode nextNode = node.next;
    preNode.next = nextNode;
    nextNode.pre = preNode;
  }

  /**
   * 添加節(jié)點(diǎn)到頭部
   * @param node
   */
  private void addNode(LinkedNode node) {
    node.pre = head;
    node.next = head.next;
    head.next.pre = node;
    head.next = node;
  }

  /**
   * 將節(jié)點(diǎn)移動到頭部
   * @param node
   */
  private void moveToHead(LinkedNode node) {
    removeNode(node);
    addNode(node);
  }

  /**
   * 獲取數(shù)據(jù)
   * @param key
   * @return
   */
  public int get(int key) {
    LinkedNode node = cache.get(key);
    if(node != null) {
      moveToHead(node);
    }else{
      return -1;
    }
    return node.value;
  }

  /**
   * 寫入數(shù)據(jù)
   * @param key
   * @param value
   */
  public void put(int key, int value) {
    LinkedNode node = cache.get(key);
    //存在
    if(node != null) {
      node.value = value;//可能更新數(shù)據(jù)
      moveToHead(node);
    }
    //不存在
    else{
      LinkedNode newNode = new LinkedNode();
      newNode.key = key;
      newNode.value = value;
      cache.put(key,newNode);//更新Map
      addNode(newNode);//添加結(jié)點(diǎn)到頭部
      size++;//更新結(jié)點(diǎn)數(shù)
      if(size > capacity) {//如果結(jié)點(diǎn)數(shù)超過容量大小
        LinkedNode tailPre = tail.pre;
        cache.remove(tailPre.key);//更新Map
        removeNode(tailPre);//刪除最后一個(gè)結(jié)點(diǎn)（尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)）
        size--;
      }
    }
  }
}