阅读量:0
目录
1、双向链表的结构
注意：这⾥的“带头“跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“放哨的”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”。
“哨兵位”存在的意义：遍历循环链表避免死循环。
2、顺序表和双向链表的优缺点分析
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持O(N) |
| 任意位置插⼊或者删除元素 | 可能需要搬移元素，效率低 | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储和频繁访问 | 任意位置频繁插入和删除 |
3、双向链表的实现
ListNode.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> //定义双向链表节点的结构 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); //尾删 LtPopBack(ListNode* phead); //头删 LtPopFront(ListNode* phead); //查找 ListNode* LtFind(ListNode* phead, Ltdatatype x); //指定位置前插入 void LtInsert(ListNode* pos, Ltdatatype x); //删除pos位置 void LtErase(ListNode* pos); //销毁链表 void LtDestroy(ListNode* phead); ListNode.c
#define _CRT_SECURE_NO_WARNINGS #include "ListNode.h" //申请节点 ListNode* LtBuyNode(Ltdatatype x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (node == NULL) { perror("malloc fail"); exit(1); } //申请成功 node->data = x; node->next = node->prev = node; return node; } //双向链表的初始化 ListNode* LtInit() { ListNode*phead = LtBuyNode(-1); return phead; } //尾插 void LtPushBack(ListNode* phead, Ltdatatype x) { assert(phead); ListNode* newnode = LtBuyNode(x); //改变新节点的指向 newnode->prev = phead->prev; newnode->next = phead; //改变尾节点和哨兵位的指向 phead->prev->next = newnode; phead->prev = newnode; } //打印链表 void LtPrint(ListNode* phead) { ListNode* pcur = phead->next; //遍历链表 while (pcur != phead) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); } //头插 void LtPushFront(ListNode* phead,Ltdatatype x) { assert(phead); ListNode* newnode = LtBuyNode(x); newnode->prev = phead; newnode->next = phead->next; //修改哨兵位和第一个有效节点的指向 phead->next->prev = newnode; phead->next = newnode; } //尾删 LtPopBack(ListNode* phead) { //链表必须有效且链表不能为空（只有一个哨兵位） assert(phead && phead->next != phead); ListNode* Del = phead->prev;//尾节点 ListNode* DelPrev = Del->prev;//尾节点的前一个节点 phead->prev = DelPrev; DelPrev->next = phead; free(Del);//删除Del节点 Del = NULL; } //头删 LtPopFront(ListNode* phead) { //判断链表是否有效和链表是否为空 assert(phead && phead->next != phead); ListNode* Del = phead->next;//第一个有效节点 ListNode* DelNext = Del->next;//有效节点的下一个节点 phead->next = DelNext; DelNext->prev = phead; free(Del);//删除Del节点 Del = NULL; } //查找 ListNode* LtFind(ListNode* phead, Ltdatatype x) { ListNode* pcur = phead->next; //遍历链表 while (pcur != phead) { if (pcur->data == x) return pcur; pcur = pcur->next;//继续让pcur往下遍历 } return NULL;//没有找到 } //在pos位置之前插入数据 void LtInsert(ListNode* pos,Ltdatatype x) { ListNode* newnode = LtBuyNode(x); newnode->prev = pos->prev; newnode->next = pos; pos->prev->next = newnode; pos->prev = newnode; } //删除pos位置 void LtErase(ListNode* pos) { assert(pos); ListNode* PosPrev = pos->prev;//pos的前一个节点 ListNode* PosNext = pos->next;//pos的后一个节点 PosPrev->next = PosNext; PosNext->prev = PosPrev; free(pos); //pos = NULL;这里就算置空了，也不会影响实参 } //销毁链表 void LtDestroy(ListNode* phead) { ListNode* pcur = phead->next; //边遍历边释放节点 while (pcur != phead) { ListNode* Next = pcur->next;//保存要释放掉节点的下一个地址 free(pcur); pcur = Next; } //此时pcur指向phead，而phead还没有被销毁 free(phead); pcur = NULL; } text.c
#define _CRT_SECURE_NO_WARNINGS #include "ListNode.h" void LtnodeTest() { //测试初始化 ListNode* plist = LtInit(); //测试尾插 LtPushBack(plist,1); LtPushBack(plist,2); LtPushBack(plist,3); //测试打印 LtPrint(plist); //测试头插 //LtPushFront(plist,4); //LtPushFront(plist,5); //LtPushFront(plist,6); //LtPrint(plist); //测试尾删 LtPopBack(plist); LtPrint(plist); //测试头删 //LtPopFront(plist); //LtPrint(plist); //测试查找 //ListNode*find = LtFind(plist,2); //if (find) // printf("找到了！\n"); //else // printf("没找到！\n"); //测试在pos位置之前插入数据 //LtInsert(find,88); //LtPrint(plist); //测试删除pos位置 //LtErase(find); //find = NULL;//形参的改变不会影响实参，所以要在函数调用结束之后置为空 //LtPrint(plist); //测试销毁链表 //LtDestroy(plist); //plist = NULL; } int main() { LtnodeTest(); return 0; } 如果对你有所帮助的话，别忘了一键三连哟，谢谢宝子们😘！
