04｜单链表：如何通过指针提升插入、删除数据的速度？
王健伟
你好，我是王健伟。
今天我继续说一说“单链表”。
上节课我们提到过，顺序表（线性表的顺序存储）的最大缺点是，在插入和删除操作可能会移动大量元素，去保证元素之间的内存不能有空隙，而这，会导致程序的执行效率变低。
那我们要如何弥补这个缺点呢？这就涉及到了我们今天的内容：采用线性表的链式存储来保存数据元素。
线性表的链式存储也非常基础和常用，它不需要使用连续的内存空间。从名字可以得知，所谓链式存储，是通过“链（指针）”建立元素之间的关系，保证元素之间像一条线一样按顺序排列。这样，在插入和删除元素的时候，就不需要为了保证内存空间的连续性，去进行数据元素的大量迁移，只需要修改指向元素的指针即可。
用链式存储实现的线性表叫做链表，链表比顺序表稍复杂一些。它可以具体分为单链表、双链表、循环链表、静态链表这四种。这节课，我们先讲解单链表。
单链表有哪些特点？
图 1 展示了顺序表与单链表保存数据元素的区别（左侧为顺序表，右侧为单链表）。
图1 顺序表与单链表存储数据的区别
你可以看到，左侧顺序表中存储的元素在内存中紧密相连。其中，每个存储数据元素的内存空间被称为一个节点。
而右侧单链表中存储的元素在内存中并不需要紧密相连。在单链表中，每个节点不但用于存放一个数据元素（数据域），还要额外存放一个用于指向后继节点的指针也称后继指针（指针域），最后一个节点的指针域指向 nullptr。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
单链表是一种基础的数据结构，通过指针建立元素之间的关系，实现数据的插入和删除操作，避免了顺序表中可能出现的大量元素移动。文章详细介绍了单链表的特点，包括节点的结构和带头结点和不带头结点的区别。通过类定义和初始化操作，展示了单链表的构造函数和初始化过程。在插入操作方面，文章详细介绍了在单链表中插入元素的实现代码，并分析了插入操作的时间复杂度。同时，提出了一种更高效的方法，即将新节点插入到已知节点之后，从而优化插入操作的时间复杂度。在删除操作方面，文章展示了在单链表中删除元素的实现代码，并提出了一种优化方法，实现快速高效的删除操作。此外，文章还介绍了单链表的其他常用操作，包括输出所有元素、获取单链表长度、判断单链表是否为空以及翻转单链表等。最后，文章通过详细的代码实现和时间复杂度分析，全面介绍了单链表的操作，为读者提供了深入理解和应用单链表的基础知识。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(3)
- 最新
- 精选
徐石头Go实现单链表 https://github.com/xushuhui/algorithm-and-data-structure/tree/master/datastructure/linkedlist/singlyLinkedList作者回复: 💪💪💪加油
2023-02-28归属地：湖南
阿阳orward_list 是 C++ 11 新添加的一类容器，其底层实现和 list 容器一样，采用的也是链表结构，只不过 forward_list 使用的是单链表，而 list 使用的是双向链表。 forward_list 容器底层使用单链表，也不是一无是处。比如，存储相同个数的同类型元素，单链表耗用的内存空间更少，空间利用率更高，并且对于实现某些操作单链表的执行效率也更高。 效率高是选用 forward_list 而弃用 list 容器最主要的原因，换句话说，只要是 list 容器和 forward_list 容器都能实现的操作，应优先选择 forward_list 容器。作者回复: 😂😂
2023-02-24归属地：江苏- 阿阳老师好，单链表中，好像缺少了“修改”元素的操作。老师能补充“修改”相关的逻辑和代码？
作者回复: 咱们实现了LocateElem来查找元素，找到这个元素之后直接对他的.data域赋值就可以了。学完这节后，修改这种操作是应该能够自己实现出来的，再试试吧😂😂
2023-02-20归属地：江苏2
收起评论