链式结构
| 链式结构 | |
|---|---|
| 术语名称 | 链式结构 |
| 英语名称 | linked data structure |
| 别名 | 链接存储结构 |
| 结点 | |
|---|---|
| 术语名称 | 结点 |
| 英语名称 | node |
| 别名 | 节点 |
| 元素 | |
|---|---|
| 术语名称 | 元素 |
| 英语名称 | element |
| 链接 | |
|---|---|
| 术语名称 | 链接 |
| 英语名称 | link |
| 别名 | connector, 引用, reference, 指针, pointer |
| 空 | |
|---|---|
| 术语名称 | 空 |
| 英语名称 | empty |
| 空链接 | |
|---|---|
| 术语名称 | 空链接 |
| 英语名称 | null link |
| 别名 | 空, null |
| 解引用 | |
|---|---|
| 术语名称 | 解引用 |
| 英语名称 | dereference |
| 别名 | 间接寻址, 间址 |
链式存储结构/链接存储结构(linked data structure)是一类最基础的存储结构。有时也用代表数据结构链表代指，但是链式结构范围比链表范围宽很多。有时仅链式存储结构的数据结构也被会称为某某链表。
链式存储结构容纳一系列的结点，每个结点中有若干数据记录。除外，每个结点中还会含有至少一个链接，且指向另一个结点或空，在不同的语言中可能使用引用或指针等引用类型表达。
链式存储结构中，寻址需要通过某个已知结点开始逐个寻找其指向的结点，因此有时被称为链式寻址或链表寻址。
定义
存储结构
链式存储结构/链接存储结构(linked data structure)是一种存储结构。链式结构包括多个结点(node)，其内存空间关系不做要求；结点中含有数据记录，称为元素(element)。结点中除元素外，还有称为链接(link/connector)的数据，链接可以引用(refer to/reference)/指向(point to)结点自身或另一个结点。
链接存储结构中的链接是一个抽象类型，其可以指向某个结点，通常只要求其是一个可空、等值可比较的引用类型：
- 判断空值(emptiness)：是可空类型的同名操作。一个链接的数据，可以指向某个结点，也可以不指向任何结点（注：指向不是结点的数据不符合要求，不属于合理状态），分别称这个链接是非空的(non-empty)和空的(empty)。一个空的链接(empty link)也可以称为一个空链接(null link)并简称为空(null[1])[2]，记作
NULL或^。 - 判断两个链接是否相等(equality)：两个链接的数据指向同一个结点，或者同时为空，称两个链接相等(equal)，否则称为不相等。通常用等号或不等号表达。
- 解引用/间址(deference)：是引用类型的同名操作。若链接非空，可以通过这一操作得到其指向的结点。
寻址方式
链式寻址/链接寻址/链表寻址中，数据结构由结点构成，结点间以链接相连接。若已知结点 [math]\displaystyle{ b }[/math] ，函数 [math]\displaystyle{ f(\cdot) }[/math] 给出从某结点确定下一结点的链接，函数 [math]\displaystyle{ d(\cdot) }[/math] 代表对链接解引用，则对任意元素 [math]\displaystyle{ e }[/math] ，其所在结点 [math]\displaystyle{ n_e }[/math] 与任意结点 [math]\displaystyle{ n }[/math] 间的函数关系 [math]\displaystyle{ n_e(n) }[/math] 满足递归关系：
[math]\displaystyle{ n_e(n) = \begin{cases} n &, n = n_e \\ n_e(d(f(n))) &, n \neq n_e \\ \end{cases} }[/math]
且展开有 [math]\displaystyle{ n_e = d(f(d(f(\cdots d(f( n )) \cdots )))) }[/math] 。
由于在寻找 [math]\displaystyle{ n_e }[/math] 时是不知道 [math]\displaystyle{ n_e }[/math] ，无法比较 [math]\displaystyle{ n_e = n }[/math] 的，通常用其他条件结束递归，如位置计数或者元素的某种特征。