用双向链表实现LRU算法（c++）_c++ 双向链表实现lru

实现LRU算法的方式有两种：数组和单链表。讲讲我为什么要用链表模拟实现。
其实我们知道，cpu从外存取数据到内存是以块为基本单位的，也就是说cpu取一块连续的地址到内存内，这样说的话是不是对数组友好点？因为数组用连续的地址存储着相同类型的数据。但是在我考虑在实际应用中，如果需要分配的地址过大时，可能会由于各种原理（存储空间有限或者空间碎片化）无法分配一块连续的地址给数组，而且在频繁的插入删除操作面前，数组的时间复杂度太高。所以我觉得链表在LRU实现上虽不能一次性传送块数据，但是实现条件却很简单，没有数组的苛刻，且时间复杂度低。

算法实现：用单链表实现LRU算法
1、将需要放进链表的数据同链表中的数据域比较，是否在链表中
true：如果链表没有达到最大存储上限，将原先存储的那一块内存删除，再将数据头插法插入链表；
false：如果链表没有达到上限，直接插入链表头部，Nowlen+1，空间满删除最后一个节点再将数据插入链表头部

在实现的过程中，当需要删除最后一个节点时，单链表往往需要重新遍历链表找到最后一个节点，比较费时，就将单链表转为双向链表实现，这样插入的时候将tail尾指针给插入的第一个元素，这样删除尾元素之前先将尾指针指向尾元素的pre节点，这样就不用重复遍历节点了。但是后来又想了想，其实时间复杂度还是O（n），然后突然想到我们每次都需要遍历一次指针，那不妨同时遍历到尾，将尾指针赋值给tail，就只需要遍历一次，或许也是个可行的办法。
实现头文件

#pragma once
#pragma once
#include<iostream>
#include<string>
using namespace std;
class linknode
{
public:
	char data;
	linknode *next;
	linknode *pre;
	linknode()
	{
		data = '0';
		next = NULL;
		pre = NULL;
	}
};
class list : public linknode
{
private:
	linknode *first;
	linknode *tail;
	int Maxlen;//链表的最大长度
	int Nlen;//链表当前长度
public:
	list();//初始化链表
	void head_insert(linknode *a);//当有新节点被访问时，将新节点查到链表头部
	void  omit(linknode *q);//删除当前节点，但节点还是要存储在链表头，所有不用Delete当前节点
	bool LRU(char a);//遍历链表查找字符是否在链表中，如何存在则删除
	void  getlen(int n);//获得链表最大可允许存储的数据大小
	void output();//输出链表，测试用
};
list::list()
{
	first = new linknode;
	tail = new linknode;
	Maxlen = 0;
	Nlen = 0;
}

void list::head_insert(linknode *a)
{
	
	if (first->next != NULL)//第一个元素插入式时应为first->next没有具体的地址（NULL），需要特殊处理
	{
		a->next = first->next;
		first->next->pre = a;
	}
	first->next = a;
	a->pre = first;
	if (Nlen == 0)
		tail = first->next;
	
}
bool list::LRU(char a)
{   
	linknode *p = first->next;
	linknode *pPre = first;
	while (p != NULL)//如果链表不为空
	{
		if (p->data == a)//查找链表中是否存在元素
		{
            omit(pPre);//存在则删除并重新插入到表头
			head_insert(p);
			return true;
		}
		p = p->next;
		pPre = pPre->next;
	}
	
	if (Nlen == Maxlen)//链表达到上限
	{
		linknode *t = tail->pre;//重新设置尾指针
		tail = t;
		tail->next = NULL;//删除尾结点
		Nlen--;
	}
	linknode *Node=new linknode;
	Node->data = a;
	head_insert(Node);//插入新元素
	Nlen++;
	return false;
	
}
void  list::getlen(int n)
{
	Maxlen = n;
}

void  list::omit(linknode *q)
{

	q->next = q->next->next;
}
void list::output()
{
	linknode *temp = first->next;
	while (temp != NULL)
	{
		cout << temp->data << "   ";
		temp = temp->next;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

测试cpp

#include"list.h"
int main()
{
	char a;
	int n;
	cout << "请输入内存最大可存入的数:";
	cin >> n;
	list *List=new list;
	List->getlen(n);
	while (cin >> a)
	{

		if (List->LRU(a))
		{
			List->output();
		}
		else
		{
			List->output();
		}

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23