See http://blog.csdn.net/hexinuaa/article/details/6630384

Node<T>
{
 T data;
 Node<T> next;
 Node<T> pre;
}

Node<T> swapToHead(Node<T> head, Node<T> n)
{
  if (n == head)
    return n;
    
  Node<T> temp = n.next;
  n.next = temp;
  if (temp != null) temp.pre = n.pre;
  n.pre = null;
  n.next = head;
  return n;
}


class LRU<K, T>
{
  private Map<K, Node<T>> map;
  private Node<T> head;
  private Node<T> tail;
  int size;
  
  T search(K key)
  {
    Node<T> n = map.get(key);
    if (n != null)
    {
      head = swapToHead(head, n);
      return head.data;
    }
    else
    {
      T = getOutFromCache(K);
      Node newNode = new Node(T);
      newNode.next = head;
      head = newNode;
      if (size == MAX_SIZE)
      {
        Node newTail = tail.pre;
        newTail.next = null;
        tail.pre = null;
        tail = null;
        tail = newTail;
      }
      else
      {
        size++;
      }
    }
    
    return T;
  }
}

LRU cache.