概念

线性表指的是零个或多个数据元素的有限序列。特点是数据元素之间存在一对一的线性关系，线性表分为顺序存储结构（又称顺序表）和链式存储结构（又称为链表）。顺序表中的元素存储地址是连续的，而链表的元素存储地址是非连续的，元素节点中除了存储数据元素之外还存储相邻元素的地址信息。顺序表中数据之间的逻辑关系和物理关系是一致的，链表中数据元素的逻辑关系和物理关系并不一定一致。

上图中左边为顺序表，右边为链表。顺序表在内存中的地址是连续的，各个元素的下标之间是有规律可循的，通过一个已知下标的元素可以找到顺序表中任意一个其它元素。但是链式表中的元素在内存中的地址是不连续的，所以链式表中的每个元素除了要保存数据信息外，还要保存下一个元素的内存地址，以便形成线性关系。

线性表的数据对象集合为{a1, a2, ..., an}，每个元素的类型均为 DataType。其中，除第一个元素 a1 以外，每一个元素都有且只有一个直接前驱元素，除最后一个元素 an 外，每一个元素都有且只有一个直接后继元素。数据元素之间存在一对一的关系。