线性表
- 最基本、最简单、最常用的一种数据结构
- 线性表中的元素，除了第一个和最后一个以外，其它数据元素都是首尾连接的（注：循环链表逻辑层次上也是一种线性表，存储结构上属于链式存储，但是最后一个元素的尾指针指向了首结点）
线性表的特征
- 集合中必存在唯一的“第一元素”
- 集合中必存在唯一的“最后元素”
- 除最后一个元素外，其它元素都有后继
- 除第一个元素外，其它元素都有前驱
线性表-单链表结点
image.png
线性表-单链表逻辑状态
image.png
线性表-有头结点的单链表逻辑状态
image.png
线性表-单链表为什么要增加头结点
- 为了便于首元结点的处理
- 为了便于空表和非空表的统一处理
线性表-单链表的插入
假设要在单链表数据元素a和b中插入一个元素c，已知p为其单链表存储结构中指向结点a的指针：
1.先通过p找到元素a和a的后继
2.元素c的后继指向a的后继
3.a的后继指向c
image.png
线性表-单链表的删除
假设在单链表数据元素a、b和c删除元素b，已知p为其单链表存储结构中指向结点a的指针：
1.临时变量q为指向要删除的结点：a->next(就是b)
2.将a的后继改成c
3.释放b
image.png
线性表-单链表的前插法
插入元素p的时候，始终把该元素插入到首元结点位置
- 1.创建带有头结点的单链表
- 2.生成新的结点并赋值数据
- 3.修改头结点next的指针
- 4.将结点p插入到头结点之后
线性表-单链表的后插法
插入元素p的时候，始终把该元素插入到链表末尾
*1.创建带有头结点的单链表
*2.生产新的结点p并赋值数据
*3.将表链表尾结点的指针指向P
*4.将尾结点next指针指向null
