定义

线性表（ Linear list ）是具有相同数据类型的 n （ n ≥0）个数据元素（ a1， a2，...， an ）的有限序列。它只有一个开始结点 a1 和一个终端结点 an ，其余的结点 ai （1＜ i ＜ n ）都有且仅有一个前驱结点 ai-1和一个后继结点 ai+1。 a1 称为表头， an 称为表尾， n 是表的长度。

线性表中数据元素的长度通常是相同的，在程序设计时常用数组实现。线性表常见的运算有存取、查找、插入、删除、更改、排序、合并、分解和求长度等。

顺序表

用顺序存储结构存储的线性表称作顺序表。对于数据元素长度相同的顺序表，可以对任意元素进行随机存取。设线性表为 A=（ a1,a2,...,an ）， a1 的地址为 Loc （ a1），元素的长度为 d ，则线性表中任意元素 ai 的地址：

Loc(a^i) = Loc(a^i) + ( i - l ) * d // l <= i <= n

只要知道顺序表的首地址和每个数据元素所占单元的字节个数就可以求出第 i 个元素的地址，这就是顺序表随机存取的原理和特点。

插入

在某一任意处添加一个元素，则需要将位置之后的所有的元素进行后移，然后插入数据，最后长度加一。

最理想插入的就是插到最后面，最不理想的就是插到最前面，平均 n + 1。算法的时间复杂度为 O(n)。

删除

与添加相同，需要挪动删除后的每一个元素，算法的复杂度为 O(n)。