线性表的顺序存储和链式存储 · 融合风（象牙 + Obsidian 入口）

速查

线性表是最基本的线性结构，有两种存储实现：顺序表随机访问 O(1)、存储密度为 1，但增删需移动元素（平均 O(n)）；链表通过指针链接、增删灵活（已知前驱 O(1)），但只能顺序访问 O(n)。

核心概念 ▾

线性表是最基本、最简单的数据结构，包含顺序存储和链式存储两种实现方式。

顺序表：用一段地址连续的存储单元依次存储线性表的数据元素。逻辑上相邻的元素在物理位置上也相邻，支持随机访问，时间复杂度 O(1)。

链表：用一组任意的存储单元存储线性表的数据元素，通过指针链接各结点。逻辑上相邻的元素在物理位置上不一定相邻，只能顺序访问，时间复杂度 O(n)。

图：顺序表地址连续、支持随机访问；链表用指针把分散的结点串起来、只能顺序访问。

链表的常见变体：

头指针 vs 头结点头指针必有（没有头指针找不到链表）；头结点可有可无，带头结点可统一空表与非空表的插入/删除操作。

考点	说明
顺序表与链表的对比	从存取方式、空间利用、插入删除效率等维度比较
链表的插入删除操作	头插法、尾插法、指定位置插入、删除等指针操作
双链表操作	插入/删除需修改四个指针域，常考操作序列
顺序表的插入删除	平均移动元素次数：插入 $n/2$，删除 $(n-1)/2$
头结点的作用	统一空表和非空表的操作，避免判断头指针是否为空
判空条件	顺序表：$length==0$；带头结点单链表：$L\text{->next==NULL}$

最常考顺序表增删的平均移动元素次数是高频计算题：插入平均移动 $n/2$ 个、删除平均移动 $(n-1)/2$ 个元素，均为 O(n)。

易错清单

选型口诀表长可预估、查询多 → 顺序表；表长难预估、增删频繁 → 链表。

顺序表和链表的存取方式区别？

顺序表随机访问 O(1)，链表只能顺序访问 O(n)。

顺序表插入/删除的时间复杂度？

平均移动 $n/2$（插入）、$(n-1)/2$（删除），均为 O(n)。

带头结点的好处？

统一空表和非空表的处理，头插法 O(1)。

顺序表与链表的存储密度？

顺序表为 1（全存数据），链表 < 1（含指针域）。

带头结点的单链表：head → A → B → C。选择操作查看指针如何修改

点击上方按钮开始

橙色流动虚线表示本次操作新建立/激活的指针路径；灰化的结点表示已脱离链表。插入操作必须先接新结点、再改前驱指针。