如何使用鏈表實現(xiàn) LRU 算法

什么是 LRU 算法

LRU 是一種緩存淘汰策略。計算機的緩存容量有限，如果緩存滿了就要刪除一些內容，給新的內容騰位置。但是要刪除哪些內容呢？我們肯定希望刪掉那些沒有用的緩存，而把有用的數(shù)據(jù)繼續(xù)留在緩存中，方便之后繼續(xù)使用。

LRU 的全稱是 Least Recently Used，也就是說我們認為最近使用過的數(shù)據(jù)應該是有用的，很久都沒用過的數(shù)據(jù)應該是無用的，緩存滿了就優(yōu)先刪除那些很久沒有用過的數(shù)據(jù)。

LRU 算法的特點

首先是緩存的大小是有限的。每次從緩存當中獲取數(shù)據(jù)的時候，如果獲取成功會將數(shù)據(jù)移動到最頭部。同時新添加的元素也是在頭部。當緩存大小達到上限之后，添加元素時會刪除最久未使用的元素，也就是鏈表的最后一個元素，然后將新的元素插入在鏈表頭。

LRU 的應用場景

LRU 算法可以用來管理我們的緩存數(shù)據(jù)?？刂莆覀兊木彺娲笮?，用較少的緩存空間達到更高的緩存數(shù)據(jù)。舉例來說我們可以將一些不容易發(fā)生變化的數(shù)據(jù)且頭部效應表中的數(shù)據(jù)加入到緩存當中。

編碼實現(xiàn)

結構定義

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 默認容量
#define N 10

// 表示這個鏈表的長度信息
int len = 0;

//當前鏈表的元素個數(shù)信息
int count = 0;

typedef struct Node
{
    /* data */
    char *key;
    char *value;

    struct Node *next;
    struct Node *prev;
} Node;

// 鏈表的頭節(jié)點和尾節(jié)點
struct Node *head;
struct Node *tail;

// 函數(shù)預聲明
// 創(chuàng)建節(jié)點
Node *createNode(char *key, char *value);
// 插入節(jié)點到頭部
void insertHead(Node *node);
// 移除尾部節(jié)點
void removeTail();
// 添加節(jié)點操作
void add(char *key, char *value);
// 刪除鏈表中的一個節(jié)點
Node *deleteNode(Node *node);
// 獲取指定key的值
char *get(char *key);
// 銷毀數(shù)據(jù)
void destory();

插入操作

// 獲取一個元素
void add(char *key, char *value)
{
    Node *node = createNode(key, value);
    //第一個元素
    if (head == NULL)
    {
        insertHead(node);
        return;
    }

    //判斷整個鏈表中是否存在整個元素
    Node *now = deleteNode(node);

    // 如果找到了元素 將元素移動至末尾 結束方法
    if (now != NULL)
    {
        // 設置新的值
        now->value = value;
        insertHead(now);
        return;
    }

    // 此時鏈表中是不存在這個元素
    // 判斷鏈表的長度
    if (count >= len)
    {
        removeTail();
    }

    // 將新元素添加至末尾
    insertHead(node);
    return;
}

獲取操作

char *get(char *key)
{
    if (key == NULL)
    {
        return NULL;
    }

    // 尋找元素
    Node *node = createNode(key, NULL);
    Node *now = deleteNode(node);

    // 釋放空間
    free(node);

    // 元素存在
    if (now != NULL)
    {
        //將元素調整到末尾
        insertHead(now);
        return now->value;
    }
    return NULL;
}

基本操作函數(shù)

// 創(chuàng)建一個節(jié)點
Node *createNode(char *key, char *value)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->prev = node->next = NULL;
    return node;
}

// 將節(jié)點插入到頭節(jié)點部分
void insertHead(Node *node)
{
    // 元素為空時
    if (head == NULL)
    {
        tail = head = node;
        count++;
        return;
    }
    node->next = head;
    head->prev = node;
    // 移動鏈表的末尾指針
    head = node;
    // 計數(shù)
    count++;
}

// 移除
void removeTail()
{
    //移除最久未使用的那個元素
    Node *now = tail;
    if (now != NULL)
    {
        // 獲取前一個節(jié)點
        Node *p = now->prev;

        if (p != NULL)
        {
            // 斷開當前節(jié)點 同時移動尾節(jié)點
            p->next = NULL;
            tail = p;
        }
        else
        {
            head = tail = NULL;
        }
        // 當前節(jié)點置空
        now->prev = now->next = NULL;
        // 元素減少
        count--;
        // 釋放空間
        free(now);
    }
}

// 鏈表中刪除一個節(jié)點  刪除成功返回被刪除節(jié)點
Node *deleteNode(Node *node)
{
    Node *now = head;
    while (now != NULL)
    {
        // 存在節(jié)點
        if (strcmp(now->key, node->key) == 0)
        {
            // 獲取前后節(jié)點
            Node *p = now->prev;
            Node *n = now->next;

            // 更新指向
            if (n != NULL)
            {
                n->prev = p;
            }
            else
            {
                tail = p;
            }

            if (p != NULL)
            {
                p->next = n;
            }
            else
            {
                head = n;
            }
            //當前節(jié)點置空
            now->prev = NULL;
            now->next = NULL;
            count--;
            break;
        }
        now = now->next;
    }
    return now;
}

// 銷毀數(shù)據(jù)
void destory()
{
    Node *node = head;
    while (node != NULL)
    {
        Node *n = node;
        free(n);
        node = node->next;
    }
    len = 0;
    count = 0;
    head = tail = NULL;
}

// 從頭節(jié)點開始打印整個鏈表
void printLink()
{
    Node *now = head;
    while (now != NULL)
    {
        printf("[key=%s,value=%s]", now->key, now->value);
        now = now->next;
    }
    printf("\n");
}

最后的測試函數(shù)

int main()
{
    init(5);
    add("1", "1");
    add("2", "2");
    printLink();
    char *res = get("1");
    printLink();
    printf("value=%s\n", res);
    add("3", "3");
    add("4", "4");
    add("5", "5");
    add("6", "6");
    printLink();
    res = get("1");
    printLink();
    destory();
    return 0;
}

// 輸出結果：
/*

[key=2,value=2][key=1,value=1]
[key=1,value=1][key=2,value=2]
value=1
[key=6,value=6][key=5,value=5][key=4,value=4][key=3,value=3][key=1,value=1]
[key=1,value=1][key=6,value=6][key=5,value=5][key=4,value=4][key=3,value=3]

*/

以上就是一個鏈表實現(xiàn) LRU 算法的大體代碼。
已將代碼上傳至https://gitlab.com/BitLegend/c-data-structure.git

感謝你能看到這里，歡迎關注我的公眾號：BitLegend,我們下期見！