查看“︁单向链表”︁的源代码

[[分类:线性表]]
[[分类:链式存储结构]]
{{InfoBox
|name=单向链表
|eng_name=singly linked list
|aliases=单链表
}}
{{#seo:
|keywords=单向链表,单链表
|description=介绍了单向链表，即逻辑结构为线性表、存储结构为链式、结点拥有指向下一结点链接的数据结构，即结点拥有指向下一结点链接的链表。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-7-18
}}
'''单向链表'''('''singly linked list''')或'''单链表'''指逻辑结构为[[线性表]]、存储结构为[[链式存储结构]]（即属于[[链表]]），且结点间只存在指向下个结点的链接（尾结点除外）的数据结构。

在[[编程语言]]中，通常不直接提供链表结构。在内存中，链表分配和访问内存的方式不符合[[访问局部性原理]]，对[[缓存]]不友好，执行效率会按照缓存与内存的访问时间比例成数量级地放大。因此真正需要链表时往往通过[[内存池]]方案预分配结点块，或者结合[[自由链表]]的形式复用存储上局部化的结点，减少内存碎片。如果数据量较小，也通常会使用[[动态数组]]代替；在动态数组中间插入时间复杂度在数据量较大时会较高，必须要插入中间段时，会使用[[块状链表]]作为代替。

在外存中，文件间通过文件名的链表连接则是比较常见的做法。

尽管单向链表不适合直接用于内存分配，但是经常以逻辑上的形式存在。一个例子是管理内存常用的自由链表，固定内存段被划分为结点，结点间互相连接成链表，以数组的内存限制为代价保证访问的局部性，并同时用链式结构难以[[随机访问]]为代价换取插入删除的灵活性。

== 结构 ==

单向链表中的每个结点可以抽象成如图所示结构。

{{GiteaSvg|singly_linked_node}}

其中含有数据域和指向下个结点的链接。链接成一个链表时如下图所示。

{{GiteaSvg|singly_linked_list}}

这个结构只需要获取第一个结点，就可以顺藤摸瓜地找到整个结构。
如果只保存一个能取得第一个结点的数据，保存这个数据的变量通常称为 <code>head</code> ，因此称为'''头指针'''('''head pointer''', '''head reference''')。

修改操作中，总是需要修改上一个结点的链接，从而插入或删除的结点，因此会存在需要修改一个实际链接还是需要修改头指针本身的问题，这也使得传递头指针时不得不加入一层指针以保证间址取得最新值，使用一个虚拟结点可以统一对第一个结点的操作。
所以有时也保存一个虚拟结点，称为'''头结点'''('''head node''')/'''哨兵结点'''('''sentinel node''')。头结点中的链接就相当于上一个方法中的头指针。

== 语言实例 ==

{{数据结构实例
|c=人工实现
|cpp=[https://en.cppreference.com/w/cpp/container/forward_list <syntaxhighlight inline lang="cpp">std::forward_list</syntaxhighlight>]
|cpp_ex=STL
|cpp_ver=C++11
}}

== 实现实例 ==

{{Libcxx|libcxx/include/forward_list|https://github.com/llvm/llvm-project/blob/9a3e66e314e698ffb08dba151bc098b6b8867c61/libcxx/include/forward_list#L640}}

{{Libstdc++|libstdc++-v3/include/std/forward_list|https://github.com/gcc-mirror/gcc/blob/7eecc08ccf75679e6ae688d92e50afae935547ab/libstdc%2B%2B-v3/include/bits/forward_list.h#L433}}

== GSSDS 定义 ==

{{Gitea|array/include/sds/linked_list/linked_list.h}}

== 复杂度估计 ==

=== 空间复杂度 ===

单向链表整体空间复杂度为[[线性复杂度]]，每个结点保存一个数据，使得结点数量与数据量成正比。但是由于结点中需要额外保存链接，比起直接保存有额外常数，考虑每段数据的大小和链接大小的关系，为 <math>\sim \frac{d+p}{d} n=O(n)</math> 。

=== 时间复杂度估计与优化 ===

本节讨论单向链表对其逻辑结构线性表的操作实现。

==== 插入删除操作 ====

在链表两端的插入算法通常称为[[头插法]]和[[尾插法]]。这两个词一般指构造时的算法，但也常用在向已有链表插入结点的场景。

插入删除时，涉及是否允许从尾部插入删除、是否保存并维护尾部指针，也存在一些优化差异。
若需要进行尾插法，实现上可以保存尾指针，在尾插法中不需要提前找到尾部，直接操作尾部（但尾插法作为构造链表过程时是自动获得尾部的，不涉及这个问题），
但是在删除尾结点时，需要将尾指针移动到上一个结点，这就不得不从头进行遍历寻找；
相反，若实现不保存尾指针，则尾部插入删除都需要额外遍历。

==== 时间复杂度总结 ====

记链表长度为 <math>n</math> 。

{| class='wikitable' style='width:100%'
! colspan=2 | 操作
! 最好
! 最坏
! 平均
|-
! rowspan=3 | 基本操作
! 初始化 <code>Create</code>
| colspan=3 | 不初始化结点为一次分配
|-
! 长度 <code>Length/Size</code>
| colspan=3 | <math>O(n)</math> ，如果没维护则需要遍历
|-
! 清空
| colspan=3 | <math>O(n)</math> ，逐个结点销毁
|-
! rowspan=4 | 元素获取
! 指定索引 <code>Get(i)</code>
| <math>\Theta(1)</math> ，起始位置
| <math>\Theta(n)</math> ，结束位置
| <math>\sim i\sim \tfrac{n}{2}=O(n)</math> ，需要遍历到指定位置
|-
! 指定位置 <code>Get(p)</code>
| colspan=3 | <math>\Theta(1)</math>
|-
! 头部 <code>Head</code>
| colspan=3 | <math>\Theta(1)</math>
|-
! 尾部 <code>Rear</code>
| colspan=3 | <math>\Theta(1)</math> ，若保存尾指针；<math>\Theta(n)</math> ，若需要遍历到尾部
|-
! rowspan=4 | 插入删除
! 指定索引 <code>Insert(i,x)/Remove(i)</code>
| <math>\Theta(1)</math> ，头部
| <math>\Theta(n)</math> ，尾部
| <math>\sim i\sim \tfrac{n}{2}=\Theta(n)</math> ，平均遍历长度
|-
! 指定位置 <code>InsertAfter(p,x)/RemoveAfter(p)</code> *
| colspan=3 | <math>\Theta(1)</math> ，只需要插入删除结点后连接指针
|-
! 头部
| colspan=3 | <math>\Theta(1)</math>
|-
! 尾部
| colspan=3 | <math>\Theta(1)</math> ，保存尾指针且插入尾部； <math>\Theta(n)</math> ，否则插入删除尾部均需要遍历找到前一结点
|-
! rowspan=2 | 元素顺序
! 指定位置前趋 <code>Pred</code>
| <math>\Theta(1)</math> ，头部
| <math>\Theta(n)</math> ，尾部
| <math>\sim i\sim \tfrac{n}{2}=\Theta(n)</math> ，平均遍历长度
|-
! 指定位置后继 <code>Succ</code>
| colspan=3 | <math>\Theta(1)</math> ，只需要随着链接找到
|}

* 由于单向链表中直接操作一个结点往往需要修改前后结点的指针，一般指定其前一结点的位置而不是本结点，根据链表连接关系得到本结点和下一结点，所以和线性表词条中的定义不同。如果只给定当前结点地址，则无论插入还是删除都需要遍历出其前一个结点，变成线性复杂度。


{{数据结构}}