LRU算法(Least Recently Used) 算是我们经常遇到的一种淘汰算法，其中内存管理模块进行内存页回收时有用到，针对不经常使用的内存页，LRU淘汰策略能够将该内存页回收给操作系统。

属于 我们操作系统设计中的 时间局部性原理，最长时间未被访问的数据优先淘汰，当内存中已存在的数据再次被访问时，则进行热度的提升。

本文为了巩固数据结构相关知识，特 使用链表数据结构方式完整实现LRU链表的功能。关于数据结构和算法相关的学习导图可以借鉴数据结构和算法导图

实现算法思路：

   LRU 功能的实现:1. 已有链表中存在 待插入元素，则将该元素在链表中删除，并头插法到链表头节点2. 已有链表中不存在 待插入元素：a. 若 LRU 容量已满，则删除尾元素，头插当前元素b. 若 LRU 容量未满，则直接头插法当前元素 

以上实现 使用其他的线性表数据结构（栈、队列、数组）均能够实现，链表的实现方式如下：

#include using namespace std;typedef int DataType;/*节点类*/
class Node{ public:DataType val;Node *next;
};class List{ 
private:int maxSize;int length;Node *head;public:List();List(int size);~List();void insertElementBegin(DataType x); //头插法建立链表bool findElement(DataType x);        //查找链表中是否存在元素x,存在则返回true，不存在则返回falsevoid deleteElementEnd();             //删除链表的最后一个节点bool deleteElem(DataType x);         //删除链表中值为x的节点，删除成功则返回true,不存在则返回falsebool isEmpty();                      //判断链表是否为空，是则返回true,否则返回falsebool isFull();                       //判断链表是否满，是则返回true,否则返回falsevoid printAll();                     //打印链表中的元素，链表长度，LRU长度void * findElemOptim(DataType x);       //针对此应用的优化，查找,返回指定元素的前一个节点的指针void deleteElemOptim(void * node);     //针对此应用的优化，删除
};List::List(){ head = new Node;head -> next = NULL;this -> length = 0;this -> maxSize = 10;
}List::List(int size) { head = new Node;head -> next = NULL;this -> length = 0;this -> maxSize = size;
}List::~List() { Node* p, *tmp;p = head;while(p -> next) { tmp = p -> next;p -> next = p -> next -> next;delete tmp;}delete head;this -> head = NULL;this -> length = 0;
}void List::insertElementBegin(DataType x) { Node *p = new Node;p -> val = x;p -> next = head -> next;head -> next = p;this -> length ++;
}bool List::findElement(DataType x) { Node *p = head;while(p -> next != NULL) { if(p -> val == x) { return true;}p = p -> next;}return false;
}void List::deleteElementEnd() { if(head -> next == NULL) { return;}Node *tmp;Node *p = head;while(p -> next != NULL && p -> next -> next != NULL) { p = p -> next;}tmp = p -> next;p -> next = tmp -> next;this -> length --;delete tmp;
}bool List::deleteElem(DataType x) { Node *p = head;Node *tmp;while(p -> next != NULL) { if(p -> next -> val == x) { tmp = p -> next;p -> next = tmp -> next;delete tmp;this -> length --;return true;}p = p -> next;}return false;
}bool List::isEmpty() { return this -> length == 0 ? true:false;
}bool List::isFull() { return this -> length == maxSize ? true:false;
}void List::printAll() { Node *p;p = head;cout << "lru list length :" << this -> length << endl;cout << "lru list maxSize :" << this -> maxSize << endl;cout << "lru list val:" << endl;while(p -> next != NULL) { p = p -> next;cout << p -> val << " ";}cout << endl;
}void * List::findElemOptim(DataType x) { Node *p = head;while(p -> next != NULL) { if(p -> next -> val == x) { return (void *)p;}p = p -> next;}return NULL;
}void List::deleteElemOptim(void *node) { Node *p, *tmp;p = (Node*)node;tmp = p -> next;p -> next = tmp -> next;delete tmp;this -> length --;
}int main() { cout << "test LRU:" << endl;List list(10);int num = 0;while(1) { cout << "please enter a number, 99999 = exit" << endl;cin >> num;if(num == 9999) { break;}/*LRU 功能的实现:1. 已有链表中存在 待插入元素，则将该元素在链表中删除，并头插法到链表头节点2. 已有链表中不存在 待插入元素：a. 若 LRU 容量已满，则删除尾元素，头插当前元素b. 若 LRU 容量未满，则直接头插法当前元素           */Node *node = (Node*)list.findElemOptim(num);if(node != NULL) { list.deleteElemOptim(node);list.insertElementBegin(num);} else { if(list.isFull()) { list.deleteElementEnd();list.insertElementBegin(num);} else { list.insertElementBegin(num);}}list.printAll();}return 0;
}

编译g++ -std=c++11 lru_list.cc

运行如下./a.out：

test LRU:
please enter a number, 99999 = exit
2
lru list length :1
lru list maxSize :10
lru list val:
2 
please enter a number, 99999 = exit
3
lru list length :2
lru list maxSize :10
lru list val:
3 2 
please enter a number, 99999 = exit
4
lru list length :3
lru list maxSize :10
lru list val:
4 3 2
...
...
...
please enter a number, 99999 = exit #输入了34，此时LRU容量已满，则删除尾元素，头插入34
34
lru list length :10
lru list maxSize :10
lru list val:
34 23 12 11 1 8 7 3 2 6 
please enter a number, 99999 = exit #输入23，提升23的热度
23
lru list length :10
lru list maxSize :10
lru list val:
23 34 12 11 1 8 7 3 2 6 
please enter a number, 99999 = exit #输入2，提升2的热度
2
lru list length :10
lru list maxSize :10
lru list val:
2 23 34 12 11 1 8 7 3 6 
please enter a number, 99999 = exit
9999