【数据结构】21_线性表的链式存储结构
文章目录
顺序存储结构线性表的最大问题
插入和删除需要移动大量的元素!
链式存储的定义
- 为了表示每个元素与其直接后继元素之间的逻辑关系;数据元素除了存储本身的信息外,还要存储其直接后继的信息。

ai 和 ai+1 是线性表中的两个相邻数据元素;在物理内存中无相邻关系。
联系存储逻辑结构
基于链式存储结构的线性表中,每个结点都包含数据域和指针域
- 数据域:存储数据元素本身
- 指针域:存储相邻结点的地址

专业术语的统一
顺序表
- 基于顺序存储结构的线性表
链表
基于链式存储结构的线性表
- 单链表:每个结点只包含直接后继的地址信息
- 循环链表:单链表中的最后一个结点的直接后继为第一个结点
- 双线链表:单链表中的结点包含直接前驱和后继的地址信息
不同类型的链表
单链表

循环链表

双线链表

链表头中的基本概念
头结点
- 链表中的辅助结点,包含指向第一个数据元素的指针
数据结点
- 链表中代表数据元素的结点,表现形式为:[数据元素 | 地址]
尾结点
- 链表中的最后一个数据结点,包含的地址信息为空
单链表中的结点定义

单链表的内部结构

头结点在单链表的意义:
辅助数据元素的定位,方便插入和删除操作;因此,头结点不存储实际的数据元素。
在目标位置插入数据元素
- 从头结点开始,通过 current 指针定位到目标位置
- 从堆空间申请新的 Node 结点
- 执行操作:
node->value = e;
node->next = current->next;
current->next = node;


在目标位置删除数据元素
- 从头结点开始,通过 current 指针定位到目标位置
- 使用 toDel 指针指向需要删除的结点
- 执行操作:
toDel = current->next;
current->next = toDel->next;
delete toDel;

小结
- 链表中的数据元素在物理内存中无相邻关系
- 链表中的结点都包含数据域和指针域
- 头结点用于辅助数据元素的定位,方便插入和删除操作
- 插入和删除操作需要保证链表的完成性
以上内容整理于狄泰软件学院系列课程,请大家保护原创!
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论