Java数据结构-线性表之顺序表ArrayList

线性表的顺序存储结构，也称为顺序表，指用一段连续的存储单元依次存储线性表中的数据元素。根据顺序表的特性，我们用数组来实现顺序表，下面是我通过数组实现的Java版本的顺序表。

package com.phn.datestructure;/** * @author 潘海南 * @Email 1016593477@qq.com * @TODO 顺序表 * @date 2015年7月16日 */public class FOArrayList<E> {// 顺序表长度private int size;// 顺序表默认数组为nullprivate Object[] data = null;// 顺序表中数组的初始化长度private int capacity;// 顺序表默认初始化长度private static final int DEFUALT_INITIAL_SIZE = 0;/** * 默认无参构造函数 */public FOArrayList（） {this（DEFUALT_INITIAL_SIZE）;}/** * @TODO 带参构造函数 * @param initialSize 初始化顺序表长度 */public FOArrayList（int initialSize） {if （initialSize < 0） {throw new RuntimeException（"数组大小错误:" + initialSize）;}this.data = new Object[initialSize];this.capacity = initialSize;this.setSize（）;}/** * @TODO 设置顺序表的长度 */private void setSize（） {this.size = 0;}/** * @TODO 获取顺序表的长度 * @return size 顺序表的长度 */public int size（） {return this.size;}/** * @TODO 顺序表添加元素 * @param e 数据元素类型 * @return true */public boolean add（E e） {ensureSize（size）;this.data[size] = e;this.size++;return true;}/** * @TODO 顺序表插入元素 * @param index 插入位置 * @param e 数据元素类型 * @return true */public boolean insert（int index, E e） {if （index >= 0 && index <= size） {ensureSize（size）;E temp = （E） this.data[index - 1];this.data[index - 1] = e;this.size++;for （int i = index; i <= size; i++） {E temp2 = （E） this.data[i];this.data[i] = temp;temp = temp2;}} else {throw new RuntimeException（"数组下标错误：" + index）;}return true;}/** * @TODO 顺序表删除元素 * @param index 将要删除的元素的索引位置 * @return E 删除的元素 */public E remove（int index） {validateIndex（index）;E e = （E） this.data[index];for （int i = index; i < size - 1; i++） {this.data[i] = this.data[i + 1];}this.size--;return e;}/** * @TODO 根据元素索引位置获取元素 * @param index 元素的索引位置 * @return E 元素e */public E get（int index） {validateIndex（index）;return （E） this.data[index];}/** * @TODO 将顺序表中索引位置为i的元素修改为元素e * @param index 元素的索引位置 * @param e 需要修改成的元素 * @return true 修改成功标志 */public boolean set（int index, E e） {validateIndex（index）;this.data[index] = e;return true;}@Overridepublic String toString（） {return this.arrayToString（data）;}/** * @TODO 获取字符串形式的顺序表中的数组序列 * @param a 顺序表中的数组 * @return String 字符串形式的顺序表中的数组序列 */private String arrayToString（Object[] a） {if （a == null）return "null";int iMax = this.size - 1;if （iMax == -1）return "[]";StringBuilder b = new StringBuilder（）;b.append（"["）;for （int i = 0;; i++） {b.append（String.valueOf（a[i]））;if （i == iMax）return b.append（"]"）.toString（）;b.append（", "）;}}/** * @TODO 验证所给索引位置是否合法 * @param index 给出的索引位置 */private void validateIndex（int index） {if （index >= this.size || index <= 0） {throw new RuntimeException（"数组下标错误：" + index）;}}/** * @TODO 判断是否需要扩充顺序表容量 * @param currentSize 当前顺序表的大小 */private void ensureSize（int currentSize） {if （currentSize == capacity） {this.capacity = （this.capacity * 3） / 2 + 1;Object[] newData = new Object[this.capacity];for （int i = 0; i < currentSize; i++） {newData[i] = this.data[i];}this.data = newData;}}}

主要注意上述3个私有成员变量，如下：

// 顺序表长度private int size;// 顺序表中数组的初始化长度private int capacity;// 顺序表默认数组为nullprivate Object[] data = null;

如同注释解释的那样，size用来表示顺序表的长度，data用来表示数组,而capacity用来表示数组的长度.
相信data应该比较好理解，而对应的两个长度变量相对难理解一些，下面解释一下：

size指的是对外界访问这个顺序表的长度时展示的值，是顺序表中数据元素的个数，随顺序表插入和删除操作而会进行改变；
capacity表示的是data数组的长度，实际上也是整个顺序表的容量，在顺序表初始化的时候可以赋值，或者之后可以调用顺序表的扩容来进行改变；
size是小于等于capacity的。

这里主要讲讲顺序表的插入和删除：
顺序表的插入演示如图所示：

根据图片可以看出插入一个元素后，插入位置之后的元素都需要向后移动一个位置。
删除操作则是插入操作的逆过程，删除位置之后的元素都需要向前移动一个位置。时间复杂度分析：

在顺序表进行存入，查找和修改时，平均时间复杂度都是O（1）；
而在进行插入和删除操作时，最快时为O（1）,最慢时为O（n），所以平均时间复杂度为O（n）。

解释：上述的存入和插入有区别，存入表示存储在数组末尾，而插入表示插入在任意位置。优缺点分析：
优点：

不用为表示表中数据元素之间的逻辑关系而增加额外的存储空间；
可以快速的存取表中任意位置的元素。
缺点：
插入和删除操作需要移动大量元素；
当线性表的长度变化较大的时候，很难确定存储空间的容量；
容易造成存储空间的“碎片”。

本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-07/120145.htm