顺序表示和链式表示的比较：
1.读写方式：顺序表可以顺序存取，也可以随机存取；链表只能从表头顺序存取元素；
2.逻辑结构与物理结构：顺序存储时，逻辑上相邻的元素其对应的物理存储位置也相邻；链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻；
3.查找、插入和删除操作：
按值查找，当线性表在无序的情况下，两者的时间复杂度均为o(n)；而当顺序表有序时，可采用折半查找，此时时间复杂度为o(log n)；
按位查找，顺序表支持随机访问，时间复杂度为o(1)；而链表的平均时间复杂度为o(n)。
顺序表的插入和删除操作平均需要移动半个表长的元素；链表的插入、删除操作时，只需修改相关节点的指针即可。
4.空间分配：顺序存储一般是基于静态存储分配，一单存储空间装满就不能扩充；链式存储的节点空间只有在需要的时候申请分配，只要内存有足够的空间即可分配。
顺序表示的实现：
public class ArrayList<E> {
final int defaultSize=0;
int maxSize; //线性表的最大长度
int length; //线性表当前长度
Object[] arrayList; //存储线性表的数组
/*
* 构造函数
*/
public ArrayList(int size){
initList(size);
}
//按给定size初始化顺序表
public void initList(int size) {
if(size < 0){
throw new RuntimeException("数组大小错误：" + size);
}else{
this.maxSize= size;
this.length=0;
this.arrayList = new Object[size];
}
}
//表长
public int length() {
return length;
}
//按值查找
public int locateElem(Object e) {
for(int i=0 ;i<length;i++){
if(arrayList[i] == e){
return i;
}
}
return -1;
}
//按位查找
public Object getElem(int i) {
if(i<0 || i>=length ){
throw new RuntimeException("参数出错："+i);
}
if(length ==0){
throw new RuntimeException("顺序表为空");
}
return arrayList[i];
}
//插入
public void insert(int i, Object e) {
if(i<0 || i>length+1 ){
throw new RuntimeException("新元素插入位置有误："+i);
}
if(i >= maxSize){
throw new RuntimeException("顺序表已满，不能再插入新的元素");
}
for(int j=length;j<i; j--){
arrayList[j]=arrayList[j-1];
}
arrayList[i]=e;
length++;
}
//删除
public void delete(int i, Object e) {
if(i<0 || i > length-1){
throw new RuntimeException("需删除元素位置有误："+i);
}
if(length == 0){
throw new RuntimeException("顺序表为空，不能删除元素");
}
for(int j=i;j<length-1;j++){
arrayList[j] = arrayList[j+1];
}
arrayList[length-1]="";
length--;
}
//判空
public boolean isEmpty() {
return length==0 ? true : false;
}
//删除顺序表
public void destroyList() {
this.arrayList=null;
this.length=0;
this.maxSize=0;
}
}
单链表表示的实现：