顺序表采用数组实现，并且通过继承AbstractList类，下图为顺序表的存储结构图：
该图为顺序表的存储结构
具体代码如下：【详见SequenceList.java】
package datastructure.linear.sequence;
import datastructure.exception.StructureException;
import datastructure.linear.AbstractList;
public class SequenceList<T> extends AbstractList<T>{
/**
* 该顺序表的默认容量为10
*/
private final static int defaultCapacity = 10;
/**
* 实现顺序表的数组
*/
private Object[] arrs;
/**
* 实例化顺序表，使用默认的容量大小，为10
*/
public SequenceList() {
this(defaultCapacity);
}
/**
* 实例化顺序表， 指定顺序表的容量
* @param capacity
*/
public SequenceList(int capacity) {
arrs = new Object[capacity];
size = 0;
}
@Override
public void insert(int index, T t) throws StructureException {
if(arrs.length <= size) {
throw new StructureException("顺序表的容量已满");
}
if(index < 0 || index > size) {
throw new StructureException("参数异常！不能小于0或者大于当前长度");
}
// 插入前先后移之后的元素
for(int i = size ; i > index ; i--) {
arrs[i] = arrs[i-1];
}
arrs[index] = t;
size ++;
}
@Override
public void delete(int index) throws StructureException{
if(isEmpty()) {
throw new StructureException("该顺序表为空！不存在任何元素");
}
if(index < 0 || index >size - 1) {
throw new StructureException("参数异常！不能小于0或者大于顺序表的容量");
}
for(int i = index+1 ; i < size ; i++ ) {
arrs[i-1] = arrs[i];
}
arrs[size -1] = null;
size--;
}
@SuppressWarnings("unchecked")
@Override
public T get(int index) throws StructureException {
if(isEmpty()) {
throw new StructureException("该顺序表为空！不存在任何元素");
}
if(index < 0 || index >arrs.length) {
throw new StructureException("参数异常！不能小于0或者大于顺序表的容量");
}
return (T) arrs[index];
}
}
顺序表上的插入和删除是顺序表中时间复杂度最高的成员函数。在顺序表中插入一个数据元素时，算法中时间复杂度最高的部分是循环移动数据元素。循环移动数据元素的效率与插入数据元素的位置pos有关，最坏情况是pos=0,需移动size个数据元素；最好情况是pos=size，需移动0个元素。
顺序表的时间复杂度：顺序表中的其余操作都是与数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n)，其余操作的时间复杂度为O(1).
顺序表的主要优点：算法简单，空间单元利用效率高；主要缺点是需要预先确定数据元素的最大个数，并且插入和删除操作时需要移动较多的数据元素。
测试类：代码如下：
package datastructure.linear.sequence;
import static org.junit.Assert.fail;
import org.junit.Test;
import datastructure.exception.StructureException;
import datastructure.linear.List;
public class SequenceListTest {
@Test
public void testSequenceList() throws StructureException {
List<String> list = new SequenceList<String>();
list.insert(0, "asdas");
list.insert(1, "sdf");
list.insert(1, "a");
int index = 0;
while(index < 10) {
if(list.get(index) != null) {
System.out.println(index + "----" + list.get(index));
}
index ++;
}
System.out.println(list.size());
}
@Test
public void testSequenceListInt() throws StructureException {
List<Integer> list = new SequenceList<Integer>();
for(int i = 0 ; i < 10 ; i ++) {
list.insert(i, i+1);
}
list.delete(4);
for(int i = 0 ; i < list.size() ; i++) {
System.out.print(list.get(i) + " ");
}
}
@Test
public void testInsert() {
fail("尚未实现");
}
@Test
public void testDelete() {
fail("尚未实现");
}
@Test
public void testGet() {
fail("尚未实现");
}
@Test
public void testSize() {
fail("尚未实现");
}
@Test
public void testIsEmpty() {
fail("尚未实现");
}
}
