下载掌阅APP，畅读海量书库
立即打开
顺序表采用顺序结构存储数据，在Java语言中常用的顺序存储结构是数组。顺序表如图2-1所示。
图2-1 顺序表存储示例
在顺序表指定位置添加元素，首先需要确定指定位置是否已经有元素。如果指定位置没有元素，就直接加入元素，如图2-2所示。
图2-2 顺序表末尾添加元素示意图
如果指定位置已经有元素，就需要将指定位置处的元素及其后续元素依次向后移动，将指定位置空出后，插入指定元素，如图2-3所示。
图2-3 顺序表非末尾位置添加元素示意图
当顺序表按照索引查找元素时，将以O(1)的时间复杂度查找到指定的元素，如图2-4所示。
图2-4 顺序表查找指定位置元素示意图
顺序表按照元素值查询指定元素时，需要从第一个元素开始依次向后查找元素，直至找到指定元素，查找的时间复杂度为O(n)。查找V5元素的过程如图2-5所示。
图2-5 顺序表查找指定元素示意图
如果从顺序表删除的元素是末尾元素，就直接删除即可，如图2-6所示。
图2-6 顺序表删除末尾元素示意图
如果删除的元素并非末尾元素，就已删除元素后面的所有元素将依次向前移动，如图2-7所示。
图2-7 顺序表删除非末尾元素示意图
创建顺序表实现类SequenceList并实现List接口。其中使用对象数组Object[]存储线性表中的数据。顺序表SequenceList类的代码如下：
创建顺序表测试类，验证顺序表的功能。测试类的代码如下：
执行顺序表测试类，测试结果如下：
因为线性表有最大容量maxSize = 15的限制，所以在测试代码中再次添加新元素100时，将会抛出“顺序表已满，无法插入！”的异常信息。
（1）顺序表的概念：顺序表是使用顺序结构存储的线性表。
（2）顺序表的存储：顺序表必须使用一块连续的存储空间存储数据。
（3）顺序表的优点：顺序表是使用顺序结构存储数据的，通过索引访问元素的时间复杂度为O(1)。
（4）顺序表的缺点：
· 顺序表的存储空间必须是连续的，如果在顺序表中存储大量数据，那么对存储介质的容量是一个挑战。
· 顺序表的存储容量是有限的、固定的，超过顺序表的存储容量将无法进行数据存储。
· 顺序表中按值查找元素的时间复杂度为O(n)。
· 在顺序表的非末尾位置添加元素将导致顺序表此位置后的元素依次向后移动。
· 在顺序表的非末尾位置删除元素将导致顺序表此位置后的元素依次向前移动。
（5）JDK中的实现：JDK中的ArrayList实现了顺序表，并提供了动态扩容等高级特性，ArrayList的详细内容可参考本书4.2节。