手动实现ArrayList

　　public interface List {
  　　  public void insert(int i,Object obj)throws Exception;
  　　  public void delete(int i)throws Exception;
  　　  public Object getData(int i)throws Exception;
  　　  public int size();
  　　  public boolean isEmpty();
　　}
　　顺序表：
　　顺序表插入一个元素需要移动元素的平均次数为n/2次，删除一个元素需要移动元素次数为(n-1)/2，所以顺序表的时间复杂度为O（n）。
　　顺序表的实现如下
　　package com.nishizhen.list;

　　public class SeqList implements List{
    final int defaultSize = 10;
    int maxSize;//顺序表的最大长度
    int size;//线性表当前长度
    Object[] listArray;//存储线性表元素的数组

　　public SeqList(int size){
       initiate(size);
    }

    public SeqList(){
       initiate(defaultSize);
    }

    public void initiate(int sz){
       maxSize = sz;
       size = 0;
       listArray = new Object[sz];
    }

　　public void insert(int i,Object obj)throws Exception{
       if(size == maxSize){
           throw new Exception("顺序表已满，不能再插入元素。");
       }
       if(i<0 || i>maxSize){
           throw new Exception("参数有误。");
       }
       else{
           for(int j=size;j>=i;j--){
              listArray[j] = listArray[j-1];
           }

           listArray[i] = obj;
           size++;
       }
    }

　　public void delete(int i)throws Exception{
       if(size == 0){
           throw new Exception("顺序表为空，无法进行删除元素操作。");
       }

       if(i<0 || i>=size){
           throw new Exception("参数出错。");//数组下标不能小于0或者大于size，因为size及其以后的元素为空。
       }
       else{
           for(int j=size-1;j>=i;j--){
              listArray[j-1] = listArray[j];
           }
           listArray[listArray.length-1] = "";
           size--;
       }
    }

　　public Object getData(int i)throws Exception{
       if(size == 0){
           throw new Exception("顺序表为空，无法返回元素。");
       }

       if(1<0 || i>=size){
           throw new Exception("参数出错。");//数组下标不能小于0或者大于size，因为size及其以后的元素为空。
       }
       else{
           return listArray[i];
       }
    }

　　public int size(){
       return listArray.length;
    }

　　public boolean isEmpty(){
       boolean flag = false;
       if(listArray.length==0){
           flag = true;
       }
       return flag;
    }
}
巴特西

手动实现ArrayList

最新文章

热门文章
