☺线性表（Linear List）是由n (n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做（a1,a2,…，ai-1，ai，ai+1， …，an）。
数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。☺线性表（Linear List）是由n (n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做（a1,a2,…，ai-1，ai，ai+1， …，an）。
数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。
实际上，链表就是一种典型的线性表（链式储存）。
线性表的三个特点：
- 同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。
- 有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。
- 有序性：线性表中相邻数据元素之间存在着 序偶关系<ai,ai+1>。
一、线性表的顺序存储：
简单来讲，数组就算是顺序储存，在编程学习过程中，我们之前提到了数组加法的定义——下标向后改变指向，实际上就是因为顺序储存的物理相邻状态与逻辑相邻状态一致。
顺序操作的基本运算如下：
☺查找操作： 两种：1、按序号和2、按内容，选取哪一种主要取决于得到的相关信息是什么。
☺插入操作： 相比链式存储而言，顺序表的插入显得非常繁琐，为了在中间插入某个数往往需要将其后的数全部依次后移。
注意这里k–是为了避免出现数据覆盖的情况而从后向前依次进行移位操作。
其实讲道理，这种插入操作本身也算一种“原地算法”。算法分析如下：
☺删除操作：讲道理和上面插入其实一样的，因此算法复杂度也都是O(n)。
☺顺序表合并算法：
☺算法思想 ：
♫设表LC是一个空表，设两个指针i、j分别指向表LA和LB中的元素，
♫若LA.elem[i]>LB.elem[j]，则当前先将LB.elem[j]插入到表LC中，
♫若LA.elem[i]≤LB.elem[j] ，当前先将LA.elem[i]插入到表LC中，
♫如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。因此算法的时间复杂度其实就和两表长度和有关
其实也完全可以先直接一股脑全部塞进去，再利用qsort（）函数进行排序（从懒得写代码的角度来说我其实更喜欢这个）。
顺序存储总结：
顺序储存固然方便，但同时也存在诸多不足。因此，在一些特定情况下，顺序存储显然已不能满足要求，此时就需要用到链式存储。
二、线性表的链式存储：
☺采用链式存储结构的线性表称为链表 。
☺每个节点包含指针域（存放位置）和数据域（存放结点的值）
☺设计链式存储结构时，每个逻辑结点存储单独存储，为了表示逻辑关系，增加指针域。
（物理上不一定相连，是由指针域来保持逻辑关系上相连的）
仅有后继节点的是单链表，而多一个前驱节点则成为了双链表
（附上一个不错的简述：https://blog.csdn.net/SlimShadyKe/article/details/89503062?spm=1001.2014.3001.5506）
为什么要添加头节点，有什么优点：
- 第一个结点的操作和表中其他结点的操作相一致，无需进行特殊处理；
- 无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。
对于链表的初始化和插入删除等操作，这里有一个较为详细的教程：
注：查找无论是按序号还是按值，都必须确认当前是否处于一个合法的位置（即判断是否越界，检查是否为NULL），不同点在于一个加了计数器辅助，另一个用值域做筛选。
计算长度和按序号查找加入计数器的方法类似。
循环链表：
与非循环单链表相比，循环单链表：
- 链表中没有空指针域
- p所指结点为尾结点的条件：p->next==L（头节点）
由此可见带尾结点的链表结构在进行一些运算时比仅有头指针的链表表现更优（查找，合并等操作），比如：
双向链表：
相比单向链表，既有后继节点又有前驱节点，从任一结点出发可以访问其他结点。
对应的，也有双向循环链表。
链式存储总结：
下一单元总结链接：ch3栈和队列