LRU算法 -- 链表 完整实现

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

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

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

实现算法思路：

LRU 功能的实现:

1. 已有链表中存在 待插入元素，则将该元素在链表中删除，并头插法到链表头节点

2. 已有链表中不存在 待插入元素：

a. 若 LRU 容量已满，则删除尾元素，头插当前元素

b. 若 LRU 容量未满，则直接头插法当前元素

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

#include <iostream>

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，不存在则返回false
    void deleteElementEnd();             //删除链表的最后一个节点
    bool deleteElem(DataType x);         //删除链表中值为x的节点，删除成功则返回true,不存在则返回false
    bool isEmpty();                      //判断链表是否为空，是则返回true,否则返回false
    bool isFull();                       //判断链表是否满，是则返回true,否则返回false
    void 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;
}      

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