查看“︁线性表”︁的源代码

== 线性结构的特点 ==
* 线性结构中的元素具有严格的一对一关系，表现为一个前驱和一个后继。
* 通常存储为顺序表（数组）或链表。

== 顺序表中第 <math>i</math> 个数据元素存储位置的计算 ==
'''公式：'''
<math>\text{LOC}(a_i) = \text{LOC}(a_1) + (i - 1) \times L</math>

* <math>\text{LOC}(a_i)</math>：第 <math>i</math> 个数据元素的存储地址。
* <math>i</math>：数据元素在表中的位置。
* <math>L</math>：每个元素所占存储单元大小。

该公式体现了顺序存储结构中地址的连续性，计算时间复杂度为 <math>O(1)</math>。

== 顺序表的基本操作 ==
* 取值：根据位置直接通过公式计算地址，时间复杂度为 <math>O(1)</math>。
* 查找：按值查找时，需要逐个比较，时间复杂度为 <math>O(n)</math>。
* 插入与删除：为保持数据的连续性，需要移动元素，时间复杂度为 <math>O(n)</math>。

== 顺序存储结构的特点 ==
* 逻辑相邻即物理相邻：数据存储为一段连续的内存空间。
* 随机存取：通过公式快速计算元素地址，支持直接访问任意位置。
* 存储密度大：所有存储空间都存储有效数据，密度为 1。

== 链式存储结构的特点 ==
* 物理位置不一定相邻：数据元素之间通过指针链接，内存分配灵活。
* 顺序存取：必须从头节点开始，逐一访问每个元素。
* 存储密度小于 1：每个节点需要额外存储指针信息。
* 链表：单链表中每个节点包含数据域和指针域。

== 单链表的操作 ==
=== 单链表的插入操作 ===

在位置 p 之后插入新节点 s：

<syntaxhighlight lang="c">
s->next = p->next;

p->next = s;
</syntaxhighlight>

# 将 s 的指针指向 p 的后继。
# 将 p 的指针指向 s。

=== 单链表的删除操作 ===

删除位置 p 之后的节点 q：

<syntaxhighlight lang="c">
q = p->next;

p->next = q->next;
</syntaxhighlight>

# 将 q 定位为 p 的后继节点。
# 修改 p 的指针，使其跳过 q。

== 效率 ==

插入和删除只需修改指针，时间复杂度为 <math>O(1)</math>，不需要移动数据。

{{Template:数据结构与算法}}
{{Template:线性表}}