语言：C++
描述：使用单链表实现，HeadNode是key=-1，value=-1，next=NULL的结点。距离HeadNode近的结点是使用频度最小的Node。
struct Node {
int key;
int value;
Node* next;
};
class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
this->curLength = ;
this->headNode = new Node();
this->headNode->key = -;
this->headNode->value = -;
this->headNode->next = NULL;
this->lastNode = this->headNode;
}
int get(int key) {
if (this->curLength == )
return -;
Node* tmpNode = reSequencing(key, -);
if (tmpNode != NULL) {
return tmpNode->value;
} else {
return -;
}
}
void set(int key, int value) {
if (this->capacity == ) return;
Node* tmpNode = reSequencing(key, value);
if (tmpNode != NULL) {
tmpNode->value = value;
return;
}
if (this->curLength + > this->capacity) {
if (this->headNode->next == this->lastNode) {
delete this->lastNode;
this->lastNode = this->headNode;
} else {
Node* t = this->headNode->next->next;
delete this->headNode->next;
this->headNode->next = t;
}
}
Node* newNode = new Node();
newNode->key = key;
newNode->value = value;
newNode->next = NULL;
this->lastNode->next = newNode;
this->lastNode = newNode;
curLength += ;
}
Node* reSequencing(int key, int value) {
Node* tmpNode = this->headNode;
Node* preNode;
while (tmpNode != NULL) {
if (tmpNode->key == key) {
break;
}
preNode = tmpNode;
tmpNode = tmpNode->next;
}
if (tmpNode != NULL && this->lastNode->key != key) {
preNode->next = tmpNode->next;
this->lastNode->next = tmpNode;
this->lastNode = tmpNode;
tmpNode->next = NULL;
}
return tmpNode;
}
private:
int capacity;
int curLength;
Node* headNode;
Node* lastNode;
};