顺序表示和链式表示的比较：

1.读写方式：顺序表可以顺序存取，也可以随机存取；链表只能从表头顺序存取元素；

2.逻辑结构与物理结构：顺序存储时，逻辑上相邻的元素其对应的物理存储位置也相邻；链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻；

3.查找、插入和删除操作：

　　按值查找，当线性表在无序的情况下，两者的时间复杂度均为o(n)；而当顺序表有序时，可采用折半查找，此时时间复杂度为o(log n)；

　　按位查找，顺序表支持随机访问，时间复杂度为o(1)；而链表的平均时间复杂度为o(n)。

　　顺序表的插入和删除操作平均需要移动半个表长的元素；链表的插入、删除操作时，只需修改相关节点的指针即可。

4.空间分配：顺序存储一般是基于静态存储分配，一单存储空间装满就不能扩充；链式存储的节点空间只有在需要的时候申请分配，只要内存有足够的空间即可分配。

顺序表示的实现：

public class ArrayList {
? ? 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? ? ? ? ? ? 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? ? ? ? ? ? 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? ? ? ? ? ? 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;
? ? }
}

单链表表示的实现：

class Node{
? ? E e;? //数据
? ? Node next; //下一个节点
? ?
? ? Node(){}
? ?
? ? Node(E e){
? ? ? ? this.e = e;
? ? ? ? this.next = null;
? ? }
}

public class LinkedList {
? ? private Node header = null;? //头结点
? ? int size=0;? ? //链表大小
? ?
? ? public LinkedList() {
? ? ? ? this.header = new Node();
? ? }

? ? //得到链表的长度
? ? public int length() {
? ? ? ? return size;
? ? }

? ? //按值查找节点，返回该节点的位置
? ? public int locateElem(E e) {
? ? ? ? Node temp = header;
? ? ? ? int count = 1;
? ? ? ? while(temp.next != null && temp.e != e){
? ? ? ? ? ? temp = temp.next;
? ? ? ? ? ? count ++;
? ? ? ? }
? ? ? ? return count;
? ? }

? ? //找到第index个位置的节点
? ? public Node getNode(int index) {
? ? ? ? if(index > size || index < 0){
? ? ? ? ? ? throw new RuntimeException("索引值有错：" + index);
? ? ? ? }
? ? ? ? Node temp = new Node();
? ? ? ? temp = header;
? ? ? ? int count=1;
? ? ? ? while(count != index){
? ? ? ? ? ? temp = temp.next;
? ? ? ? ? ? count ++;
? ? ? ? }
? ? ? ? return temp;
? ? }