文章导读
【本文首先介绍了线性表在计算机中的顺序存储结构，之后重点讨论了线性表的实现方式及元素插入等算法，并给出了详尽的代码。代码案例也可以在指定的网站下载】
在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的数据元素。
假设表中一个数据元素占K个存储单元，长度为n，表第一个元素的地址为LOC（a），则第二个元素的地址为LOC（a+k），第i个元素的地址为LOC（a+(i-1)*k）。
线性表的这种机内表示称作线性表的顺序存储结构，它以元素在计算机内物理位置上的紧邻来表示线性表中数据元素之间相邻的逻辑关系。每一个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数（见图1）。即根据元素的序号和表首地址就可以得到该元素的存储地址，所以线性表的顺序结构是一种随机存取的存储结构。
图1 线性表顺序存储结构图
线性表的顺序存储结构可以用编程语言中的向量（一维数组）来表示，数组的下标为元素在线性表中的序号，通过下标可以完成对某个元素的存取。
线性表在Java语言中，可以用ArrayList来表示。ArrayList是一个动态数组，它提供了数组空间管理、元素添加、插入、删除等操作。下面通过一个项目案例，编写LinearList类，实现ArrayList的数组空间管理、元素的添加、插入和删除操作。
LinearList类的属性
LinearList类定义了三个基本属性。MIN_CAPACITY_INCREMENT属性用于定义数组的扩充容量；size属性定义了列表的长度，即列表已存储元素的个数；array属性定义了一个Object数组，用于存储Object类型的元素，当数组空间不够时，可以扩充数组空间以容纳更多的元素。
/** * LinearList扩充容量的最小值 */ private static final int MIN_CAPACITY_INCREMENT = 12; /** * 列表的长度 */ int size; /** * LinearList基于数组方式实现 * 数组类型为Object，这样可以容纳所有Java对象类型 * 数组声明为transient类型，禁止数组序列化 */ transient Object[] array;
LinearList类的构造函数
LinearList类提供了两个构造函数。一个是指定容量的构造函数，创建LinearList类实例时，可以指定LinearList类的空间容量。一个是默认的构造函数，用于创建具有默认空间容量的LinearList类实例。
/**
* 创建一个指定带容量大小的LinearList
*/
public LinearList(int capacity) {
if (capacity < 0) {
//抛出参数异常
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? new Object[MIN_CAPACITY_INCREMENT] : new Object[capacity]);
size = 0;
}
/**
* 创建一个无参构造的LinearList
*/
public LinearList() {
array = new Object[MIN_CAPACITY_INCREMENT];
size = 0;
}LinearList类的添加方法add
add方法添加一个元素到列表的尾部。在添加元素之前，需要判断存储元素的数组空间是否已满，若已满，需要重新申请数组空间，并调用arraycopy方法复制原数组元素到新数组元素。
add算法在数组容量充裕的条件下，其执行时间是个常量，算法复杂度为O(1)。当数组容量需要重新申请的条件下，其执行时间与列表长度n有关，算法复杂度为O(n)
/**
* 添加方法，添加到列表的尾部
*/
public boolean add(Object obj) {
//将array赋值给一个局部数组
Object[] a = array;
//获取列表的长度
int s = size;
//如果列表的长度等于数组array的长度，空间不够，需要声明一个新数组
if ((s+1) == a.length) {
//声明的新数组长度为原长度加上扩展容量长度
Object[] newArray = new Object[s + MIN_CAPACITY_INCREMENT];
arraycopy(a, 0, newArray, 0, s);// 把原来的数组拷贝到新的数组中来
array = a = newArray;
}
a[s] = obj;// 把元素添加进来
size += 1;// 长度+1
return true;
}LinearList类的添加方法insert
insert方法在指定的列表位置插入一个元素。在插入元素之前，需要判断存储元素的数组空间是否已满，若已满，需要重新申请数组空间。无论是否重新申请数组空间，都需要将插入位置及位置之后的元素顺序后移。
insert算法执行时间与插入位置i相关。一般来说在估算算法的时间复杂度时，均以数据集中最坏的情况来估算，因此insert算法复杂度为O(n)。
/**
* 插入方法，插入一个元素到指定的位置
*
* @param index : 插入元素所在的位置
* @param obj: 需要插入的元素.
*
* */
public void insert(int index, Object obj) {
Object[] a = array;
int s = size;
if (index > a.length || index < 0) {
//抛出参数异常
throw new IllegalArgumentException("index异常" + index);
}
// 当数组长度容量足够时，从index位置开始，顺序后移s-index个元素
if ((s+1) < a.length) {
arraycopy(a, index, a, index + 1, s - index);
} else {
// 当数组容量不足时，进行扩容
// assert s == a.length;
// 创建新数组
Object[] newArray = new Object[s + MIN_CAPACITY_INCREMENT];
// 将数据拷贝到新数组中，并移动位置
arraycopy(a, 0, newArray, 0, index);
arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = obj;
size = s + 1;
}LinearList类的删除方法remove
remove方法删除列表中index指向的元素。删除元素之前需要判断index是否在列表长度范围内。删除元素后，需要把index之后的元素顺序前移动。
romove算法执行时间与index相关。一般来说在估算算法的时间复杂度时，均以数据集中最坏的情况来估算，因此romove算法复杂度为O(n)。
/**
* 删除列表中指定位置上的元素
* @param index 删除元素所在的列表位置
*
* */
public void remove(int index) {
Object[] a = array;
int s = size;
if (index >= s || index < 0 ) {
//抛出参数异常
throw new IllegalArgumentException("index异常" + index);
}
// 将删除位置之后的s-index个元素向前挪动一个位置
arraycopy(a, index + 1, a, index, --s - index);
// 将数组末尾置空
a[s] = null;
size = s;
}文章小结
顺序存储结构是线性表在计算机中最简单和最常用的存储方式，该存储方式可以实现线性表数据元素的随机存取，元素访问速度快。元素的插入和删除需要移动表中的元素，算法的时间复杂度为O（n）。文章也给出了列表的实现代码，模拟了ArrayList的部分功能，可以下载学习和使用。
课程案例源码下载地址：
gitee.com/jianxh/algorithm