双向链表，每次有get之后就把get的元素放到链表头，put的时候满了就删掉链表尾的元素。
public class LRUCache
{
private int Length;
private Node Head;
private Node Tail;
private int Capacity;
public LRUCache(int capacity)
{
Length = 0;
Head = new Node();
Tail = new Node();
Head.Next = Tail;
Tail.Prev = Head;
Capacity = capacity;
}
public int Get(int key)
{
if (Length == 0) return -1;
Node FindNode = Head;
while (FindNode != null)
{
if (FindNode.Key == key)
{
FindNode.Prev.Next = FindNode.Next;
FindNode.Next.Prev = FindNode.Prev;
FindNode.Prev = Head;
FindNode.Next = Head.Next;
Head.Next.Prev = FindNode;
Head.Next = FindNode;
return FindNode.Value;
}
FindNode = FindNode.Next;
}
return -1;
}
public void Put(int key, int value)
{
if (Get(key) != -1)
{
Node FindNode = Head;
while (FindNode != null)
{
if (FindNode.Key == key)
{
FindNode.Value = value;
return;
}
FindNode = FindNode.Next;
}
}
Node NewNode = new Node(key, value);
if (Length < Capacity)
{
//Node NewNode = new Node(key, value);
NewNode.Prev = Head;
NewNode.Next = Head.Next;
Head.Next.Prev = NewNode;
Head.Next = NewNode;
Length++;
return;
}
if (Capacity == 1)
{
//Node NewNode = new Node(key, value);
NewNode.Prev = Head;
Head.Next = NewNode;
Tail.Prev = NewNode;
NewNode.Next = Tail;
Length++;
return;
}
Node OldNode = Tail.Prev;
Tail.Prev = Tail.Prev.Prev;
Tail.Prev.Next = Tail;
OldNode = null;
NewNode.Next = Head.Next;
Head.Next.Prev = NewNode;
Head.Next = NewNode;
NewNode.Prev = Head;
Length++;
return;
}
}
public class Node
{
public int Key;
public int Value;
public Node Next, Prev;
public Node(int key, int value) { Key = key; Value = value; Next = null; Prev = null; }
public Node() { Key = 0; Value = 0; Next = null; Prev = null; }
}