双链表的节点删除操作：
void remove(CacheNode *node)
{
if (node -> pre != NULL)
{
node -> pre -> next = node -> next;
}
else
{
head = node -> next;
}
if (node -> next != NULL)
{
node -> next -> pre = node -> pre;
}
else
{
tail = node -> pre;
}
}
将节点插入到头部的操作：
void setHead(CacheNode *node)
{
node -> next = head;
node -> pre = NULL;
if (head != NULL)
{
head -> pre = node;
}
head = node;
if (tail == NULL)
{
tail = head;
}
}
get(key)操作的实现比较简单，直接通过判断Map是否含有key值即可，如果查找到key，则返回对应的value，否则返回-1;
int get(int key)
{
map<int, CacheNode *>::iterator it = mp.find(key);
if (it != mp.end())
{
CacheNode *node = it -> second;
remove(node);
setHead(node);
return node -> value;
}
else
{
return -1;
}
}
set(key, value)操作需要分情况判断。如果当前的key值对应的节点已经存在，则将这个节点取出来，并且删除节点所处的原有的位置，并在头部插入该节点；如果节点不存在节点中，这个时候需要在链表的头部插入新节点，插入新节点可能导致容量溢出，如果出现溢出的情况，则需要删除链表尾部的节点。
void set(int key, int value)
{
map<int, CacheNode *>::iterator it = mp.find(key);
if (it != mp.end())
{
CacheNode *node = it -> second;
node -> value = value;
remove(node);
setHead(node);
}
else
{
CacheNode *newNode = new CacheNode(key, value);
if (mp.size() >= size)
{
map<int, CacheNode *>::iterator iter = mp.find(tail -> key);
remove(tail);
mp.erase(iter);
}
setHead(newNode);
mp[key] = newNode;
}
}
总结
好了，至此，LRU算法的实现操作就完成了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。
注：相关教程知识阅读请移步到C++教程频道。
