
目录

这里的双向链表,准确的说是:带头双向循环链表
这里的“头节点”指的是“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这⾥“放哨
的”。
“哨兵位”存在的意义:遍历循环链表避免死循环。
注意⚠️
双向链表的每一个节点存储一个有效数据+下一个节点的地址+上一个节点的地址
头节点和尾节点有些特殊:头节点指向的上一个节点的地址是尾节点,尾节点指向的下一个节点的地址是头节点
我们需要多个接口帮助我们实现:创建、一系列具体操作、销毁
具体操作包括:头部/尾部插入数据、头部/尾部删除数据、打印出双向链表、指定节点之后插入数据、删除指定节点的数据、查找指定节点
- #include
- #include
- #include
-
- typedef int LTDataType;
- //创建双向链表的结构体
- typedef struct ListNode {
- LTDataType data;
- struct ListNode* prev;
- struct ListNode* next;
- }ListNode;
-
- //初始化
- ListNode* LTInit();//不用传入参数,直接调用接口返回一个头节点
- #include"List.h"
- //初始化
- ListNode* LTInit()//不用传入参数,直接调用接口返回一个头节点
- {
- //为头节点申请空间
- ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
- //判断开辟是否成功
- if (phead == NULL)
- {
- perror("malloc error!\n");
- return;
- }
- //开辟成功--->初始化头节点
- phead->data = -1;//头节点不存储有效数据,可以任意赋值
- //只有哨兵位的时候,要实现双向链表,不能指向NULL,否则无法双向循环,所以我们指向自己
- phead->prev = phead->next = phead;
- return phead;
- }
- #include"List.h"
- void ListTest()
- {
- ListNode* plist = LTInit();
- }
- int main()
- {
- ListTest();
- return 0;
- }




- //在双向链表中不会改变哨兵位,所以这里都可以传一级指针
- //尾插
- void LTPushBack(ListNode* phead, LTDataType x);
-
- //打印
- void LTPrint(ListNode* phead);
-
- //头插
- void LTPushFront(ListNode* phead, LTDataType x);
- //在双向链表中不会改变哨兵位,所以这里都可以传一级指针
- // 只改变数据,不改变地址
-
- //开辟空间
- ListNode* ListBuyNode(LTDataType x)
- {
- ListNode* node = (ListNode*)malloc(sizeof(ListNode));
- if (node == NULL)
- {
- perror("malloc error!\n");
- return;
- }
- node->data = x;
- node->next = node->prev = NULL;
- return node;
- }
-
- //尾插
- void LTPushBack(ListNode* phead, LTDataType x)
- {
- assert(phead);//注意哨兵位不能为空
- //申请空间
- ListNode* node = ListBuyNode(x);
- //先处理node的前驱指针和后继指针
- node->prev = phead->prev;
- node->next = phead;
- //再处理之前的尾节点和phead
- phead->prev->next = node;
- phead->prev = node;
- }
-
- //打印
- void LTPrint(ListNode* phead)
- {
- //哨兵位不能改变
- ListNode* cur = phead->next;
- while (cur != phead)//当cur再次指向phead的时候,循环结束
- {
- printf("%d->", cur->data);
- cur = cur->next;
- }
- printf("\n");
- }
-
- //头插
- void LTPushFront(ListNode* phead, LTDataType x)
- {
- assert(phead);//注意哨兵位不能为空
- //申请空间
- ListNode* node = ListBuyNode(x);
- //node插入头节点之后才算头插
- //先处理node的前驱指针和后继指针
- node->prev = phead;
- node->next = phead->next;
- //再处理phead和phead->next
- phead->next->prev = node;
- phead->next = node;
- }
- #include"List.h"
- void ListTest()
- {
- ListNode* plist = LTInit();
- LTPushBack(plist, 1);
- LTPushBack(plist, 2);
- LTPushBack(plist, 3);
- LTPushBack(plist, 4);
- LTPrint(plist);//1 2 3 4
- LTPushFront(plist, 5);
- LTPrint(plist);//5 1 2 3 4
- }
- int main()
- {
- ListTest();
- return 0;
- }



