数据结构学习笔记|链表
原创
数据结构学习笔记|链表
原创
1. 链表的定义
链表是一种常见的数据结构，一般的缓存管理都会选择链表来实现LRU。在常见的面试八股文中，总会提到数组和链表的区别。一般的答案主要包括几个方面：
- 数组在内存中是连续的，链表不是连续的；
- 数组用下标查找的时间复杂度是O(1)，链表适合插入删除，时间复杂度是O(1)
在日常的工作中基本按照上面的特点选择需要的数据结构就可以了。链表是一种很有用的基础数据结构，用链表可以实现像栈、队列等数据结构。
链表又分为单链表、双向链表和循环链表。不管是那种形式，链表就是一个由指针串起来的数据结构。下图是链表在内存中的示意图，可以看到链表并不要求内存的连续，这也就决定了链表在插入和删除时完全没有内存搬迁的压力，所以无论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。
2. 链表的操作
链表的操作常见的无非是插入、删除和查找，这几种操作又可以变化出不同的功能接口出来。例如JDK的LinkedList就有功能非常丰富的接口供人使用。
插入结点是一个比较特殊的地方，有头插法和尾插法两种不同的逻辑。用图来表示头插法，引入头结点之后，头插法的逻辑也适用于向链表中任意位置插入的场景：
逻辑顺序是：
- new node的next指向原结点node的next，此时短暂的形成了两个list，上图时刻1；
- 原结点的next指向new node，此时两个list合二为一，插入操作完成，上图时刻2。
用代码来实现则是，这里我添加了一个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：
其逻辑顺序是：
- 尾指针p指向尾结点；
- p的next指向new node；
- 将指针p指向new node，即继续表示链表尾部，逻辑完成。
从图中不难看出不管是头插法还是尾插法，其操作的时间复杂度都是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;
}结点的删除操作用图来示意，也就是将指针指向变换一下即可：
其逻辑顺序是：
- 指针p指向要删除的结点node；
- node的前导结点pre的next指向p的next；
- 释放p的内存
如果是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;
}3. 用双向链表解决插入和删除的O(n)问题
之前提到了删除和插入都可能被寻址搞成总体消耗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表。
4. 利用链表实现简易的LRU算法
所谓LRU就是“最近最少使用”，是一种缓存管理的思路。具体到链表里，当一个数据被访问时，其逻辑是这样的：
- 遍历链表寻找该数据，如果能找到，则将其从原来的位置删除并移到链表的头部（带头结点的链表则是移动到头结点之后）；
- 如果没有找到该数据，则分为两种情况。如果链表没有满（size < capacity），将该数据插入到链表头部；如果链表已满，则将队尾的结点删除，然后将数据插入链表头部。
这里有个问题，如果是测试人员此时访问了大量数据，那么就会导致真的热数据被逐出链表，造成后续操作耗时增加，且有需要大量的链表操作造成内存碎片。
为了解决这个问题，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)，加在一起，那就更可观了。
5. LeetCode解题
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 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;
}206. 反转链表
给你单链表的头节点 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 删除。
腾讯云开发者
