定义
线性表(List)：零个或多个数据元素的有限序列
数学定义
若将线性表记为（a1, …, ai-1, ai, ai+1, … , an）,则表中ai-1领先于ai，ai领先于ai+1，那么此时我们称ai-1为ai的直接前驱元素，ai+1为ai的直接后继元素。当i=1，2，…，n-1时，ai有且仅有一个直接后继，当i=2，…，n时，ai有且仅有一个直接前驱。
Ps：当n=0，我们称此线性表为空表。n表示的是线性表的元素个数，定义为线性表的长度
线性表的顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
ps：就是我们开辟出一块内存，固定的，然后把数据元素一个一个依次放入，这个可以用c语言的一位数组来表示，就是第一个元素放入下表为0的位置，依次类推。
所以我们这里区分两个概念，数组的长度，线性表的长度。
数组的长度就是我们开辟这块空间的长度一般是固定不变的
线性表的长度是这个线性表的元素个数，一般线性表的元素个数不能超过开辟的空间长度，否则越界了。所以这里就有一个：线性表的长度永远小于等于数组的长度
Ps:你会疑问，说我们平时学习的oc，c++等数组都是动态的，给多少都行啊，你这里怎么说这个数组的长度的固定的，上去先开辟好了固定的空间呢，这个咱们讲的是数据结构，底层的语言，你说的那些的确是数组动态分配的，这些都是些上层高级语言。
顺序存储结构的插入和删除
1》插入：因为线性表顺序存储是一个接一个连续的，所以插入操作，某个地方插入之后，她后面的元素都要一次往后移动一位
插入算法思路：
1:如果插入位置不合理，抛出异常。比如当前一共n个元素，你插入到n+5的位置。
2:如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
3:从最后一个元素开始向前遍历到 i 处，分别将它们向后移动一个位置
4:将要插入的元素填入位置 i 处
5:表长加1
2》删除：因为线性表顺序存储是一个接一个连续的，所以删除操作，某个地方删除之后，她后面的元素都要一次往前移动一位
删除算法思路：
1:如果删除位置不合理，抛出异常。
2:去除删除元素
3:从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
4:表长减1
线性表顺序存储的优缺点
优点：1》无须为表示表中元素之间的逻辑关系而增加额外的存储空间（链式存储需要，详见下节介绍）
2》可以快速的存取表中任一位置元素（也就是可以快速找到，因为它们都是顺序的，一个挨一个，可以通过下标快速找到）
缺点：1》插入，删除操作需要移动大量元素
2》当线性表长度变化较大时，难以确定存储空间的容量
3》造成存储空间的“碎片”
线性表的链式存储结构
前章节回顾：上节我们学习的线性表的顺序存储，我们最后总结了它的最大缺点是什么，即“插入和删除时需要移动大量的元素”，因此针对解决此问题，我们本节来学习引入线性表的链式存储结构
因为线性表的链式存储结构它们每个元素的存放地址都是不连续的，没法直接知道每个元素的前驱元素和后继元素，但是还需要满足线性表的定义，即出了第一和最后一个元素，每个元速都有且仅有一个前驱和后继，因此线性表的链式存储的介绍为：
为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储本身的信息之外，还需要存储一个指示其直接直接后继元素的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为节点
定义
N个节点（ai的存储映像）链接成一个链表，即为线性表的链式存储。
ps：上述说的链表每个节点中只包含一个指针域，所以叫做单链表
1，我们把链表中第一个节点的存储位置叫做头指针
2，有时，我们为了方便对链表的操作，会在单链表的第一个节点前附设一个节点，称为头节点。头节点的数据域可以不存储任何信息，指针域指向第一个节点的指针
头指针与头节点的区别
头指针：1》头指针是指链表指向第一个节点的指针，若链表有头节点，则是指向头节点的指针
2》头指针具有标示作用，所以常用头指针冠以链表的名字
3》无论链表是否为空。头指针均不为空。头指针是链表的必要元素
头节点：1》头节点是为了操作的统一和方便而设立的，放在第一元素的节点之前，其数据域一般无意义（为空或存放链表的长度）
2》有了头节点，对在第一元素节点前插入节点和删除第一节点，其操作就与其他节点的操作就统一了
3》头节点不一定是链表必须元素
单链表
定义：链表每个节点中只包含一个指针域，所以叫做单链表
1，单链表的读取
单链表读取的算法思路（获取第 i 个数据）
1》声明一个指针p指向链表的第一个节点，初始化 j 从1开始
2》当 j<1 时，就遍历链表，让p的指针向后移动，不断指向下一节点，j 累加1
3》若到链表末尾p为空，则说明第 i 个节点不存在
4》否则查找成功，返回节点p的数据
ps：介绍一下上面的思路，我们要读取第 i 个元素，怎么才能拿到第二个元素呢，我们得知道第 i 个元素存放的地址吧，那么这个元素的存放地址我们在哪找呢，对于链式存储，他是在第i - 1个元素的指针域中存放的，所以我们只要找到i-1个元素就可以了，但是i-1个元素怎么得道，就是又回到起点了，这样依次找，就说明我们先需要找到第一个元素，很庆幸第一个元素对于链表来说我们时已知的，这样我们通过第一找到第二，第二找到第三最终就可以找到地 i 个了。但是对于线性表的顺序存储是怎样的呢，因为顺序存储我们还是知道第一个元素地址，但是顺序存储在内存中是一个挨一个的，所以我们要找i个元素，直接算出第i个元素的地址就行，直接找到了。就不需要遍历了
2，单链表的插入与删除
1》单链表的插入算法思路（删除第i个节点的算法思路）
声明一个指针p指向链表的头节点，初始化 j 从1开始
否则查找成功，在系统中生成一个空节点s
2》单链表的删除算法思路（插入第i个节点的算法思路）
若到链表末尾p为空，则说明第i个节点不存在
ps：学完之后，你会发现，单链表的插入和删除，都是先找打要插入删除的位置，然后才能进行操作，你会疑问说，你们不是说链式存储的插入和删除相对于顺序存储有很大的优势吗，它的删除和插入不是一样需要遍历，遍历的时间复杂度也是O(n)，也没见多牛逼啊，在此需要解释的是，虽然链式存储的插入和删除都需要直接遍历，不会想顺序存储的那种直接找到，但是链式存储的掺入荷删除之后，都是指影响自己的前后两个元素，不会让其他元素都动一次，但是顺序存储的是插入和删除需要插入删除位置后面的所有元素都动一遍，所以咱们一般说的都是这个动的动作的时间复杂度有利于顺序存储的
3，单链表的整表创建
单链表整表创建的算法思路：
1》生命一个指针p和计数器变量i
2》初始化一个空链表L
3》让L的头节点的指针指向null，即建立一个带头节点的单链表
4》循环
生成一新节点赋值给p
随机生成一数字赋值给p的数据域p->data
将p插入到头节点与前一节点之间
你会发现我们用的是头插法，即新生成总是在最前面。当然我们也可以用尾插法
4，单链表的整表删除
单链表整表删除的算法思路：
1》生命一个指针p和q
2》将第一个节点赋值给p
3》让L的头节点的指针指向null，即建立一个带头节点的单链表
4》循环
将下一节点赋值给q
释放p
将q赋值给p
5，线性表的顺序存储结构和单链表(线性表链式存储结构的一种)结构的对比
存储分配方式：
1》顺序存储结构用一块连续的存储单元一次存储线性表的数据元素
2》单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能：
1》查找：顺序存储O(1) 单链表O(n)
2》插入和删除
顺序存储需要平均移动表长的一半的元素，时间为O(n)
单链表在找出某只的指针后，插入和删除时间仅为O(1)
空间性能：
1》顺序存储结构需要预分配存储空间，分大了，浪费，分小了溢出
2》单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
总结：分别什么时候使用不同的存储结构
1，线性表需要频繁查找，很少进行插入和删除使用顺序存储
2，当线性表中的元素个数变化较大或者根本不知道多大的时候，最后用单链表结构（类似存储一年的月份或者星座可以用顺序存储，既是有序的也是个数有限的）
静态链表
用数组描述的链表叫做静态链表。
静态链表的其他内容，不再详述
循环链表
将单链表中终端节点的指针域由空指针改为头节点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
双向链表
有了单链表，我们可以一次找到下一个元素，但是如果我们想找当前的上一个元素怎么办，如果还是单链表，我们就需要转一圈去找（循环链表），太麻烦，为了解决此问题，我们引入双向链表概念
双向链表是在单链表的每个节点中，在设置一个指向前驱节点的指针域
下图是本章节的整体总结：
