数据结构 单链表(1)

1.概念和结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中

的指针链接次序实现的。

通过指针链接次序实现的要怎么理解呢?

这是一张链表的结构图:

与顺序表不同的是，链表里的每节“车厢” (仔细观察这张结构图会发现它和火车很像，并且可以看

出由4个车厢组成) 都是独立申请下来的空间，我们称之为“结点/节点”

结点的组成主要有两个部分：当前结点要保存的数据和保存下一个结点的地址（指针变量）。

图中指针变量plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点, 也称为链表的的

头结点 。

我们可以把链表比喻成 火车，这样会非常直观：

1. 「火车车厢」=「链表结点」

每节火车车厢就是链表的一个结点：

- 车厢里装的「乘客、货物」→ 对应结点储存的数据（存实际内容，比如数字、字符串）。

- 车厢之间的「挂钩」→ 对应结点的指针（存下一个结点的地址，把车厢串起来）。

最后一节车厢的挂钩「没有连接下一节」→ 对应链表最后一个结点的指针域为 NULL（空），表

示链表结束。

2. 「火车头」=「链表头指针」

火车头（车头本身也算一节特殊车厢）→ 对应链表的头指针（或头结点）：

- 头指针存的是「第一节车厢的地址」→ 你通过头指针，才能找到整列火车（遍历链表）。

- 如果火车头丢了（头指针丢了），就找不到整列火车了 → 链表头指针是访问链表的唯一入口。

简单总结：

链表 = 火车，节点 = 车厢，指针 = 挂钩，头指针 = 火车头。

这种比喻能帮你记住：链表靠「指针（挂钩）」把「节点（车厢）」串起来，增删节点只改指针

（挂钩），不需要移动其他节点（车厢），这也是链表最核心的特点～

2.链表和顺序表的关系:

链表和顺序表都属于线性表，是数据在逻辑结构上呈现线性关系的两种不同存储方式实现的结构，

用于存储和管理数据，二者关系可从以下方面理解：

一、相同点:

- 逻辑结构：都用于存储具有线性逻辑关系的数据，即数据元素在逻辑上是“一对一”的相邻关系，

比如存储一列学生的成绩，都能体现成绩的先后顺序 。

- 基本操作：都支持常见的数据操作，像添加（插入）、删除、查找、遍历等操作，只是实现方式

和效率有差异。

二、不同点:

可以从 存储、访问、增删、空间、适用场景 这 5 点简单概括：

存储:

顺序表 : 内存连续，元素“挤在一起”

单链表 : 内存不连续，靠指针“串”起节点 

访问:

顺序表 : 下标直接访问（如  arr[2] ），很快

单链表 :  必须从头遍历找，慢（像数火车车厢）

增删:

顺序表 : 中间增删要移动大量元素，慢

单链表 : 改指针就能增删（像火车改挂钩），快 

空间:

顺序表 : 预分配空间，满了扩容麻烦（需拷贝数据）

单链表 : 用多少申请多少，灵活但有指针开销

适用场景:

顺序表 : 频繁查、数据少且稳定（如查成绩）

单链表 : 频繁增删、数据动态变化（如历史记录）

简单说，顺序表像“排队的一长串盒子”，空间连续好快速找；链表像“串起的珠子”，节点分散但增

删灵活，实际开发选哪种，得看数据操作特点和性能需求。

关于单链表的概念基础知识就这么些。下一篇小编为大家带来关于单链表的实现。也是非常复杂的

一部分内容。感谢大家的观看!