线性表的定义和性质
线性表定义
定义：线性表(Linear List)是具有相同物理含义、同一数据类型的n(n >= 0)个数据元素的有限序列。
线性表的特性
1)有且仅有一个开始节点
2)有且仅有一个终端节点
3)除了开始节点和终端节点外，其余节点都有且仅有一个直接前驱和直接后驱
线性表常用的存储方式有两种，即顺序存储结构和链式存储结构
顺序表的定义和性质
顺序表含义
定义：在计算机中按顺序存储结构的线性表简称为顺序表(Sequential List)
顺序表的特征
1)存储单元地址连续(需要一段连续空间)
2)逻辑上相邻的数据元素其物理地址也相邻
3)随机存储
4)存储密度大
顺序表上的插入运算，时间主要消耗在节点的移动上，在第i个位置上插入x，从an到ai都要向下一个移动一个位置，共需移动n-i+1个节点，而i的取值范围为1≤i≤i+1，即有n+1个位置可以插入。
顺序表删除运算的时间主要消耗在移动表的节点上，删除第i个节点，其后面的节点ai+1到an都要向上移动一个位置，共移动了n-1个节点。
插入和删除时间复杂度为O(n),所以当n较大时，算法的效率较低。
在线性表的顺序存储结构中，利用节点的存储位置来反映节点的逻辑关系，节点的逻辑次序与存储空间中的物理次序一致，因而只要确定了线性表中起始节点的存储位置，即可方便的计算出任一节点的存储位置，就可以实现节点的随机访问。
顺序表优点：存储密度大，空间利用率高
顺序表缺点：节点的插入，删除可能需要移动其他节点，一些长度变化较大的线性表必须按照最大需要的空间分配存储空间。