数据结构 —— 链表

在数据结构体系中顺序表与链表是两大最基础的线性存储结构。顺序表依靠连续内存实现随机访问但插入、删除中间元素效率低下而链表用离散内存 指针连接的方式完美解决了顺序表的痛点是 Linux 内核、操作系统、网络编程中高频使用的数据结构。本文从零拆解链表的底层原理、分类、完整实现、核心优缺点、与顺序表的对比同时结合 Linux 内核使用场景彻底吃透面试高频考点。一、先搞懂什么是链表1.1 链表的核心定义链表是非连续、非顺序的线性表它不要求内存连续通过 ** 指针引用** 将分散在堆内存中的一个个节点串联起来。每个节点包含两部分数据域存储业务数据指针域存储下一个节点的内存地址节点分散在内存各处不连续排列靠指针维系前后关系没有下标不支持随机访问只能从头节点开始逐个遍历你可以把链表想象成一串带钩子的珠子每个珠子存数据同时带一个钩子勾住下一颗珠子珠子不用挨在一起靠钩子串联想要找到第 N 颗珠子必须从第一颗顺着钩子依次找。1.2 链表的四大分类日常开发 面试中链表分为 4 种层层递进单链表最基础只有后继指针只能从头往后遍历双向链表有前驱 后继两个指针可双向遍历Linux 内核高频使用循环链表尾节点指针指向头节点首尾相连双向循环链表双向 循环功能最全内核 list_head 底层就是它1.3 链表与顺序表的核心对立点顺序表连续内存、随机访问快、中间增删慢、缓存友好链表离散内存、随机访问慢、任意位置增删快、缓存不友好二、单链表底层原理与完整实现单链表是链表的基础我们用 C 手写一个极简单链表彻底搞懂底层逻辑。2.1 节点结构定义// 链表节点 template typename T struct ListNode { T val; // 数据域存储数据 ListNode* next; // 指针域存下一个节点地址 ListNode(T v) : val(v), next(nullptr) {} };val存放业务数据next指向下一个节点末尾节点 next 为nullptr2.2 单链表核心操作1. 头插O (1)在头部插入节点只需要修改指针是链表效率最高的插入方式。void push_front(T val) { ListNodeT* new_node new ListNodeT(val); new_node-next head; // 新节点指向原头节点 head new_node; // 头指针更新为新节点 }2. 尾插O (n)需要遍历到链表尾部才能插入节点。void push_back(T val) { ListNodeT* new_node new ListNodeT(val); if(head nullptr) { head new_node; return; } // 遍历到尾节点 ListNodeT* cur head; while(cur-next ! nullptr) cur cur-next; cur-next new_node; }3. 指定位置插入O (n)找到前驱节点修改指针指向不需要移动任何元素。void insert(int pos, T val) { // 找到pos前一个节点 ListNodeT* cur head; for(int i0; ipos-1; i) cur cur-next; ListNodeT* new_node new ListNodeT(val); new_node-next cur-next; cur-next new_node; }4. 删除节点O (n)找到前驱节点跳过目标节点释放内存即可无需移动元素。void erase(int pos) { ListNodeT* cur head; for(int i0; ipos-1; i) cur cur-next; ListNodeT* del cur-next; cur-next cur-next-next; delete del; // 释放堆内存避免内存泄漏 }5. 遍历查找O (n)链表没有下标必须从头节点逐个往后遍历无法直接跳转。2.3 单链表致命缺点只能单向遍历无法反向查找尾插 / 尾删效率极低需要遍历整个链表删除当前节点必须找到它的前驱节点操作繁琐三、双向链表Linux 内核最爱3.1 底层原理双向链表在单链表基础上给每个节点增加前驱指针 prevtemplate typename T struct DListNode { T val; DListNode* prev; // 前驱指针指向前一个节点 DListNode* next; // 后继指针指向后一个节点 };每个节点可找到前驱、后继支持双向遍历尾插、尾删、删除当前节点效率直接提升到 O (1)Linux 内核、epoll 就绪队列、进程调度队列全部使用双向链表3.2 核心优势可正向、反向双向遍历已知当前节点可直接删除无需遍历找前驱头插、尾插、头删、尾删全部 O (1)3.3 缺点每个节点多存一个指针内存开销比单链表大四、循环链表 双向循环链表4.1 循环链表尾节点的next指针不再置空而是指向头节点首尾相连。优势从任意节点都可遍历整个链表适合环形场景环形队列缺点遍历结束条件从nextnullptr变为nexthead容易死循环4.2 双向循环链表Linux 内核 list_head双向 循环功能最全、使用最广。内核中实现不存储数据只存两个指针嵌入任意结构体中通用型极强epoll 的就绪队列、进程 task_struct 调度队列、定时器队列全部基于此实现五、链表核心优缺点面试必背优点增删效率极高任意位置插入 / 删除节点只需要修改指针无需移动大量元素O (1) 时间复杂度已知节点内存利用率高按需分配节点没有顺序表的预留冗余内存无内存浪费内存离散存储不需要连续的大块内存碎片化内存也能使用适配海量动态连接场景缺点不支持随机访问只能顺序遍历查找元素 O (n)速度远慢于顺序表缓存命中率低节点内存离散CPU 缓存无法预加载顺序遍历也比顺序表慢额外内存开销每个节点需要存储指针内存占用比顺序表高容易内存泄漏节点手动 new 创建忘记 delete 会造成内存泄漏六、顺序表 vs 链表终极对比面试必背表格特性顺序表链表内存分布连续内存离散内存随机访问支持O (1)不支持O (n)头部 / 中间增删O (n)需移动元素O (1)仅修改指针尾部增删O (1)均摊双向链表 O (1)单链表 O (n)CPU 缓存缓存友好速度快缓存不友好速度慢内存开销低无指针冗余高每个节点带指针适用场景查找多、增删少增删多、查找少场景选择口诀频繁查询、极少增删 → 选顺序表vector频繁插入删除、动态扩容 → 选链表Linux 内核、高并发队列 → 选双向循环链表七、链表在 Linux 网络编程中的实际应用链表不是纸上谈兵在你学习的 IO 复用、高并发服务器中无处不在epoll 就绪队列epoll 内核中用双向链表存储就绪的 fd 事件epoll_wait 直接取链表头部O (1) 获取就绪事件进程 / 线程管理Linux 内核用双向链表串联所有进程、线程调度时快速增删节点定时器管理网络服务的定时器心跳、超时检测用链表管理超时事件日志系统日志缓冲区、异步队列常用链表实现动态节点增删八、高频面试总结单链表单向遍历头插 O (1)尾插 O (n)实现简单功能有限双向链表双向遍历头尾操作 O (1)Linux 内核主流使用循环链表首尾相连适合环形结构双向循环链表功能最全epoll、内核调度核心数据结构核心区别顺序表胜在查询链表胜在增删顺序表缓存友好链表动态灵活