顺序表其实就是我们所熟悉的数组，擅长随机访问，给定位置能够高效的获取/修改指定位置的值，时间复杂度为O(1)，但按值查找、插入、删除等时间复杂度均为O(n)。对于尾插和尾删，时间复杂度为O(1)。
SeqList的实现：
package SeqList; public class SeqList { //数组最大容量为10，但这10个元素不一定都是有效元素 private int[] data = new int[10]; //表示数组当前有效元素个数 private int size = 0; //打印 public void display() { System.out.print("["); for(int i=0;i<size;i++) { System.out.print(data[i]); if(i != size-1) { System.out.print(","); } } System.out.println("]"); } //增加元素 //pos为放在哪个下标，elem为插入哪个元素 public void add(int pos,int elem) { //pos无效 if(pos < 0 || pos > size) { return; } if(this.size >= this.data.length) { //容量不够，需扩容 //申请一块更大的内存，再把原有数据拷贝过去 realloc(); } //pos == size 相当于尾插 if(pos == size) { this.data[pos] = elem; this.size++; return; } //在中间位置插入，要进行搬运 for(int i = this.size; i > pos; i--) { this.data[i]=this.data[i-1]; } this.data[pos] = elem; this.size++; } //扩容 private void realloc() { //根据实际场景来选择是线性增长还是指数增长，亦或其它方式 //扩容是比较大的开销 int[] newData = new int[this.data.length*2]; for(int i=0; i<this.data.length;i++) { newData[i]=this.data[i]; } this.data = newData; } //判断元素是否存在 public boolean contains(int toFind) { for(int i=0;i<this.size;i++) { if(this.data[i] == toFind) { return true; } } return false; } //查找元素 public int search(int toFind) { for(int i=0;i<this.size;i++) { if(this.data[i] == toFind) { return i; } } return -1; } //获取pos位置 public int getPos(int pos) { return this.data[pos]; } public void setPos(int pos,int elem) { this.data[pos] = elem; } //删除第一次出现的值为key的元素 public void remove(int toRemove) { int pos = search(toRemove); if(pos == -1) { //该值不存在，不必删除 return; } if(pos == this.size-1) { //如果是最后一个元素，直接size-- this.size--; return; } //普通位置的删除，也需搬运 for (int i = pos; i < size-1; i++) { this.data[i] = this.data[i+1]; } this.size--; } //求长度 public int size() { return size; } //清空 public void clear() { this.size = 0; //缩容 this.data = new int[10]; } }Test测试类：
package SeqList; public class Test { public static void main(String[] args) { TestAdd(); TestContians(); TestSearch(); TestRemove(); } public static void TestAdd() { System.out.println("测试添加："); SeqList seqList = new SeqList(); seqList.add(0, 1); seqList.add(1, 2); seqList.add(2, 3); seqList.add(3, 4); seqList.add(2, 5); seqList.display(); } public static void TestContians() { System.out.println("测试contians方法："); SeqList seqList = new SeqList(); seqList.add(0, 1); seqList.add(1, 2); seqList.add(2, 3); seqList.add(3, 4); boolean ret = seqList.contains(2); System.out.println("ret预期是true，实际是："+ret); } public static void TestSearch() { System.out.println("测试search方法："); SeqList seqList = new SeqList(); seqList.add(0, 1); seqList.add(1, 2); seqList.add(2, 3); seqList.add(3, 4); int ret = seqList.search(3); System.out.println("ret预期是2，实际是："+ret); } public static void TestRemove() { System.out.println("测试remove方法："); SeqList seqList = new SeqList(); seqList.add(0, 1); seqList.add(1, 2); seqList.add(2, 3); seqList.add(3, 4); seqList.remove(3); System.out.print("预期是:[1,2,4]，实际是:"); seqList.display(); } }运行结果：
