Part one
线性表基本概念
线性表定义：具有相同特征数据元素的一个有限序列，可以为空，即n为0。
线性表的逻辑特性：只有一个表头，只有一个表尾，表头前没有数据元素，表尾后没有数据元素，除了表头以及表尾以外的数据元素有且只有一个直接前驱，一个直接后继。
线性表的存储结构：顺序存储结构-->顺序表：把线性表中所有元素按照其逻辑顺序，依次存储到从指定的存储位置开始的一块连续的存储空间当中，即第i+1个元素紧跟在第 i个元素后面。
链式存储结构-->链表：每个结点当中不仅包含所存元素的信息，还包含元素之间的逻辑关系，单链表只包含和后继元素的逻辑关系。
线性表两种存储结构的比较：顺序表：支持随机访问的特性，因为只要知道了表头的位置，就可以找到任何一个元素的位置；占用连续的存储空间，因此所有存储空间应当 预先分配好；添加或删除数据元素需要移动多个元素，当数据量很大时较为繁琐。
链表：不支持随机访问的特性，由于链表当中的结点不仅仅包含元素的信息，同时还包含了元素之间的逻辑关系，因此无法通过第一个元素的 置来确定其他元素的位置；存储空间利用率稍低一些，由于结点不仅要储存数据信息还同时要存储数据之间的逻辑关系；支持存储空间 的动态分配，由于链表中当前结点的位置是有前驱结点中的地址信息所指示的，因此链表中的结点可以散落在内存中的任意位置，即不 需要一次性预先分配好存储空间；添加或删除数据元素时无需移动元素，只需要修改指针即可。
链表有以下5种形式：单链表、双链表、循环单链表、循环双链表、静态链表。
链表中带头结点和不带头结点的区别：带头结点的链表中有一个结点不储存信息（或者仅储存一些描述链表属性的信息，例如表长等等），而不带头结点的链表当中所有结 点都储存信息。但无论是带头结点还是不带头结点的链表，头指针都指向链表当中的第一个结点，而头结点是带头结点链表中的第一 个结点，只作为链表存在的标志。
判断各种链表为NULL的条件：单链表&双链表：带头结点为head->next等于NULL时；不带头结点为head等于NULL时。
循环单链表：带头结点为head等于head->next时；不带头结点为head等于NULL时。
循环双链表：带头结点为head->next==head或head->prior==head有一个成立或者两个都成立时；不带头结点为head等于NULL时。
静态链表的特点：静态链表的结点空间来自于一个结构体数组，数组中每个结点有两个分量：一个是数据元素分量data；另一个是指针分量指示了当前结点的直接后继结点 在数组当中的位置（这和一般链表当中的next指针有相同的地位），静态链表中的指针不是通常所指的指针型变量，而是一个存储数组下的整形变量，其 功能类似于指针，因此称为指针。
对顺序表进行插入和删除元素算法时间复杂度分析：
具有n个元素的顺序表，插入一个元素进行的平均移动个数为多少？
每个位置被插入数据的概率是1/n，在第i个元素之后插入元素，则要移动元素个数为n-i，则移动元素个数的期望E=p((n-1)+(n-2)+...+0)=(n-2)/2，因此平均时间复杂 度为O(n)。
原文：https://www.cnblogs.com/jinyuhao117/p/10666671.html