线性表

• 最基本、最简单、最常用的一种数据结构
• 线性表中的元素，除了第一个和最后一个以外，其它数据元素都是首尾连接的（注：循环链表逻辑层次上也是一种线性表，存储结构上属于链式存储，但是最后一个元素的尾指针指向了首结点）

线性表的特征

• 集合中必存在唯一的“第一元素”
• 集合中必存在唯一的“最后元素”
• 除最后一个元素外，其它元素都有后继
• 除第一个元素外，其它元素都有前驱

线性表-单链表结点

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