- //尾删
- void LTPopBack(ListNode* phead);
-
- //头删
- void LTPopFront(ListNode* phead);
- //尾删
- void LTPopBack(ListNode* phead)
- {
- //不能为空链表,只有一个哨兵位不能尾删
- assert(phead&&(phead->prev!=phead||phead->next!=phead));
- ListNode* del = phead->prev;//phead->prev就是尾节点
- //先处理del
- del->prev->next = phead;
- //再处理phead
- phead->prev = del->prev;
- free(del);
- del = NULL;
- }
-
- //头删
- void LTPopFront(ListNode* phead)
- {
- //不能为空链表,只有一个哨兵位不能头删
- assert(phead && (phead->prev != phead || phead->next != phead));
- ListNode* del = phead->next;
- del->next->prev = phead;
- phead->next = del->next;
- free(del);
- del = NULL;
- }
- #include"List.h"
- void ListTest()
- {
- ListNode* plist = LTInit();
- LTPushBack(plist, 1);
- LTPushBack(plist, 2);
- LTPushBack(plist, 3);
- LTPushBack(plist, 4);
- LTPrint(plist);//1 2 3 4
- LTPushFront(plist, 5);
- LTPrint(plist);//5 1 2 3 4
- LTPopBack(plist);
- LTPrint(plist);//5 1 2 3
- LTPopFront(plist);
- LTPrint(plist);//1 2 3
- }
- int main()
- {
- ListTest();
- return 0;
- }



- //查找数据
- ListNode* LTFind(ListNode* phead, LTDataType x);
-
- //pos节点之后插入
- void LTPushAfter(ListNode* pos, LTDataType x);
-
- //删除pos节点
- void LTErase(ListNode* pos);
- //查找数据
- ListNode* LTFind(ListNode* phead, LTDataType x)
- {
- assert(phead);
- ListNode* cur = phead->next;
- while (cur!= phead)
- {
- if (cur->data == x)
- {
- return cur;
- }
- cur = cur->next;
- }
- return NULL;
- }
-
- //pos节点之后插入
- void LTPushAfter(ListNode* pos, LTDataType x)
- {
- assert(pos);
- ListNode* node = ListBuyNode(x);
- //node
- node->next = pos->next;
- node->prev = pos;
- //pos
- pos->next = node;
- node->next->prev = node;
- }
-
- //删除pos节点
- void LTErase(ListNode* pos)
- {
- assert(pos);
- pos->prev->next = pos->next;
- pos->next->prev = pos->prev;
- free(pos);
- pos = NULL;
- }
- #include"List.h"
- void ListTest()
- {
- ListNode* plist = LTInit();
- LTPushBack(plist, 1);
- LTPushBack(plist, 2);
- LTPushBack(plist, 3);
- LTPushBack(plist, 4);
- LTPrint(plist);//1 2 3 4
- LTPushFront(plist, 5);
- LTPrint(plist);//5 1 2 3 4
- LTPopBack(plist);
- LTPrint(plist);//5 1 2 3
- LTPopFront(plist);
- LTPrint(plist);//1 2 3
- ListNode* find = LTFind(plist, 1);
- /*LTPushAfter(find, 4);*/
- //LTPrint(plist);//1 4 2 3
- LTErase(find);
- LTPrint(plist);//2 3
-
- }
- int main()
- {
- ListTest();
- return 0;
- }


一开始的初始化,我们直接调用了接口,返回头节点进行初始化。我们没有考虑一级指针还是二级指针的问题。
那么,最后的销毁又该怎么办?是一级指针?还是二级指针?下面我们一一来尝试
- //销毁
- void LTDestroy(ListNode* phead);
- //销毁
- void LTDestroy(ListNode* phead)
- {
- assert(phead);
- ListNode* cur = phead->next;
- while(cur!=phead)
- {
- ListNode* next = cur->next;
- free(cur);
- cur = next;
- }
- //注意哨兵位还没有释放
- free(phead);
- phead = NULL;
- }
- #include"List.h"
- void ListTest()
- {
- ListNode* plist = LTInit();
- LTPushBack(plist, 1);
- LTPushBack(plist, 2);
- LTPushBack(plist, 3);
- LTPushBack(plist, 4);
- LTPrint(plist);//1 2 3 4
- //LTPushFront(plist, 5);
- //LTPrint(plist);//5 1 2 3 4
- //LTPopBack(plist);
- //LTPrint(plist);//5 1 2 3
- //LTPopFront(plist);
- //LTPrint(plist);//1 2 3
- //ListNode* find = LTFind(plist, 1);
- /*LTPushAfter(find, 4);*/
- LTPrint(plist);//1 4 2 3
- //LTErase(find);
- //LTPrint(plist);//2 3
- LTDestroy(plist);
-
- }
- int main()
- {
- ListTest();
- return 0;
- }

