一、引言在介绍完单链表之后还有一种常见的经常使用的链表结构——带头双向循环链表。接下来介绍一下这个结构。二、带头双向循环链表具体介绍带头指的是带头节点我们单链表所说的头节点是第一个节点带第一个有效数据的但是这里的头结点它是第一个节点但它不携带有效数据。比如在整型数据的链表里它可能就带-1这个-1不是我们想存储的数据。这样子头结点之后的节点存储的就是我们想存储的有效数据。双向每个节点有指向后节点的next指针也有指向前节点的prev指针。循环最后一个节点之后不是NULL而是头结点。也就是说走完最后一个节点会回到头结点。三、带头双向循环链表的代码实现依然分为三个文件。DCList.h文件// DCList.h #include stdio.h #include stdlib.h #include assert.h typedef int DCLDataType; typedef struct DCListNode { DCLDataType data; // 存储数据元素的值 struct DCListNode* prev; // 存放前驱结点的指针 struct DCListNode* next; // 存放后继结点的指针 }DCListNode; // 链表初始化 DCListNode* DCListInit(); // 销毁链表 void DCListDestroy(DCListNode* L); // 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i); // 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x); // 删除pos位置的结点 void DCListDelete(DCListNode* pos); // 头插 void DCListPushFront(DCListNode* L, DCLDataType x); // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x); // 头删 void DCListPopFront(DCListNode* L); // 尾删 void DCListPopBack(DCListNode* L); // 打印链表中的元素 void DCListPrint(DCListNode* L);接下来依次实现1.创建一个新节点// 创建一个新结点 DCListNode* BuyDCListNode(int data) { // 不能创建一个LNode的结构体变量因为局部变量出了作用域就销毁了 // 所以这里用malloc从堆上动态申请结点并检测是否申请成功 DCListNode* newNode (DCListNode*)malloc(sizeof(DCListNode)); if (NULL newNode) { printf(BuyListNode失败!!!\n); exit(-1); } // 申请成功后对结点中的数据域和指针域进行初始化 newNode-data data; newNode-next NULL; newNode-prev NULL; return newNode; }2、链表初始化// 链表初始化 DCListNode* DCListInit() { DCListNode* L BuyDCListNode(-1); L-next L; L-prev L; return L; }创建一个带数据-1的头结点把头结点的prev和next都置为L使得头结点也可以维持带头双向循环链表的特质。在后面插入时有用。返回头结点的头指针。3、销毁链表// 销毁链表 void DCListDestroy(DCListNode* L) { assert(L); DCListNode* cur L-next; while (cur ! L) { DCListNode* next cur-next; free(cur); cur next; } free(L); }从头结点后的第一个节点开始用cur和next两个指针每次循环定义next为cur-next释放cur再让cur往后移动直到cur为头结点时结束循环最后释放头结点即可。注意不能从头结点开始释放不然就找不到链表的尾了。因为你最后cur要回到L才算释放完成4、获取链表的下标i的节点// 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i) { assert(L); assert(i 0); // 2. 从链表头结点之后开始逐个往后找第i个结点 DCListNode* cur L-next; int j 0; while (cur ! L j i) { cur cur-next; j; } // j i说明没第i个结点参数i非法 assert(j i); return cur; }这里的cur从L-next开始此时下标为0j也为零j就是下标此后每往后移动j代表下标直到回到头指针代表结束或者j下标已经等于要获取的下标i结束。然后assert断言判断目前下标是否等于要找的下标i不等于肯定是非法了你要访问的i不在可访问范围内。这里当curL时跳出循环如果链表有两个元素而我们要访问下标为2。则我们会访问到头结点此时返回的就是头指针数据也是-1。会让你知道是非法的。或者说你可以改成// 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i) { assert(L); assert(i0); DCListNode*curL-next; int j0; while (cur-next ! L j i) { curcur-next; j; } assert(ij); return cur; }这样子只到最后一个不会到头结点即使2个元素下标为01i下标为2也只会到1最后一个节点就结束循环最后assert断言告诉你错误。例子四个元素时//下标为3 DCListNode* pos2 DCListGetElem(L, 3); printf(%d \n,pos2-data); //下标为4 DCListNode* pos3 DCListGetElem(L, 4); printf(%d \n, pos2-data);5、打印链表中的元素// 打印链表中的元素 void DCListPrint(DCListNode* L) { // 从前往后打印链表 //printf(头结点-); DCListNode* cur L-next; while (cur ! L) { printf(%d-, cur-data); cur cur-next; } printf(\n); // 从后往前打印链表 /* cur L-prev; while (cur ! L) { printf(%d-, cur-data); cur cur-prev; } printf(\n);*/ }找一个cur指针遍历即可结束标志是cur到头L了就不打印了。6、在pos位置后插入值为x的节点// 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x) { assert(pos); DCListNode* newNode BuyDCListNode(x); // 无关顺序 //DCListNode* posNext pos-next; //// pos newNode posNext //pos-next newNode; //newNode-prev pos; //newNode-next posNext; //posNext-prev newNode; // 注意顺序 newNode-next pos-next; pos-next-prev newNode; pos-next newNode; newNode-prev pos; }两种方法第一种你可以先用一个Next指针记录pos-next,然后依次连接。第二种不记录下一个节点直接连接。如果这样需要注意连接顺序。先连接后节点与新节点否则你没有记录后结点前节点与新节点连上之后找不到后结点了next已经改变为newnode)。7、头插// 头插 void DCListPushFront(DCListNode* L, DCLDataType x){ assert(L); DCListInsert(L, x); }复用前面代码pos即为头结点L。8、尾插// 尾插 void DCListPushBack(DCListNode* L, DCLDataType x){ assert(L); DCListInsert(L-prev, x); }复用前面代码pos即为L-prev也就是尾节点。9、删除pos位置节点// 删除pos位置的结点 void DCListDelete(DCListNode* pos) { assert(pos); pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); }让前结点(pos-prev)的next改成后结点后结点(pos-next)的prev改为前结点最后free(pos)就行了。10、头删// 头删 void DCListPopFront(DCListNode* L) { assert(L); assert(L-next!L);//保证不为空 DCListDelete(L-next); }复用前面代码pos为L-next删除第一个元素。11、尾删// 尾删 void DCListPopBack(DCListNode* L) { assert(L); assert(L-next ! L); DCListDelete(L-prev); }复用前面代码pos为L-prev就是最后一个元素。四、所有任务文件DCList.h:// DCList.h #include stdio.h #include stdlib.h #include assert.h typedef int DCLDataType; typedef struct DCListNode { DCLDataType data; // 存储数据元素的值 struct DCListNode* prev; // 存放前驱结点的指针 struct DCListNode* next; // 存放后继结点的指针 }DCListNode; // 链表初始化 DCListNode* DCListInit(); // 销毁链表 void DCListDestroy(DCListNode* L); // 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i); // 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x); // 删除pos位置的结点 void DCListDelete(DCListNode* pos); // 头插 void DCListPushFront(DCListNode* L, DCLDataType x); // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x); // 头删 void DCListPopFront(DCListNode* L); // 尾删 void DCListPopBack(DCListNode* L); // 打印链表中的元素 void DCListPrint(DCListNode* L);DCList.c:#includeDCList.h // 创建一个新结点 DCListNode* BuyDCListNode(int data) { // 不能创建一个LNode的结构体变量因为局部变量出了作用域就销毁了 // 所以这里用malloc从堆上动态申请结点并检测是否申请成功 DCListNode* newNode (DCListNode*)malloc(sizeof(DCListNode)); if (NULL newNode) { printf(BuyListNode失败!!!\n); exit(-1); } // 申请成功后对结点中的数据域和指针域进行初始化 newNode-data data; newNode-next NULL; newNode-prev NULL; return newNode; } // 链表初始化 DCListNode* DCListInit() { DCListNode* L BuyDCListNode(-1); L-next L; L-prev L; return L; } // 销毁链表 void DCListDestroy(DCListNode* L) { assert(L); DCListNode* cur L-next; while (cur ! L) { DCListNode* next cur-next; free(cur); cur next; } free(L); } // 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i) { assert(L); assert(i 0); // 2. 从链表头结点之后开始逐个往后找第i个结点 DCListNode* cur L-next; int j 0; while (cur ! L j i) { cur cur-next; j; } // j i说明没第i个结点参数i非法 assert(j i); return cur; } // 打印链表中的元素 void DCListPrint(DCListNode* L) { // 从前往后打印链表 //printf(头结点-); DCListNode* cur L-next; while (cur ! L) { printf(%d-, cur-data); cur cur-next; } printf(\n); // 从后往前打印链表 /* cur L-prev; while (cur ! L) { printf(%d-, cur-data); cur cur-prev; } printf(\n);*/ } // 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x) { assert(pos); DCListNode* newNode BuyDCListNode(x); // 无关顺序 //DCListNode* posNext pos-next; //// pos newNode posNext //pos-next newNode; //newNode-prev pos; //newNode-next posNext; //posNext-prev newNode; // 注意顺序 newNode-next pos-next; pos-next-prev newNode; pos-next newNode; newNode-prev pos; } // 头插 void DCListPushFront(DCListNode* L, DCLDataType x){ assert(L); DCListInsert(L, x); } // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x){ assert(L); DCListInsert(L-prev, x); } // 删除pos位置的结点 void DCListDelete(DCListNode* pos) { assert(pos); pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); } // 头删 void DCListPopFront(DCListNode* L) { assert(L); assert(L-next ! L); // 空 DCListDelete(L-next); } // 尾删 void DCListPopBack(DCListNode* L) { assert(L); assert(L-next ! L); // 空 DCListDelete(L-prev); }Test.c:#includeDCList.h int main() { DCListNode* L DCListInit(); DCListPushBack(L, 1); DCListPushBack(L, 2); DCListPushBack(L, 3); DCListPushBack(L, 4); DCListPrint(L); DCListPushFront(L, 10); DCListPushFront(L, 20); DCListPushFront(L, 30); DCListPushFront(L, 40); DCListPrint(L); DCListPopFront(L); DCListPopFront(L); DCListPrint(L); DCListPopBack(L); DCListPopBack(L); DCListPrint(L); printf(\n\n); DCListNode* pos DCListGetElem(L, 2); DCListInsert(pos, 200); DCListPrint(L); pos DCListGetElem(L, 2); DCListDelete(pos); DCListPrint(L); DCListNode* pos2 DCListGetElem(L, 3); printf(%d \n,pos2-data); DCListNode* pos3 DCListGetElem(L, 4); printf(%d \n, pos2-data); return 0; }五、总结带头双向循环链表的优势主要体现在两⽅⾯第⼀可以通过头结点的prev快速找到尾结点以O1的高效实现尾插尾删第⼆pos结点位置插⼊删除时可以更简单因为不需要考虑尾结点的的后继结点为空的情况。六、顺序表与链表的比较学完了两个数据结构对比一下顺序表和链表。• 顺序表和链表都是线性表逻辑结构都是线性结构最⼤的区别是存储结构(物理结构)不同顺序表采⽤连续物理单元存储⼀组数据链表采⽤任意存储单元存储数据数据元素之间指针关系链 接。• 顺序表的优点1、⽀持下标的随机访问实践中这个点⾮常有⽤⽐如排序、排序后⼆分查找 优先级队列都适合在顺序表这种数据结构上进⾏。2、顺序表cpu缓存命中率很⾼没有内存碎⽚等 也是他很⼤的优点。• 顺序表的缺点1、插⼊删除数据要挪动数据(除了尾插/尾删)复杂度为 O(N)所以他只适合⼤ 量尾插尾删的场景。2、空间不够时需要扩容扩容是有⼀定的代价的且可能会存在⼀定的空间 浪费。• 链表的优点1、按需申请释放空间不需要扩容。2、双向循环链表确定位置的情况下可以实现任意位置 O(1) 的插⼊删除不需要挪动数据。• 链表的缺点1、不⽀持下标的随机访问。2、链表的cpu缓存命中率相对低且会导致内存碎⽚问 题。• 通过上述的对⽐我们会发现这两个数据结构是相辅相成的顺序表的优点弥补了链表的缺点链表的优点弥补了顺序表的缺点所以实践中是分析使⽤场景来选择合适的数据结构。如果觉得讲的不错可以收藏点赞关注三连谢谢 数据结构（C语言版）：4.带头双向循环链表
一、引言在介绍完单链表之后还有一种常见的经常使用的链表结构——带头双向循环链表。接下来介绍一下这个结构。二、带头双向循环链表具体介绍带头指的是带头节点我们单链表所说的头节点是第一个节点带第一个有效数据的但是这里的头结点它是第一个节点但它不携带有效数据。比如在整型数据的链表里它可能就带-1这个-1不是我们想存储的数据。这样子头结点之后的节点存储的就是我们想存储的有效数据。双向每个节点有指向后节点的next指针也有指向前节点的prev指针。循环最后一个节点之后不是NULL而是头结点。也就是说走完最后一个节点会回到头结点。三、带头双向循环链表的代码实现依然分为三个文件。DCList.h文件// DCList.h #include stdio.h #include stdlib.h #include assert.h typedef int DCLDataType; typedef struct DCListNode { DCLDataType data; // 存储数据元素的值 struct DCListNode* prev; // 存放前驱结点的指针 struct DCListNode* next; // 存放后继结点的指针 }DCListNode; // 链表初始化 DCListNode* DCListInit(); // 销毁链表 void DCListDestroy(DCListNode* L); // 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i); // 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x); // 删除pos位置的结点 void DCListDelete(DCListNode* pos); // 头插 void DCListPushFront(DCListNode* L, DCLDataType x); // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x); // 头删 void DCListPopFront(DCListNode* L); // 尾删 void DCListPopBack(DCListNode* L); // 打印链表中的元素 void DCListPrint(DCListNode* L);接下来依次实现1.创建一个新节点// 创建一个新结点 DCListNode* BuyDCListNode(int data) { // 不能创建一个LNode的结构体变量因为局部变量出了作用域就销毁了 // 所以这里用malloc从堆上动态申请结点并检测是否申请成功 DCListNode* newNode (DCListNode*)malloc(sizeof(DCListNode)); if (NULL newNode) { printf(BuyListNode失败!!!\n); exit(-1); } // 申请成功后对结点中的数据域和指针域进行初始化 newNode-data data; newNode-next NULL; newNode-prev NULL; return newNode; }2、链表初始化// 链表初始化 DCListNode* DCListInit() { DCListNode* L BuyDCListNode(-1); L-next L; L-prev L; return L; }创建一个带数据-1的头结点把头结点的prev和next都置为L使得头结点也可以维持带头双向循环链表的特质。在后面插入时有用。返回头结点的头指针。3、销毁链表// 销毁链表 void DCListDestroy(DCListNode* L) { assert(L); DCListNode* cur L-next; while (cur ! L) { DCListNode* next cur-next; free(cur); cur next; } free(L); }从头结点后的第一个节点开始用cur和next两个指针每次循环定义next为cur-next释放cur再让cur往后移动直到cur为头结点时结束循环最后释放头结点即可。注意不能从头结点开始释放不然就找不到链表的尾了。因为你最后cur要回到L才算释放完成4、获取链表的下标i的节点// 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i) { assert(L); assert(i 0); // 2. 从链表头结点之后开始逐个往后找第i个结点 DCListNode* cur L-next; int j 0; while (cur ! L j i) { cur cur-next; j; } // j i说明没第i个结点参数i非法 assert(j i); return cur; }这里的cur从L-next开始此时下标为0j也为零j就是下标此后每往后移动j代表下标直到回到头指针代表结束或者j下标已经等于要获取的下标i结束。然后assert断言判断目前下标是否等于要找的下标i不等于肯定是非法了你要访问的i不在可访问范围内。这里当curL时跳出循环如果链表有两个元素而我们要访问下标为2。则我们会访问到头结点此时返回的就是头指针数据也是-1。会让你知道是非法的。或者说你可以改成// 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i) { assert(L); assert(i0); DCListNode*curL-next; int j0; while (cur-next ! L j i) { curcur-next; j; } assert(ij); return cur; }这样子只到最后一个不会到头结点即使2个元素下标为01i下标为2也只会到1最后一个节点就结束循环最后assert断言告诉你错误。例子四个元素时//下标为3 DCListNode* pos2 DCListGetElem(L, 3); printf(%d \n,pos2-data); //下标为4 DCListNode* pos3 DCListGetElem(L, 4); printf(%d \n, pos2-data);5、打印链表中的元素// 打印链表中的元素 void DCListPrint(DCListNode* L) { // 从前往后打印链表 //printf(头结点-); DCListNode* cur L-next; while (cur ! L) { printf(%d-, cur-data); cur cur-next; } printf(\n); // 从后往前打印链表 /* cur L-prev; while (cur ! L) { printf(%d-, cur-data); cur cur-prev; } printf(\n);*/ }找一个cur指针遍历即可结束标志是cur到头L了就不打印了。6、在pos位置后插入值为x的节点// 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x) { assert(pos); DCListNode* newNode BuyDCListNode(x); // 无关顺序 //DCListNode* posNext pos-next; //// pos newNode posNext //pos-next newNode; //newNode-prev pos; //newNode-next posNext; //posNext-prev newNode; // 注意顺序 newNode-next pos-next; pos-next-prev newNode; pos-next newNode; newNode-prev pos; }两种方法第一种你可以先用一个Next指针记录pos-next,然后依次连接。第二种不记录下一个节点直接连接。如果这样需要注意连接顺序。先连接后节点与新节点否则你没有记录后结点前节点与新节点连上之后找不到后结点了next已经改变为newnode)。7、头插// 头插 void DCListPushFront(DCListNode* L, DCLDataType x){ assert(L); DCListInsert(L, x); }复用前面代码pos即为头结点L。8、尾插// 尾插 void DCListPushBack(DCListNode* L, DCLDataType x){ assert(L); DCListInsert(L-prev, x); }复用前面代码pos即为L-prev也就是尾节点。9、删除pos位置节点// 删除pos位置的结点 void DCListDelete(DCListNode* pos) { assert(pos); pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); }让前结点(pos-prev)的next改成后结点后结点(pos-next)的prev改为前结点最后free(pos)就行了。10、头删// 头删 void DCListPopFront(DCListNode* L) { assert(L); assert(L-next!L);//保证不为空 DCListDelete(L-next); }复用前面代码pos为L-next删除第一个元素。11、尾删// 尾删 void DCListPopBack(DCListNode* L) { assert(L); assert(L-next ! L); DCListDelete(L-prev); }复用前面代码pos为L-prev就是最后一个元素。四、所有任务文件DCList.h:// DCList.h #include stdio.h #include stdlib.h #include assert.h typedef int DCLDataType; typedef struct DCListNode { DCLDataType data; // 存储数据元素的值 struct DCListNode* prev; // 存放前驱结点的指针 struct DCListNode* next; // 存放后继结点的指针 }DCListNode; // 链表初始化 DCListNode* DCListInit(); // 销毁链表 void DCListDestroy(DCListNode* L); // 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i); // 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x); // 删除pos位置的结点 void DCListDelete(DCListNode* pos); // 头插 void DCListPushFront(DCListNode* L, DCLDataType x); // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x); // 头删 void DCListPopFront(DCListNode* L); // 尾删 void DCListPopBack(DCListNode* L); // 打印链表中的元素 void DCListPrint(DCListNode* L);DCList.c:#includeDCList.h // 创建一个新结点 DCListNode* BuyDCListNode(int data) { // 不能创建一个LNode的结构体变量因为局部变量出了作用域就销毁了 // 所以这里用malloc从堆上动态申请结点并检测是否申请成功 DCListNode* newNode (DCListNode*)malloc(sizeof(DCListNode)); if (NULL newNode) { printf(BuyListNode失败!!!\n); exit(-1); } // 申请成功后对结点中的数据域和指针域进行初始化 newNode-data data; newNode-next NULL; newNode-prev NULL; return newNode; } // 链表初始化 DCListNode* DCListInit() { DCListNode* L BuyDCListNode(-1); L-next L; L-prev L; return L; } // 销毁链表 void DCListDestroy(DCListNode* L) { assert(L); DCListNode* cur L-next; while (cur ! L) { DCListNode* next cur-next; free(cur); cur next; } free(L); } // 获取链表的下标i的结点 DCListNode* DCListGetElem(DCListNode* L, int i) { assert(L); assert(i 0); // 2. 从链表头结点之后开始逐个往后找第i个结点 DCListNode* cur L-next; int j 0; while (cur ! L j i) { cur cur-next; j; } // j i说明没第i个结点参数i非法 assert(j i); return cur; } // 打印链表中的元素 void DCListPrint(DCListNode* L) { // 从前往后打印链表 //printf(头结点-); DCListNode* cur L-next; while (cur ! L) { printf(%d-, cur-data); cur cur-next; } printf(\n); // 从后往前打印链表 /* cur L-prev; while (cur ! L) { printf(%d-, cur-data); cur cur-prev; } printf(\n);*/ } // 在pos位置后插入值为x的结点 void DCListInsert(DCListNode* pos, DCLDataType x) { assert(pos); DCListNode* newNode BuyDCListNode(x); // 无关顺序 //DCListNode* posNext pos-next; //// pos newNode posNext //pos-next newNode; //newNode-prev pos; //newNode-next posNext; //posNext-prev newNode; // 注意顺序 newNode-next pos-next; pos-next-prev newNode; pos-next newNode; newNode-prev pos; } // 头插 void DCListPushFront(DCListNode* L, DCLDataType x){ assert(L); DCListInsert(L, x); } // 尾插 void DCListPushBack(DCListNode* L, DCLDataType x){ assert(L); DCListInsert(L-prev, x); } // 删除pos位置的结点 void DCListDelete(DCListNode* pos) { assert(pos); pos-next-prev pos-prev; pos-prev-next pos-next; free(pos); } // 头删 void DCListPopFront(DCListNode* L) { assert(L); assert(L-next ! L); // 空 DCListDelete(L-next); } // 尾删 void DCListPopBack(DCListNode* L) { assert(L); assert(L-next ! L); // 空 DCListDelete(L-prev); }Test.c:#includeDCList.h int main() { DCListNode* L DCListInit(); DCListPushBack(L, 1); DCListPushBack(L, 2); DCListPushBack(L, 3); DCListPushBack(L, 4); DCListPrint(L); DCListPushFront(L, 10); DCListPushFront(L, 20); DCListPushFront(L, 30); DCListPushFront(L, 40); DCListPrint(L); DCListPopFront(L); DCListPopFront(L); DCListPrint(L); DCListPopBack(L); DCListPopBack(L); DCListPrint(L); printf(\n\n); DCListNode* pos DCListGetElem(L, 2); DCListInsert(pos, 200); DCListPrint(L); pos DCListGetElem(L, 2); DCListDelete(pos); DCListPrint(L); DCListNode* pos2 DCListGetElem(L, 3); printf(%d \n,pos2-data); DCListNode* pos3 DCListGetElem(L, 4); printf(%d \n, pos2-data); return 0; }五、总结带头双向循环链表的优势主要体现在两⽅⾯第⼀可以通过头结点的prev快速找到尾结点以O1的高效实现尾插尾删第⼆pos结点位置插⼊删除时可以更简单因为不需要考虑尾结点的的后继结点为空的情况。六、顺序表与链表的比较学完了两个数据结构对比一下顺序表和链表。• 顺序表和链表都是线性表逻辑结构都是线性结构最⼤的区别是存储结构(物理结构)不同顺序表采⽤连续物理单元存储⼀组数据链表采⽤任意存储单元存储数据数据元素之间指针关系链 接。• 顺序表的优点1、⽀持下标的随机访问实践中这个点⾮常有⽤⽐如排序、排序后⼆分查找 优先级队列都适合在顺序表这种数据结构上进⾏。2、顺序表cpu缓存命中率很⾼没有内存碎⽚等 也是他很⼤的优点。• 顺序表的缺点1、插⼊删除数据要挪动数据(除了尾插/尾删)复杂度为 O(N)所以他只适合⼤ 量尾插尾删的场景。2、空间不够时需要扩容扩容是有⼀定的代价的且可能会存在⼀定的空间 浪费。• 链表的优点1、按需申请释放空间不需要扩容。2、双向循环链表确定位置的情况下可以实现任意位置 O(1) 的插⼊删除不需要挪动数据。• 链表的缺点1、不⽀持下标的随机访问。2、链表的cpu缓存命中率相对低且会导致内存碎⽚问 题。• 通过上述的对⽐我们会发现这两个数据结构是相辅相成的顺序表的优点弥补了链表的缺点链表的优点弥补了顺序表的缺点所以实践中是分析使⽤场景来选择合适的数据结构。如果觉得讲的不错可以收藏点赞关注三连谢谢