数据结构精讲链表从原理、全套手写代码到面试考点全覆盖前言链表是所有链式数据结构的基石也是面试、算法刷题、底层开发的必考核心。我们之前手写的线程池任务队列底层依托的就是单链表结构。可以说不懂链表就看不懂队列、栈、哈希表、树的链式实现。很多初学者学链表只会背概念写不出代码、看不懂指针变化、分不清和数组的区别。本文用通俗类比 完整可运行C代码 复杂度分析 高频面试题一次性吃透链表所有核心内容。一、链表是什么1.1 生活化类比数组一排固定长度的连体座位内存连续中间插一个人后面所有人都要挪位置。链表火车车厢结构每一节车厢节点只包含两个东西自己的乘客数据数据域下一节车厢的地址指针域车厢之间不连体、内存不连续任意位置增删车厢不需要移动其他车厢只需要改一下连接指针。1.2 官方定义链表是线性、链式存储的数据结构逻辑上连续物理内存不连续由若干个独立节点通过指针串联而成支持动态扩容无需提前开辟固定内存。1.3 节点核心结构任何链表节点万变不离其宗数据域存储业务数据指针域存储下一个节点地址C语言标准定义// 单链表节点结构typedefstructListNode{intval;// 数据域structListNode*next;// 指针域指向下一个节点}ListNode;二、链表 VS 数组新手最大误区不知道什么时候用数组、什么时候用链表。特性数组顺序表链表链式表内存布局连续内存分散内存靠指针连接容量固定/预分配容易浪费或溢出动态增减按需申请释放随机访问支持下标访问 O(1)不支持只能遍历 O(n)头部/中间插入删除慢 O(n)需要批量平移数据快 O(1)仅修改指针尾部插入快 O(1)需遍历尾节点 O(n)无尾指针内存开销无额外开销每个节点多一个指针有微小开销选型口诀频繁查询、少改动 → 用数组频繁增删、动态数据、不确定容量 → 用链表三、链表四大分类工程和算法中所有链表只有这4种组合单向链表只能从头往后遍历线程池任务队列底层双向链表可前后遍历STL list、LRU缓存底层循环链表尾节点指向头节点环形任务调度带头结点链表固定一个空头节点统一空表/非空表操作工程最常用本文重点带头单向链表教学、工程、面试最通用结构四、单链表全套手写代码初始化/增删改查/销毁核心优势带头结点链表彻底规避空指针特殊判断所有操作逻辑统一工业级首选。完整可编译源码// 定义单链表节点typedefstructListNode{intval;structListNode*next;}ListNode;// 1. 初始化创建空头结点ListNode*InitList(){// 申请头节点内存ListNode*head(ListNode*)malloc(sizeof(ListNode));head-nextNULL;returnhead;}// 2. 尾部插入节点voidTailInsert(ListNode*head,intval){ListNode*curhead;// 遍历找到尾节点while(cur-next!NULL){curcur-next;}// 创建新节点ListNode*newNode(ListNode*)malloc(sizeof(ListNode));newNode-valval;newNode-nextNULL;// 尾部链接cur-nextnewNode;}// 3. 头部插入节点最快速voidHeadInsert(ListNode*head,intval){ListNode*newNode(ListNode*)malloc(sizeof(ListNode));newNode-valval;// 新节点指向原第一个节点newNode-nexthead-next;// 头节点指向新节点head-nextnewNode;}// 4. 按位置插入在第pos个节点后插入voidPosInsert(ListNode*head,intpos,intval){ListNode*curhead;// 找到pos位置前驱节点for(intipos;i){if(curNULL)return;// 位置非法curcur-next;}ListNode*newNode(ListNode*)malloc(sizeof(ListNode));newNode-valval;newNode-nextcur-next;cur-nextnewNode;}// 5. 按值删除节点voidDelByVal(ListNode*head,intval){ListNode*curhead;// 找到待删除节点的前驱while(cur-next!NULLcur-next-val!val){curcur-next;}// 没找到目标值if(cur-nextNULL)return;// 缓存待删除节点ListNode*delcur-next;// 跳过待删除节点cur-nextdel-next;// 释放内存防止泄漏free(del);}// 6. 查找元素是否存在intFindVal(ListNode*head,intval){ListNode*curhead-next;intpos0;while(cur!NULL){if(cur-valval)returnpos;// 返回下标位置curcur-next;pos;}return-1;// 未找到}// 7. 遍历打印链表voidPrintList(ListNode*head){ListNode*curhead-next;while(cur!NULL){printf(%d ,cur-val);curcur-next;}printf(\n);}// 8. 销毁整个链表防止内存泄漏voidDestroyList(ListNode*head){ListNode*curhead;while(cur!NULL){ListNode*tmpcur;curcur-next;free(tmp);}}// 测试主函数intmain(){// 初始化链表ListNode*headInitList();// 尾部插入TailInsert(head,10);TailInsert(head,20);TailInsert(head,30);printf(尾插后);PrintList(head);// 头部插入HeadInsert(head,5);printf(头插后);PrintList(head);// 指定位置插入PosInsert(head,2,15);printf(指定位置插入后);PrintList(head);// 删除元素DelByVal(head,20);printf(删除20后);PrintList(head);// 查找元素intretFindVal(head,15);if(ret!-1)printf(元素15下标%d\n,ret);elseprintf(未找到\n);// 销毁链表DestroyList(head);return0;}输出结果尾插后10 20 30 头插后5 10 20 30 指定位置插入后5 10 15 20 30 删除20后5 10 15 30 元素15下标2五、链表核心操作复杂度以单链表为准尾插/查找/遍历O(n) 需要逐个遍历节点头插O(1) 仅修改头节点指针中间/指定位置插入删除O(n) 耗时全部在「查找位置」修改指针仅O(1)随机访问O(n) 不支持下标必须遍历核心结论链表改指针极快、找位置很慢。六、带头结点 vs 不带头结点不带头结点空表时 headNULL插入、删除、判空需要大量特殊if判断代码冗余、容易空指针崩溃带头结点推荐永远有一个固定空头节点head永远不为NULL空表、单节点、多节点操作逻辑完全一致线程池任务队列、开源框架、工业级代码全部采用此写法七、链表高频面试工程考点考点1为什么线程池任务队列用链表任务数量不确定链表动态扩容不浪费内存频繁尾部新增任务、头部取出任务链表头尾操作适配任务生产消费模型无需预设队列大小天然支持无界队列。考点2链表常见算法基础所有链表算法题均基于本文结构1.移除链表元素2. 合并两个有序链表有无傀儡节点3. 返回倒数第k个节点4. 删除链表的倒数第N个节点5. 反转链表6.分割链表7.链表的中间节点8.相交链表9.回文链表10.环形链表11.环形链表212.旋转链表13.随机链表的复制考点3链表最大坑内存泄漏新增节点malloc必须手动free销毁断链问题修改指针顺序错误导致链表断裂、数据丢失空指针访问不带头结点极易触发崩溃。八、全文总结链表是非连续、动态、指针串联的线性结构对标数组牺牲随机访问换取高效增删节点 数据域 指针域带头单链表是学习和工程的最优入门结构核心优势动态扩容、任意位置增删仅改指针、无数据平移核心短板不支持随机访问查找必须遍历链表是队列、线程池、哈希表、高阶算法的底层基础吃透链表搞定一半数据结构。
 ；YGGFMRRV‑OH)
