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

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
      
       =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
       
         length-1){            throw new RuntimeException("需删除元素位置有误："+i);        }        if(length == 0){            throw new RuntimeException("顺序表为空，不能删除元素");        }        for(int j=i;j
       
      
     

 

单链表表示的实现：

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; } //尾添加 public boolean addToLast(E e) { if(size == 0){ header.e = e; }else{ Node
              
                newnode = new Node
               
                (e); //根据需要添加的内容封装为节点 Node
                
                  last = getNode(size); //得到最后一个节点 last.next = newnode; } size ++; return true; } //头添加 public boolean addTofirst(E e) { if(size == 0){ header.e = e; }else{ Node
                 
                   newnode = new Node
                  
                   (e); //根据需要添加的内容封装为节点 newnode.next = header.next; header.next = newnode; } size ++; return true; } //插入到第index个的位置 public boolean insert(int index, E e) { Node
                   
                     newnode = new Node
                    
                     (e); //根据需要添加的内容封装为节点 Node
                     
                       cnode = getNode(index-1); //得到第index-1个节点 newnode.next = cnode.next; cnode.next = newnode; size++; return true; } //删除第index个节点 public boolean delete(int index) { Node
                      
                        prinode = getNode(index-1); //得到被删除的节点的前一个节点 Node
                       
                         delnode = prinode.next; //得到被删除的节点 prinode.next = delnode.next; size --; return true; } //判空 public boolean isEmpty() { return size==0 ? true : false; } public void destroyList() { header = null; size = 0; } //输出 public String toString(){ StringBuilder s = new StringBuilder("["); Node
                        
                          temp = header; for(int i=0; i < size;i++){ s.append(temp.e.toString()+" "); temp = temp.next; } s.append("]"); return s.toString(); }}
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

双链表表示的实现

class TNode
     
      {    E e;    TNode
      
        prior, next;        TNode(){}    TNode(E e){        this.e = e;        prior = null;        next = null;    }}public class DoubleLinkedList
       
         {    private TNode
        
          header = null;   //头结点    int size=0;     //链表大小        public DoubleLinkedList(){        this.header = new TNode
         
          ();    }        //尾添加    public boolean addToLast(E e) {        if(size == 0){            header.e = e;        }else{            TNode
          
            TNode = new TNode
           
            (e); //根据需要添加的内容封装为节点 TNode
            
              last = getNode(size); //得到最后一个节点 last.next = TNode; TNode.prior=last; } size ++; return true; } //找到第index个位置的节点 public TNode
             
               getNode(int index){ if(index > size || index < 0){ throw new RuntimeException("索引值有错：" + index); } TNode
              
                temp = new TNode
               
                (); temp = header; int count =1; while(count != index){ temp = temp.next; count ++; } return temp; } //插入到第index个的位置 public boolean insert(int index,E e){ TNode
                
                  TNode = new TNode
                 
                  (e); TNode
                  
                    cnode = getNode(index-1); //找到第index-1个位置的节点 TNode.next=cnode.next; TNode.prior = cnode; cnode.next.prior = TNode; cnode.next = TNode; size++; return true; } //删除第index个节点 public boolean delete(int index){ TNode
                   
                     delnode = getNode(index); delnode.prior.next=delnode.next; delnode.next.prior= delnode.prior; size--; return true; }}