下载掌阅APP，畅读海量书库
立即打开
线性表是由N个相同数据类型的数据元素组成的有限序列，其中除了第一个数据元素外，每个元素有且仅有一个直接前驱结点，除最后一个数据元素外，每个元素有且仅有一个直接后继结点。
线性表数据类型主要包括两个方面：数据元素集合和该数据元素集合上的操作集合。
数据元素集合可以表示为A0,A1,A2,...,An-1大小为N的数据集合。
操作集合包括以下操作：
（1）向线性表插入元素。
（2）从线性表删除元素。
（3）从线性表查找元素。
（4）判断线性表是否为空。
（5）求线性表的元素个数。
线性表是一种逻辑结构，这种逻辑结构在计算机中的表现形式（存储结构）主要有以下两种：
（1）线性存储：用顺序结构存储的线性表叫作顺序线性表，一般称作顺序表。顺序表一般通过高级语言中的数组类型实现。
（2）链式存储：用链式结构存储的线性表叫作链式线性表，一般称作链表。链表通常是通过定义结点的方式，通过指针（Java语言中使用的是引用）将各个数据元素和数据元素之间的关系体现出来的。
由于线性表有顺序表和链表两种实现形式，因此可以通过软件工程的设计思想对线性表这种数据结构进行抽象，由不同的子类生成不同的线性表的实现。
本节将定义一个List接口，该接口定义了线性表的规范，即定义线性表需要实现的基本操作，这些操作包括插入元素、删除元素、查找元素、判断表是否为空和查询线性表元素个数。List接口代码如下：
（1）线性表的概念。
（2）线性表的存储方式和实现方式。
（3）在线性表中操作元素的时间复杂度。