一级指针:
phead的改变不影响plist,phead释放之后,plist指向已经释放掉的空间——>把plist置为空那么置为空之前,还要不要将plist指向的空间再free一次?
我们尝试一下
那么再思考一下:一级指针是会导致phead的改变不影响plist,那么plist是什么没有改变?是指plist保存的值没有被改变还是plist的这块空间的地址没有被释放?


这里报错指的是plist指向无效地址
注意⚠️
如果plist的地址没有被释放,那么直接free(plist)是不会报错的所以在一级指针的情况下:plist的地址已经被释放了,没有被置为空的可以理解是plist的地址名称
2.6.5 一级指针的改进---test.c

- //销毁
- //void LTDestroy(ListNode* phead);
- void LTDestroy(ListNode** phead);
- //销毁
- void LTDestroy(ListNode** phead)
- {
- assert(phead && *phead);
- ListNode* cur = (*phead)->next;
- while (cur != *phead)
- {
- ListNode* next = cur->next;
- free(cur);
- cur = next;
- }
- free(*phead);
- *phead = NULL;
- }
- #include"List.h"
- void ListTest()
- {
- ListNode* plist = LTInit();
- LTPushBack(plist, 1);
- LTPushBack(plist, 2);
- LTPushBack(plist, 3);
- LTPushBack(plist, 4);
- LTPrint(plist);//1 2 3 4
- //LTPushFront(plist, 5);
- //LTPrint(plist);//5 1 2 3 4
- //LTPopBack(plist);
- //LTPrint(plist);//5 1 2 3
- //LTPopFront(plist);
- //LTPrint(plist);//1 2 3
- //ListNode* find = LTFind(plist, 1);
- ///*LTPushAfter(find, 4);*/
- LTPrint(plist);//1 4 2 3
- //LTErase(find);
- //LTPrint(plist);//2 3
- //LTDestroy(plist);
- //plist = NULL;
- LTDestroy(&plist);
- }
- int main()
- {
- ListTest();
- return 0;
- }

