11、在pos位置之前删除数据
和pos位置之前插入数据类似，这里我们的时间复杂度也为O(1)，并且我们也可以通过调用此函数来完成头删和尾删的功能。
但是这里有一个问题，那就是pos不能是第一个节点的地址，因为我们不可能把哨兵位头结点给删除了，但是如果要避免这种情况出现，我们 Erase 函数就需要接受头结点的地址；
但是其实这个问题不应该由函数的实现者来注意，而是应该有函数的调用者来避免，另外感觉为了仅仅为了检查它把头结点传过来又没必要，所以我这里就没对其进行检查；大家可以根据自己的想法来实现这个函数。
//在pos位置之前删除数据 void ListErase(LTNode* pos) { //这里有一个问题：pos不能是第一个节点的地址，因为我们不可能把哨兵位头结点给删除了，需要函数调用者自己注意 assert(pos); //记录pos的前一个节点的前一个节点 LTNode* prev = pos->prev->prev; //free pos前的节点 free(pos->prev); //修改链接关系（当pos为第二个节点/头结点节点时逻辑也成立） //ps：头删和尾删可以通过直接调用此函数来完成 prev->next = pos; pos->prev = prev; }
//在头部删除数据 void ListPopFront(LTNode* phead) { assert(phead); assert(!IsEmpty(phead)); //删空时继续删除报错 ListErase(phead->next->next); //相当于删除第二个节点前的数据 }
//在尾部删除数据 void ListPopBack(LTNode* phead) { assert(phead); assert(!IsEmpty(phead)); //删空时继续删除报错 ListErase(phead); //相当于删除头结点前的数据 }
12、修改pos位置处的数据
其实在C++ STL 的 List 中是没有单独的修改函数的，因为 Find 就可以实现修改的功能；Find 函数返回一个数据的地址 pos ，然后我们直接修改 pos->data 即可，但是这里我还是单独实现了一个修改函数。
//修改链表数据 void ListModify(LTNode* pos, LTDataType x) { assert(pos); pos->data = x; }
13、返回链表长度
由于链表长度的计算需要遍历链表，时间复杂度为O(N)，而带头双向链表其他接口的时间复杂度都是O(1)，所以这里显得有些突兀；
所以有的书上或者学校就用头结点来存储链表元素，反正头结点也不用于存储数据，乍一看这样设计好像没有什么问题，但是当我们存储的数据不是整形，而是其他类型，比如 char 时，这种设计就有问题了；
当 data 的类型是 char时，我们知道 char 最大为127，超过127就会发生截断，这种情况下当链表长度大于127时，头结点中的 data 存储的链表长度就是错误的了；更别说我们用其来存储结构体类型的数据了。
所以说用头结点来存储链表长度这种设计是因小失大、不合理的；如果实在想让计算链表长度的时间复杂度变为O(1)，我们可以在结构体中增加一个size变量，专门用于记录链表长度。
//计算链表长度 size_t ListSize(LTNode* phead) { assert(phead); size_t size = 0; LTNode* cur = phead->next; //链表长度不包含头结点，因为头结点不存储有效数据 while (cur != phead) { size++; cur = cur->next; } return size; }
14、打印链表数据
这里我们需要注意循环结束的条件，由于我们的链表是循环的，所以 cur 永远不可能为空，而是当 cur 回到头时代表遍历完成。
//打印链表数据 void ListPrint(LTNode* phead) { assert(phead); //因为链表是带头的，所以phead不可能为空 LTNode* cur = phead->next; //从第一个有效元素开始打印 printf("head<=>"); while (cur != phead) //当cur回到头结点时循环结束 { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
15、销毁链表
和 Init 函数相反，销毁链表需要同时销毁哨兵位头结点，也就是说我们需要改变头结点；要改变头结点有两种方法：
1、传递二级指针：考虑到接口的一致性，我们不使用此方法；
2、把函数返回值改为结构体指针：在销毁链表时我们还要去接受链表的返回值，感觉很别扭，所以我们也不用；
基于上面这两点：头结点置空的操作需要函数调用者在函数外来执行。
//销毁链表 void ListDestory(LTNode* phead) { assert(phead); //链表带头 LTNode* cur = phead->next; //释放掉除头结点以外的其他节点 while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } //释放头结点 (这里需要调用者在函数外部手动把phead置为NULL（要改变phead需要用二级指针或者函数返回值） free(phead); }
三、完整代码
1、List.h
#pragma once //防止头文件重复包含 //头文件的定义 #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //结构和符号的定义 typedef int LTDataType; typedef struct ListNode { LTDataType data; //用于存放数据 struct ListNode* prev; //用于存放下一个节点的地址 struct ListNode* next; //用于存放上一个节点的地址 }LTNode; //函数的声明 //初始化双链表 LTNode* ListInit(); //开辟新节点 LTNode* BuyLTNode(LTDataType x); //打印链表数据 void ListPrint(LTNode* phead); //销毁链表 void ListDestory(LTNode* phead); //在头部插入数据 void ListPushFront(LTNode* phead, LTDataType x); //在尾部插入数据 void ListPushBack(LTNode* phead, LTDataType x); //查找数据 LTNode* ListFind(LTNode* phead, LTDataType x); //在pos位置之前插入数据 void ListInsert(LTNode* pos, LTDataType x); //判断链表是否为空 bool IsEmpty(LTNode* phead); //在头部删除数据 void ListPopFront(LTNode* phead); //在尾部删除数据 void ListPopBack(LTNode* phead); //在pos位置之前删除数据 void ListErase(LTNode* pos); //计算链表长度 size_t ListSize(LTNode* phead); //修改链表数据 void ListModify(LTNode* pos, LTDataType x);
2、List.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "LIst.h" //初始化双链表 LTNode* ListInit() { //创建哨兵位头结点 LTNode* guard = (LTNode*)malloc(sizeof(struct ListNode)); if (guard == NULL) { perror("malloc fail"); return NULL; } //让双链表具有双向循环结构 guard->prev = guard; guard->next = guard; return guard; } //开辟新节点 LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(struct ListNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->prev = NULL; newnode->next = NULL; return newnode; } //打印链表数据 void ListPrint(LTNode* phead) { assert(phead); //因为链表是带头的，所以phead不可能为空 LTNode* cur = phead->next; //从第一个有效元素开始打印 printf("head<=>"); while (cur != phead) //当cur回到头结点时循环结束 { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); } //销毁链表 void ListDestory(LTNode* phead) { assert(phead); //链表带头 LTNode* cur = phead->next; //释放掉除头结点以外的其他节点 while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } //释放头结点 (这里需要调用者在函数外部手动把phead置为NULL（要改变phead需要用二级指针或者函数返回值） free(phead); } //在头部插入数据 void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead->next, x); //相当于第一个节点前面插入元素 //assert(phead); //因为链表是带头的，所以phead不可能为空 //LTNode* newnode = BuyLTNode(x); //LTNode* first = phead->next; //记录第一个节点 改变链接关系（当链表中没有节点，即只有一个头时，下面逻辑也正常） //phead->next = newnode; //newnode->prev = phead; //newnode->next = first; //first->prev = newnode; } //在尾部插入数据 void ListPushBack(LTNode* phead, LTDataType x) { assert(phead); ListInsert(phead, x); //相当于头结点前面插入元素 //assert(phead); //LTNode* newnode = BuyLTNode(x); 找尾：头结点的prev指向链表的尾 //LTNode* tail = phead->prev; 修改链接关系(当链表中没有节点时逻辑也成立） //phead->prev = newnode; //newnode->next = phead; //newnode->prev = tail; //tail->next = newnode; } //查找数据 LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; //遍历链表，找到返回数据所在节点的地址 while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } //找不到就返回NULL return NULL; } //在pos位置之前插入数据 void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyLTNode(x); //找pos的前一个节点 LTNode* prev = pos->prev; //修改链接关系（当pos为第一个节点/最后一个节点时逻辑也成立） //ps：头插和尾插可以通过直接调用此函数来完成 prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } //判断链表是否为空 bool IsEmpty(LTNode* phead) { assert(phead); return phead == phead->next; //当链表中只剩下头结点时链表为空，返回true } //在头部删除数据 void ListPopFront(LTNode* phead) { assert(phead); assert(!IsEmpty(phead)); //删空时继续删除报错 ListErase(phead->next->next); //相当于删除第二个节点前的数据 //assert(phead); //assert(!IsEmpty(phead)); //删空时继续删除报错 记录第一个节点的下一个节点 //LTNode* second = phead->next->next; 释放第一个节点 //free(phead->next); 修改链接关系 //phead->next = second; //second->prev = phead; } //在尾部删除数据 void ListPopBack(LTNode* phead) { assert(phead); assert(!IsEmpty(phead)); //删空时继续删除报错 ListErase(phead); //相当于删除头结点前的数据 //assert(phead); //assert(!IsEmpty(phead)); //删空时继续删除报错 记录尾结点的上一个节点 //LTNode* prev = phead->prev->prev; 释放尾结点 //free(phead->prev); 修改链接关系 //phead->prev = prev; //prev->next = phead; } //在pos位置之前删除数据 void ListErase(LTNode* pos) { //这里有一个问题：pos不能是第一个节点的地址，因为我们不可能把哨兵位头结点给删除了，需要函数调用者自己注意 assert(pos); //记录pos的前一个节点的前一个节点 LTNode* prev = pos->prev->prev; //free pos前的节点 free(pos->prev); //修改链接关系（当pos为第二个节点/头结点节点时逻辑也成立） //ps：头删和尾删可以通过直接调用此函数来完成 prev->next = pos; pos->prev = prev; } //计算链表长度 size_t ListSize(LTNode* phead) { assert(phead); size_t size = 0; LTNode* cur = phead->next; //链表长度不包含头结点，因为头结点不存储有效数据 while (cur != phead) { size++; cur = cur->next; } return size; } //修改链表数据 void ListModify(LTNode* pos, LTDataType x) { assert(pos); pos->data = x; }
3、test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "LIst.h" void test1() //测试插入 { //创建并初始化链表 LTNode* plist = ListInit(); //在头部插入数据 ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPrint(plist); //在尾部插入数据 ListPushBack(plist, 4); ListPushBack(plist, 5); ListPushBack(plist, 6); ListPrint(plist); //在pos位置之前插入 LTNode* pos = ListFind(plist, 3); if (pos) { ListInsert(pos, 30); } pos = ListFind(plist, 6); if (pos) { ListInsert(pos, 60); } pos = ListFind(plist, 1); if (pos) { ListInsert(pos, 10); } ListPrint(plist); //销毁链表 ListDestory(plist); plist = NULL; //需要我们手动置空plist } void test2() //测试删除 { //创建并初始化链表 LTNode* plist = ListInit(); //在头部插入数据 ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPrint(plist); //在头部删除数据 //ListPopFront(plist); //ListPopFront(plist); //ListPrint(plist); //在尾部删除数据 //ListPopBack(plist); //ListPopBack(plist); //ListPopBack(plist); //ListPrint(plist); //删除pos位置之前的数据 LTNode* pos = ListFind(plist, 2); if (pos) { ListErase(pos); } ListPrint(plist); pos = ListFind(plist, 1); if (pos) { ListErase(pos); } ListPrint(plist); //销毁链表 ListDestory(plist); plist = NULL; //需要我们手动改变plist } void test3() //测试其他功能 { //创建并初始化链表 LTNode* plist = ListInit(); //在头部插入数据 ListPushFront(plist, 1); ListPushFront(plist, 2); ListPushFront(plist, 3); ListPrint(plist); //计算链表长度 size_t size = ListSize(plist); printf("%u\n", size); //修改链表数据 LTNode* pos = ListFind(plist, 1); if (pos) { ListModify(pos, 10); } pos = ListFind(plist, 2); if (pos) { ListModify(pos, 20); } ListPrint(plist); //销毁链表 ListDestory(plist); plist = NULL; //需要我们手动改变plist } int main() { //test1(); //测试插入 //test2(); //测试删除 //test3(); //测试其他功能 return 0; }
大家也可以去我的 Gitee 仓库中获取完整代码：List/List · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)
四、顺序表和链表的区别
顺序表的优点
1、尾插尾删效率高；2、支持随机访问 (下标访问)；
3、相比于链表结构，CPU 高速缓存命中率更高；
顺序表缺点
1、在其他位置的插入删除效率低；
2、扩容存在内存消耗和空间浪费；
链表 (带头双向循环) 的优点
1、任意位置插入删除效率都很高；2、空间按需申请，没有空间浪费；
链表 (带头双向循环) 的缺点
1、由于需要频繁 malloc，所以和顺序表的内存消耗其实差不多；2、不支持随机访问 (下标访问)；
3、相比于顺序表结构，CPU 高速缓存命中率更低；
综合比较顺序表和链表的优缺点，其实在实际生活中，顺序表的应用比链表的应用还要多一些；其中顺序表支持随机访问是一个重要因素，另外还有顺序表 CPU 高速缓存命中率高和其他原因；下面我们来探讨 CPU 高速缓存命中率的问题。
我们知道，为了提高效率与降低成本，我们的计算机是分层存储的，具体的存储体系结构如下图：
从程序环境那一节的学习中我们知道，一个程序经过编译链接后被翻译成二进制指令，这些二进制指令由由 CPU 来执行；
但是，CPU 执行指令时，并不会直接去访问内存中的数据，而是会看数据是否存在于三级缓存中，如果在，就代表命中；如果不在，就代表未命中，未命中情况下数据会被先加载到三级缓存中，然后再次进行访问；
同时，计算机领域有一个局部性原理：当我们访问一个数据时，我们极有可能也会访问其周边的数据；所以在将数据加载到缓存时，我们并不是只将我们要访问的那个数据加载到缓存中，而是会将该数据所在的一长段内存空间的数据都加载到缓存中去，具体加载多少个字节取决于硬件；
对于我们的顺序表来说，它其中的数据是连续存放的，所以我们访问其中的数据不需要每次访问都去加载数据，可能我们第一次访问加载数据之后，我们第十次访问才再次加载数据；
而对于我们的链表来说，链表的每个节点的地址是不具有关联性的，所以在多数情况下我们加载一个数据所在的一长段内存空间时，该内存空间并不包含该节点后面的节点；从而使得我们的 CPU 在访问数据时需要去频繁的去加载数据，导致效率降低；
另外，链表加载数据时还会造成缓存污染，因为我们会将一个数据所在的一长段内存空间的数据都加载到缓存中去，而由于其后面的空间中可能并不包含链表的其他节点，即我们将无用的数据加载进了缓存中，就会造成缓存污染；
关于缓存的更多知识可以参考下面这篇文章：与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell
