如何使用鏈表實現(xiàn) LRU 算法
什么是 LRU 算法
LRU 是一種緩存淘汰策略宜鸯。計算機(jī)的緩存容量有限沪饺，如果緩存滿了就要刪除一些內(nèi)容球切，給新的內(nèi)容騰位置。但是要刪除哪些內(nèi)容呢捕仔？我們肯定希望刪掉那些沒有用的緩存，而把有用的數(shù)據(jù)繼續(xù)留在緩存中，方便之后繼續(xù)使用服赎。
LRU 的全稱是 Least Recently Used，也就是說我們認(rèn)為最近使用過的數(shù)據(jù)應(yīng)該是有用的交播，很久都沒用過的數(shù)據(jù)應(yīng)該是無用的重虑，緩存滿了就優(yōu)先刪除那些很久沒有用過的數(shù)據(jù)。
LRU 算法的特點
首先是緩存的大小是有限的秦士。每次從緩存當(dāng)中獲取數(shù)據(jù)的時候缺厉，如果獲取成功會將數(shù)據(jù)移動到最頭部。同時新添加的元素也是在頭部隧土。當(dāng)緩存大小達(dá)到上限之后提针，添加元素時會刪除最久未使用的元素，也就是鏈表的最后一個元素曹傀，然后將新的元素插入在鏈表頭辐脖。
LRU 的應(yīng)用場景
LRU 算法可以用來管理我們的緩存數(shù)據(jù)〗杂洌控制我們的緩存大小嗜价，用較少的緩存空間達(dá)到更高的緩存數(shù)據(jù)。舉例來說我們可以將一些不容易發(fā)生變化的數(shù)據(jù)且頭部效應(yīng)表中的數(shù)據(jù)加入到緩存當(dāng)中幕庐。
編碼實現(xiàn)
結(jié)構(gòu)定義
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 默認(rèn)容量
#define N 10
// 表示這個鏈表的長度信息
int len = 0;
//當(dāng)前鏈表的元素個數(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ù)預(yù)聲明
// 創(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);
// 如果找到了元素 將元素移動至末尾 結(jié)束方法
if (now != NULL)
{
// 設(shè)置新的值
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)
{
//將元素調(diào)整到末尾
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)
{
// 斷開當(dāng)前節(jié)點 同時移動尾節(jié)點
p->next = NULL;
tail = p;
}
else
{
head = tail = NULL;
}
// 當(dāng)前節(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;
}
//當(dāng)前節(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;
}
// 輸出結(jié)果：
/*
[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
感謝你能看到這里，歡迎關(guān)注我的公眾號：BitLegend,我們下期見翔脱！
