带头结点单链表 完整实现（增删改查 + 清空销毁 ）

前言顺序表底层是数组插入删除需要挪动数据头部操作效率很低。而单链表通过指针把节点串联起来物理空间不连续插入删除不需要移动元素只需要修改指针指向是数据结构中最基础、最重要的知识点。一、什么是带头结点单链表1. 结构头结点head / 哨兵节点不存有效数据专门用来管理链表永远存在永远是第一个节点。有效节点存储真实数据。指针域 next指向后继节点。2. 优点为什么要用头结点统一空链表和非空链表的操作逻辑头插、头删不需要修改头指针代码更简洁、更少边界判断二、结构体设计及功能接口清单核心typedef int Elem_Type; //单链表有效结点的结构体设计 struct Node { Elem_Type data;//数据域(存储有效数据) struct Node* next;//指针域(存储下一个有效节点的地址) }; typedef struct Node Node; typedef struct Node* PNode; //typedef struct Node //{ // Elem_Type data;//数据域存储有效数据 // struct Node* next;//指针域存储下一个有效结点的地址 //}Node,*PNode; //可实现的操作 // //1.初始化 void Init_List(struct Node* head); //2.头插 bool Insert_head(struct Node* head, Elem_Type val); //3.尾插 bool Insert_tail(struct Node* tail, Elem_Type val); //4.按位置插 bool Insert_pos(struct Node* head, Elem_Type val,int pos); //5.头删 bool Del_head(struct Node* head); //6.尾删 bool Del_tail(struct Node* tail); //7.按位置删 bool Del_pos(struct Node* head,int pos); //8.按值删删除值val第一次出现的地方 bool Del_val(struct Node* head, Elem_Type val); //8.5.按值删删除值val所有出现的地方 bool Del_val_all(struct Node* head, Elem_Type val); //9.查找查找值val第一次出现的地方 struct Node* Search(struct Node* head, Elem_Type val); //10.清空 void Clear(struct Node* head); //11.销毁1(需要辅助结点参与) void Destroy1(struct Node* head); //12.销毁2 void Destroy2(struct Node* head); //13.判空 bool Is_Empty(struct Node* head); //14.获取有效长度 int Get_Length(struct Node* head); //15.打印 void Show(struct Node* head);结构非常简单data存放数据next存下一个节点的地址三、完整代码实现逐行精讲1. 初始化最重要//1.初始化 void Init_List(struct Node* head) { //数据域浪费掉 assert(NULL ! head); if (NULL head) { exit(EXIT_FAILURE); } head-next nullptr; }2. 头插法O (1)最快的插入方式永远插在头结点后面//2.头插 bool Insert_head(struct Node* head, Elem_Type val) { //0.assert //1.购买新节点 Node* pnewnode (Node*)malloc(sizeof(Node)); if (NULL pnewnode) { exit(1); } pnewnode-data val;//将val值赋过来 pnewnode-next NULL; //2.找到合适的插入位置头插位置特殊 //这里不需要找 直接需要head即可 //3.插入两行代码有两个指针域要修改 pnewnode-next head-next; head-next pnewnode; return true; }3. 尾插法O (n)//3.尾插 bool Insert_tail(struct Node* head, Elem_Type val) { //0.assert //1.购买新节点pnewnode //2.找到合适的位置让指针p指向当前最后一个有效节点 Node * pnewnode (Node*)malloc(sizeof(Node)); if (NULL pnewnode)//理解方式1. 我们反复去判断指针p指向的当前节点的肚子里面的next成员看是否是NULL { //理解方式2. 我们反复去判断指针p指向的当前节点的下一个有效节点是否存在 exit(1); } pnewnode-data val;//将val值赋过来 pnewnode-next NULL; struct Node* p head; while (p-next ! NULL) { p p-next; } //3.插入两行代码有两个指针域要修改 pnewnode-next p-next; p-next pnewnode; return true; }4. 按位置插入O (n)//4.按位置插 bool Insert_pos(struct Node* head, Elem_Type val, int pos) { assert(NULL ! head); assert(pos 0 pos Get_Length(head)); //1.购买新节点 Node* pnewnode (Node*)malloc(sizeof(Node)); if (NULL pnewnode) { exit(1); } pnewnode-data val;//将val值赋过来 pnewnode-next NULL; //2 Node* p head; for (int i 0; i pos; i) p p-next; pnewnode-next p-next; p-next pnewnode; return true; }5. 头删O (1)//5.头删 bool Del_head(struct Node* head) { //0.assert assert(nullptr ! head); //0.5判断当前链表是否是空链表 if (Is_Empty(head)) return false; //1.跨越待删除节点修改辅助节点的指针域 Node* p head-next; head-next p-next; //2.释放 free(p); p NULL; return true; }6. 尾删O (n)//6.尾删 bool Del_tail(struct Node* head) { //0.assert assert(nullptr ! head); //0.5链表是否是空链表 if (Is_Empty(head)) return false; //1.先申请临时节点p让其指向待删除节点的前驱上家 Node* p head; while (p-next-next ! NULL) { p p-next; } //2.再申请临时节点q,让其指向待删除节点自身 Node* q p-next; //3.跨越指向 p-next q-next; //4.释放待删除节点 free(q); q NULL; return true; }7. 按位置删除O (n)//7.按位置删 bool Del_pos(struct Node* head, int pos) { //0.assert assert(nullptr ! head); assert(pos 0 pos Get_Length(head)); //0.5链表是否是空链表(这里功能其实已经被128行代替了) /*if (Is_Empty(head)) return false;*/ //1.先申请临时节点p让其指向待删除节点的前驱上家 Node* p head; for (int i 0; i pos; i) { p p-next; } //2.再申请临时节点q,让其指向待删除节点自身 Node* q p-next; //3.跨越指向 p-next q-next; //4.释放待删除节点 free(q); q NULL; return true; }8. 按值删除第一次出现//8.按值删删除值val第一次出现的地方 bool Del_val(struct Node* head, Elem_Type val) { //0.assert assert(nullptr ! head); //1.判断链表是否是空链表 if (Is_Empty(head)) return false; //2.调用Search函数查找当前值val是否存在用临时指针q接受 Node* q Search(head, val); if (q NULL) { return false; } //3.申请临时指针p让指针p停留指针q指向节点的上一个节点 Node* p head; while (p-next ! q) { p p-next; } p-next q-next; free(q); q NULL; return true; }8.5 按值删除全部出现面试高频一次遍历删除所有相同值//8.5.按值删删除值val所有出现的地方 bool Del_val_all(struct Node* head, Elem_Type val) { assert(head ! NULL); if (Is_Empty(head)) { return false; } bool flag false; Node* p head; while (p-next ! NULL) { if (p-next-data val) { Node* q p-next; p-next q-next; free(q); q NULL; flag true; } else p p-next; } return flag; }9. 查找节点//9.查找查找值val第一次出现的地方 struct Node* Search(struct Node* head, Elem_Type val) { for (Node* p head-next; p ! NULL; p p-next) { if (p-data val) { return p; } } return NULL; }10. 判空 获取长度//13.判空 bool Is_Empty(struct Node* head) { return head-nextNULL; } //14.获取有效值长度 int Get_Length(struct Node* head) { int count 0; for (Node* p head-next; p ! NULL; p p-next) { count; } return count; }11. 打印链表//15.打印 void Show(struct Node* head) { for (Node* p head-next; p ! NULL; pp-next) { printf(%d , p-data); } printf(\n); }12. 清空链表保留头结点销毁链表释放所有节点//10.清空 void Clear(struct Node* head) { Destroy1(head); } //11.销毁1(需要辅助结点参与) void Destroy1(struct Node* head) { //只要不是空链表则头删一次直到链表为空 /*while (!Is_Empty(head)) { Del_head(head); }*/ while (head-next ! NULL) { Node* q head-next; head-next q-next; free(q); q NULL; } } //12.销毁2 void Destroy2(struct Node* head) { //0.assert assert(head ! NULL); //1.申请指针p保存辅助节点的指针域 Node* p head-next; //2.申请指针q,先不给q赋值 Node* qNULL;//因为有可能是NULL所以不能现在直接把p-next给到q //3.反复通过p和q打配合去销毁后续节点 while (p ! NULL) { q p-next; free(p); p NULL; p q; } //4.节点全部销毁完毕别忘了把辅助节点的指针域置空 head-next NULL;//这一行代码可以帮助下一次启用的时候辅助节点不用初始化 }四、测试主函数可直接运行int main() { struct Node head; Init_List(head); Insert_head(head, 100); Insert_head(head, 200); Insert_head(head, 500); Insert_tail(head, 300); Insert_tail(head, 400); Insert_tail(head, 800); Insert_pos(head, 600, 2); Insert_pos(head, 200, 2); Insert_pos(head, 200, 5); Show(head); printf(length%d\n, Get_Length(head)); Del_head(head); Show(head); Del_tail(head); Show(head); Del_pos(head, 2); Show(head); Del_val(head, 300); Show(head); printf(length%d\n, Get_Length(head)); Del_val_all(head, 200); Show(head); printf(length%d\n, Get_Length(head)); /*Clear(head); Show(head);*/ /*Destroy1(head); Show(head);*/ Destroy2(head); Show(head); return 0; }五、复杂度总结操作时间复杂度头插 / 头删O(1)尾插 / 尾删O(n)按位置插 / 按位置删O(n)按值查找 / 按值删O(n)求长度 / 打印O(n)六、面试高频考点为什么带头结点更好统一空表和非空表逻辑头插、头删不用修改头指针。顺序表和链表区别顺序表连续、随机访问快、插入删除慢链表不连续、随机访问慢、插入删除快批量删除相同值最优写法一次遍历 O (n)本文Del_val_all就是标准最优解。链表为什么不能用二分查找不能随机访问只能顺序遍历。清空和销毁区别清空释放有效节点保留头结点销毁释放所有节点