虽然,二级指针不用手动将plist置为空
但是,更推荐一级指针,因为其他接口基本上都是一级指针——>保持接口的一致性
- #pragma once
- #include
- #include
- #include
- #include
- #include
-
- typedef int LTDataType;
- //创建双向链表的结构体
- typedef struct ListNode {
- LTDataType data;
- struct ListNode* prev;
- struct ListNode* next;
- }ListNode;
-
- //初始化
- ListNode* LTInit();//不用传入参数,直接调用接口返回一个头节点
-
- //在双向链表中不会改变哨兵位,所以这里都可以传一级指针
- //尾插
- void LTPushBack(ListNode* phead, LTDataType x);
-
- //打印
- void LTPrint(ListNode* phead);
-
- //头插
- void LTPushFront(ListNode* phead, LTDataType x);
-
- //尾删
- void LTPopBack(ListNode* phead);
-
- //头删
- void LTPopFront(ListNode* phead);
-
- //查找数据
- ListNode* LTFind(ListNode* phead, LTDataType x);
-
- //pos节点之后插入
- void LTPushAfter(ListNode* pos, LTDataType x);
-
- //删除pos节点
- void LTErase(ListNode* pos);
-
- //销毁
- void LTDestroy(ListNode* phead);
- #include"List.h"
- //初始化
- ListNode* LTInit()//不用传入参数,直接调用接口返回一个头节点
- {
- //为头节点申请空间
- ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
- //判断开辟是否成功
- if (phead == NULL)
- {
- perror("malloc error!\n");
- return;
- }
- //开辟成功--->初始化头节点
- phead->data = -1;//头节点不存储有效数据,可以任意赋值
- //只有哨兵位的时候,要实现双向链表,不能指向NULL,否则无法双向循环,所以我们指向自己
- phead->prev = phead->next = phead;
- return phead;
- }
-
- //在双向链表中不会改变哨兵位,所以这里都可以传一级指针
- // 只改变数据,不改变地址
-
- //开辟空间
- ListNode* ListBuyNode(LTDataType x)
- {
- ListNode* node = (ListNode*)malloc(sizeof(ListNode));
- if (node == NULL)
- {
- perror("malloc error!\n");
- return;
- }
- node->data = x;
- node->next = node->prev = NULL;
- return node;
- }
-
- //尾插
- void LTPushBack(ListNode* phead, LTDataType x)
- {
- assert(phead);//注意哨兵位不能为空
- //申请空间
- ListNode* node = ListBuyNode(x);
- //先处理node的前驱指针和后继指针
- node->prev = phead->prev;
- node->next = phead;
- //再处理之前的尾节点和phead
- phead->prev->next = node;
- phead->prev = node;
- }
-
- //打印
- void LTPrint(ListNode* phead)
- {
- //哨兵位不能改变
- ListNode* cur = phead->next;
- while (cur != phead)//当cur再次指向phead的时候,循环结束
- {
- printf("%d->", cur->data);
- cur = cur->next;
- }
- printf("\n");
- }
-
- //头插
- void LTPushFront(ListNode* phead, LTDataType x)
- {
- assert(phead);//注意哨兵位不能为空
- //申请空间
- ListNode* node = ListBuyNode(x);
- //node插入头节点之后才算头插
- //先处理node的前驱指针和后继指针
- node->prev = phead;
- node->next = phead->next;
- //再处理phead和phead->next
- phead->next->prev = node;
- phead->next = node;
- }
-
- //尾删
- void LTPopBack(ListNode* phead)
- {
- //不能为空链表,只有一个哨兵位不能尾删
- assert(phead&&(phead->prev!=phead||phead->next!=phead));
- ListNode* del = phead->prev;//phead->prev就是尾节点
- //先处理del
- del->prev->next = phead;
- //再处理phead
- phead->prev = del->prev;
- free(del);
- del = NULL;
- }
-
- //头删
- void LTPopFront(ListNode* phead)
- {
- //不能为空链表,只有一个哨兵位不能头删
- assert(phead && (phead->prev != phead || phead->next != phead));
- ListNode* del = phead->next;
- del->next->prev = phead;
- phead->next = del->next;
- free(del);
- del = NULL;
- }
-
- //查找数据
- ListNode* LTFind(ListNode* phead, LTDataType x)
- {
- assert(phead);
- ListNode* cur = phead->next;
- while (cur != phead)
- {
- if (cur->data == x)
- {
- return cur;
- }
- cur = cur->next;
- }
- return NULL;
- }
-
- //pos节点之后插入
- void LTPushAfter(ListNode* pos, LTDataType x)
- {
- assert(pos);
- ListNode* node = ListBuyNode(x);
- //node
- node->next = pos->next;
- node->prev = pos;
- //pos
- pos->next = node;
- node->next->prev = node;
- }
-
- //删除pos节点
- void LTErase(ListNode* pos)
- {
- assert(pos);
- pos->prev->next = pos->next;
- pos->next->prev = pos->prev;
- free(pos);
- pos = NULL;
- }
-
- //销毁
- void LTDestroy(ListNode* phead)
- {
- assert(phead);
- ListNode* cur = phead->next;
- while(cur!=phead)
- {
- ListNode* next = cur->next;
- free(cur);
- cur = next;
- }
- //注意哨兵位还没有释放
- free(phead);
- phead = NULL;
- }
- #include"List.h"
- void ListTest()
- {
- ListNode* plist = LTInit();
- LTPushBack(plist, 1);
- LTPushBack(plist, 2);
- LTPushBack(plist, 3);
- LTPushBack(plist, 4);
- LTPrint(plist);//1 2 3 4
- LTPushFront(plist, 5);
- LTPrint(plist);//5 1 2 3 4
- LTPopBack(plist);
- LTPrint(plist);//5 1 2 3
- LTPopFront(plist);
- LTPrint(plist);//1 2 3
- ListNode* find = LTFind(plist, 1);
- /*LTPushAfter(find, 4);*/
- //LTPrint(plist);//1 4 2 3
- LTErase(find);
- LTPrint(plist);//2 3
- LTDestroy(plist);
- plist = NULL;
- }
- int main()
- {
- ListTest();
- return 0;
- }
| 不同点 | 顺序表 | 链表(单链表) |
| 存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持:O(N) |
| 任意位置插入或者删除元素 | 看你需要搬移元素,效率低O(N) | 只需要改变指针指向 |
| 插入 | 动态顺序表,空间不够的时候需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
本次的分享到这里就结束了!!!
PS:小江目前只是个新手小白。欢迎大家在评论区讨论哦!有问题也可以讨论的!
如果对你有帮助的话,记得点赞👍+收藏⭐️+关注➕
