线性表
线性表的定义
线性表是具有相同特性的数据元素的一个有限序列。线性表属于逻辑结构中的线性结构，它包括顺序表、链表、栈、队列等。
线性表在存储结构上有顺序存储和链式存储两种方式，但不管哪种存储方式，它们的结构都有如下特点：
- 均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一个线性表来说，数据元素必须具有相同的数据类型和长度。每个数据元素都是单个元素。
- 有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之间的相对位置是线性的，即存在唯一的”第一个”和”最后一个”数据元素。除了第一个和最后一个外，其他元素前面均只有一个数据元素(直接前驱)，后面均只有一个数据元素(直接后继)。
- 有限性：表中元素的个数是有限的
- 抽象性：只讨论表中元素间的关系，不考虑元素究竟表示什么内容
线性表的顺序存储（顺序表）
顺序表是顺序存储结构的线性表，是把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中指定位置开始的一块连续的物理地址的空间中。由于顺序表的逻辑地址与其物理地址皆相邻，故称为顺序表。
编程语言中的数组就是顺序表的一个典型实例。
表中的任一元素的地址都可以通过这个公式得到：$LOC(d_i)=LOC(d_1)+(i-1)*L 1≤i≤n $其中，L是元素占用存储单元的长度。
顺序表的特点
优点：
1.空间利用率高，数据是连续存放，命中率比较高
2.不用为表示结点间的逻辑关系而增加额外的开销
3.顺序表可以按照元素下标**==随机访问==**
缺点：
1.在插入和删除时大约移动平均一半的元素，对比较大的顺序表操作时效率很低
最好情况是：在表尾插入和删除
最坏情况是：在表头插入和删除
2.需要预先分配足够大的空间，估计过大，导致空间浪费；估计过小，会造成溢出
此处需要注意的是：数组的动态分配还是顺序存储结构，并不是链式存储。数组的动态分配是开辟一块更大的存储空间来替换原本的存储空间。
**时间复杂度 :**插入和删除操作为O(n)。
查找操作：
如果是按照元素序号和首地址来查找的话，时间复杂度是O(1)；如果是按照元素值查找的话，时间复杂度是O(n)。
线性表的链式存储(链表)
链表是链式存储结构的线性表，是用任意一组物理地址来存储数据元素，而数据元素之间的逻辑关系通过指针来表示。所以它的存储结构可以是连续的，也可以不是连续的。
一般我们说的链表都是不连续的。有一种用数组来表示的特殊链表，叫做静态链表，它的存储结构就是连续的。
优点：
1.插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可。
2.没有空间限制,存储元素无上限,只与内存空间大小有关.
3.动态分配内存空间，不用事先开辟内存
4.是内存的利用率变高
缺点：
1.占用额外的空间以存储指针，比较浪费空间，不连续存储，malloc函数开辟空间碎片比较多)
2.查找速度比较慢，因为在查找时，需要循环链表。
**时间复杂度 :**查找操作为O(n) ,插入和删除操作为O(1)。
4.有序表
我们很容易把有序表与顺序表、链表相提并论，其实这是错误的。因为顺序表、链表是根据线性表的存储结构(顺序或链式)来划分概念的，而有序表是根据线性表的数据元素的数值大小来划分概念，故有序表与顺序表、链表不是相互独立的，而是内容互相交错的。
有序表是指表中所有数据元素的数值以递增或递减方式有序排列，是数据元素的数值的有序性。
有序表只描述元素之间的逻辑关系，故为逻辑结构，因此有序表既可以顺序存储也可以链式存储。
例如，数组int array[3]=[1,2,3];是顺序存储结构的有序表。因为是数组，所以是顺序存储结构；因为数据元素[1,2,3]是从小到大排列，故是有序表。而单链表1->2->3则是链式存储结构的有序表。由这个例子可见：有序表与顺序表、链表不是相互独立的，而是内容互相交错的，我们不能把他们相提并论。