链表是一种常见的数据结构,一般的缓存管理都会选择链表来实现LRU。在常见的面试八股文中,总会提到数组和链表的区别。一般的答案主要包括几个方面:
在日常的工作中基本按照上面的特点选择需要的数据结构就可以了。链表是一种很有用的基础数据结构,用链表可以实现像栈、队列等数据结构。
链表又分为单链表、双向链表和循环链表。不管是那种形式,链表就是一个由指针串起来的数据结构。下图是链表在内存中的示意图,可以看到链表并不要求内存的连续,这也就决定了链表在插入和删除时完全没有内存搬迁的压力,所以无论add还是delete操作,其时间复杂度都是O(1):
如果用C语言来实现链表,需要声明一个结构体,结构体主要的两个元素分别是data、指向下一结点的指针。不过为了方便,还可以加上链表的容量和长度。
于是可以写出下面的代码:
typedef struct node {
linkedlist next; //下一个节点指针
int data; //实际保存的数字
int size; //链表的当前大小
int capacity; //链表的最大容量
} *linkedlist, node;
这样就可以构造出一个单向链表了:
这里要注意,为了统一所有结点的处理逻辑,一般都会引入一个头结点来,这个头结点的data域为空值或者0值。对于上面的定义来说,头结点还能存放size和capacity,非常方便后面的各种操作。
而尾结点的特点是next域指向null。
链表的操作常见的无非是插入、删除和查找,这几种操作又可以变化出不同的功能接口出来。例如JDK的LinkedList就有功能非常丰富的接口供人使用。
插入结点是一个比较特殊的地方,有头插法和尾插法两种不同的逻辑。用图来表示头插法,引入头结点之后,头插法的逻辑也适用于向链表中任意位置插入的场景:
逻辑顺序是:
用代码来实现则是,这里我添加了一个capacity和size的作用就出来了,可以用来判断list是不是已经没有空间了,如果还能插入,则会在最后,给头结点的size域自加1:
void addFirst(linkedlist list, node* n) {
// if list is full, return
if (checkFull(list)) {
printf("list is full!\n");
return;
}
n->next = list->next;
list->next = n;
list->size += 1;
}
而尾插法则是append,如图,需要借助一个尾指针p:
其逻辑顺序是:
从图中不难看出不管是头插法还是尾插法,其操作的时间复杂度都是O(1)。但是这仅仅是操作本身的时间复杂度,在尾插法里,需要首先知道链表的尾部结点地址。而寻址的过程,时间复杂度就是O(n)了。
对于头插法来说,如果是特殊情况(每次都在头结点后插入数据,或者给定一个结点地址要求插入其后),则没有寻址的问题,时间复杂度一定是O(1)。
如果仅仅给了一个位置pos,要求插入这个pos之后,那么这时最好的情况是O(1),最差的情况是O(n)。
综上,虽然链表的插入操作本身时间复杂度并不高,但是考虑到可能存在的寻址操作,其时间复杂度也是比较可观的。
用代码来实现则能看出其时间都消耗在哪里了:
void add(linkedlist list, node* n) {
// if list is full, return
if (checkFull(list)) {
printf("list is full!\n");
return;
}
// if list has only head node, append to head node directly, then add 1 to head node's size variable, then return
if (list->next == nullptr) {
list->next = n;
list->size += 1;
return ;
}
// if list's size larger than 1, find list's tail node,O(n)
linkedlist p = list;
do {
p = p->next;
} while (p->next != nullptr);
p->next = n;
list->size += 1;
}
结点的删除操作用图来示意,也就是将指针指向变换一下即可:
其逻辑顺序是:
如果是Java这类自动管理内存的语言,可以不用管第三步。
从这里也能看出,删除操作的时间复杂度也是O(1),但是,如果没有告知前导结点pre的地址,那么寻址的过程是不可省略的,其时间复杂度最坏情况下还是O(n)。
不管是去删除给定pos的元素还是删除给定的node,都需要寻址,代码如下:
void remove(linkedlist list, int pos) {
if (pos > list->size) {
printf("pos越界!\n");
return;
}
linkedlist p = list;
int index = 0;
while (index != pos - 1) {
p = p->next;
index += 1;
}
linkedlist temp ;
temp = p->next;
p->next = temp->next;
free(temp);
list->size -= 1;
}
void remove(linkedlist list, node* n) {
linkedlist p = list;
while (p->next != n) {
p = p->next;
if (p == nullptr) {
printf("找不到要删除的节点\n");
return;
}
}
linkedlist temp ;
temp = p->next;
p->next = temp->next;
free(temp);
list->size -= 1;
}
之前提到了删除和插入都可能被寻址搞成总体消耗O(n)的时间复杂度。而如果在给定结点删除(或者在给定结点前插入)的时候能够不要遍历就知道前导结点,那么时间整体的时间复杂度就变成O(1)了。
空间换时间,在有些场景下是划算的。
稍加修改一下结点的定义即可,相比单链表只是增加了一个prev指针指向前一个结点:
struct duNode {
duLinkedlist prev;
duLinkedlist next;
int data;
int size;
int capacity;
};
此时的remove方法就看着简单很多了,没有考虑越界这些情况,从核心来看,不需要额外的寻址了:
void remove(duLinkedlist list, duNode* p) {
duLinkedlist pre = p->prev;
duLinkedlist n = p->next;
pre->next = n;
n->prev = pre;
free(p);
list->size -= 1;
}
不过想要得到被删除的结点p,仍然是要下一番功夫的,还是O(n)的时间复杂度,这似乎成了一个不可解的问题一直缠绕着我。在常见的缓存管理链表实现LRU的时候,不可能不对此进行优化的。最常见的一种方式是引入一个hash表,记录每个数据在链表中的位置,这样时间复杂度就变成O(1)了。
结合之前总结的单链表和双向链表,可以在下一小节讨论和实现LRU,暂时不引入hash表。
所谓LRU就是“最近最少使用”,是一种缓存管理的思路。具体到链表里,当一个数据被访问时,其逻辑是这样的:
这里有个问题,如果是测试人员此时访问了大量数据,那么就会导致真的热数据被逐出链表,造成后续操作耗时增加,且有需要大量的链表操作造成内存碎片。
为了解决这个问题,InnoDB则是选择每次将链表分为了新区和老区,新的数据插入到链表的3/8处,然后随着访问频次的提高,才将这个结点移动到链表的头部来。
void lru(duLinkedlist list, int data) {
duLinkedlist p = list;
duNode * d = find(list, data); //寻找结点
if (d == nullptr) { //如果结点不在LRU链表里
auto* node = (duNode*) malloc(sizeof (duNode));
node->data = data;
if (list->size == list->capacity) { //如果链表已满
removeTail(list); //删除尾结点
}
// 头插法插入结点
node->next = p->next;
p->next = node;
node->prev = p;
list->size += 1;
} else {
// 将结点移动到头部
moveToHead(list, d);
}
}
void moveToHead(duLinkedlist list, duNode* p) {
duLinkedlist pre = p->prev;
duLinkedlist head = list;
duLinkedlist n = p->next;
if (n == nullptr) { //p如果是尾结点
pre->next = nullptr;
p->next = head->next;
head->next = p;
p->prev = head;
return;
}
pre->next = n;
n->prev = pre;
p->next = head->next;
head->next = p;
p->prev = head;
}
初步测试这个算法基本可用,虽然作为工业生产不太可能,但是足以说明算法思想和数据结构的应用。
上面代码中的moveToHead函数,因为用了双向链表,所以整个函数的时间复杂度就是O(1)了,如果是单向链表,则还需要遍历找到p的前导结点,这样时间复杂度就很可观了。而这之前又要有一个用data去find结点的过程,时间复杂度还是O(n),加在一起,那就更可观了。
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
输入:head = [1,1,2]
输出:[1,2]
初见这个题的时候我想的比较复杂,我想如果用Java的话那我一定引入一个HashMap,如果Key存在则把链表的元素删除。因此我打算用一个bitmap来实现。不过后来我想明白了,这个题的关键是有序。
所有重复的元素一定是挨着的,那么我们只要不断地遍历当前元素和下一个元素就可以了,如果遇到一样的,直接将下一个元素删除就可以了。
标准的写法如下,但是在LeetCode提交的时候不要写free语句,会引发错误,在LeetCode里什么malloc,free之类的都可能导致错误,结果不错,只用了4ms,不过内存消耗比较大用了6.4MB:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head){
if (!head) {
return head;
}
struct ListNode* L = head;
while (L->next) {
if (L->val == L->next->val) {
struct ListNode* temp = L->next->next;
L->next = temp;
free(temp);
} else {
L = L->next;
}
}
return head;
}
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
我本来想的是再搞一个链表,用头插法。不过想想LeetCode可能会限制malloc,那就只能作罢。这道题的思路是维护三个指针:prev,cur,next,不断地移动cur指针,将cur的next指向cur的prev,然后移动prev到cur的位置,循环往复。
时间复杂度就是O(n)
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* L = head;
struct ListNode* prev = NULL;
while (L) {
struct ListNode* next = L->next;
L->next = prev;
prev = L;
L = next;
}
return head;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。