线性表

概念：零个或者多个数据元素的有限序列。

特点：除了第一个元素没有前驱结点，最后一个元素没有后继结点外，其它元素有且仅有一个直接前驱和一个直接后继结点。元素的个数必定为有限个。

实现：

定义一个接口：

public interface List {    public void add(int index,Object element);//在指定下标添加元素    public boolean isEmpty();//判断线性表是否为空    public int size();//线性表中当前元素的个数    public Object get(int index);//获得指定下标的元素    public void remove(int index);//删除指定下标的元素}

实现线性表

public class SeqList implements List {    final static int defaultSize=10;//默认长度    int maxSize;//最大长度    int size;//当前元素的个数    Object []array;//存储线性表        //初始化    public SeqList(){        this(defaultSize);    }    public SeqList(int sz){        maxSize=sz;        this.size=0;        array=new Object[sz];    }    @Override    public void add(int index, Object element) {        if(index>size||index<0){            System.out.println("插入下标错误");        }        if(size==maxSize){            System.out.println("线性表已经满了，无法进行插入");        }                System.arraycopy(array, index, array, index+1, size-index);        array[index]=element;        size++;    }    @Override    public boolean isEmpty() {        return size==0;    }    @Override    public int size() {        return size;    }    @Override    public Object get(int index) {        if(index>size||index<0){            System.out.println("获得下标位置出错");        }        if(size==0){            System.out.println("线性表为空");        }        return array[index];    }    @Override    public Object remove(int index) {        if(size==0){            System.out.println("线性表为空");        }        if(index>size-1){            System.out.println("删除下标有误");        }        Object l=array[index];        System.arraycopy(array, index+1, array, index, size-index-1);        size--;        return l;    }    @Override    public void ensureCapacity(int minCapacity) {        // TODO Auto-generated method stub    }}

线性表的查找效率高，但是插入和删除要移动大量元素所以效率比较低。

 

ArrayList简易版实现

import java.util.Arrays;public class MyList implements List{    private int size;    private Object []array;        public MyList(){        this(10);    }        public MyList(int initCapacity) {        super();        if(initCapacity<=0){            throw new IllegalArgumentException("下标不正确！");        }else{            this.array=new Object[initCapacity];        }    }        @Override    public void add(int index, Object element) {        if(index<0||index>size){            throw new IllegalArgumentException("下标不正确！");        }        ensureCapacity(size+1);        System.arraycopy(array, index, array, index, size-index);        array[index]=element;        size++;    }    @Override    public boolean isEmpty() {        return size==0;    }    @Override    public int size() {        return size;    }    @Override    public Object get(int index) {        if(index<0||index
     
      size-1){            System.out.println("删除下标有误");        }        Object l=array[index];        System.arraycopy(array, index+1, array, index, size-index-1);        size--;        return l;    }    @Override    public void ensureCapacity(int minCapacity) {//实现扩容        int oldCapacity=array.length;        if(oldCapacity