数据结构之 线性表 （JAVA语言描述）

线性表是一种线性结构，它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中，除了头尾元素，每个元素都有且只有一个直接前驱，有且只有一个直接后继，而序列头元素没有直接前驱，序列尾元素没有直接后继。
————————————————————————————————————————
我们可以使用线性存储结构来创建一个线性表或着使用链式存储结构
这里使用顺序存储结构来存储线性表
在创建线性表之前我们首先要了解线性表的一些方法

    //添加元素
    public void  add(E element);
    //指定角标处添加
    public  void add( int index, E element);
    //删除元素
    public  void  remove(E element);
    //删除角标元素并返回
    public E remove(int index);
    //获取指定角标处元素
    public E get(int index);
    //修改
    public  E set(int index,E element);
    //获取线性表元素个数
    public  int size();
    //查看元素首次出现位置
    public  int indexOf(E element);
    //判断是否包含元素
    public boolean contains(E element);
    //判断线性表是否为空
    public boolean isEmpty();
    //清空线性表
    public  void  clear();
    //按照比较器的内容排序
    public  void  sort(Comparator<E> c);
    //获取一个子线性表[fromindex,toindex]。。
    public List<E> subList(int fromIndex, int toIndex);

对于上述的方法可以抽取到接口里
首先创建一个线性表

 //定义一个数组容器 data.length
    private E[] data;
    //定义元素个数 size==0线性表为空 size==date.length 表满
    //size 新元素默认尾部添加时要去的角标
    private int size;
    //定义默认容量
    private  static  int DEFAULT_CAPACITY =10;
    //默认构造函数创建一个线性表
    public  ArrayList(){
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }
    //指定默认容量的构造函数：创建一个指定容量的表
    public ArrayList(int capacity){
        if (capacity<=0) {
            throw new IllegalArgumentException("capacity musc >0");
        }
        DEFAULT_CAPACITY=capacity;
        data = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;
    }
    //指定数组的构造函数：传入一个数组 将该数组封装成为线性表
    public  ArrayList(E[] arr){
            if (arr == null||arr.length==0){
                throw new IllegalArgumentException("CAN NOT NULL");
            }
        data = (E[]) new Object[DEFAULT_CAPACITY];
        for (int i=0;i<arr.length;i++){
            add(arr[i]);
        }
    }

这里使用类来封装线性表的属性和方法

• 线性表的插入操作

 @Override
    public void add(E element) {

        add(size,element);
    }

    @Override
    public void add(int index, E element) {
            if (index<0||index>size){
                throw new IllegalArgumentException("add out");
            }
            //判断表是否满
            if (size==data.length){
                resize(2 * data.length);
            }
            //移动元素
            for(int i=size-1;i>=index;i--){
                data[i+1]=data[i];
            }
            //新元素插入指定位置
            data[index]=element;
            size++;
    }

• 线性表的删除操作

public void remove(E element) {
            int index = indexOf(element);
            if (index!=-1){
                remove(index);
            }
    }

    @Override
    public E remove(int index) {
        if (index<0||index>=size){
            throw new IllegalArgumentException("index out");
        }
        //先保存要删除的值
        E ret =data[index];
        //移动元素
        for (int i= index+1;i<size;i++){
            data[i-1]=data[i];
        }
        size--;
        //什么时候去缩容
        //1.有效元素时是容量的1/4
        //2.当前容量不得小于默认容量
        if (size == data.length/4&&data.length>DEFAULT_CAPACITY){
            resize(data.length/2);
        }
        return ret;
    }

• 获取线性表的指定元素

public E get(int index) {
        if (index<0||index>=size){
            throw new IllegalArgumentException("get index out");
        }
        return data[index];
    }

• 修改线性表的指定元素

 public E set(int index, E element) {
        if (index<0||index>=size){
            throw new IllegalArgumentException("set index out");
        }
        E ret =data[index];
        data[index]=element;
        return ret;
    }

• 线性表中元素排序（使用插入排序）

 public void sort(Comparator<E> c) {
        if (c==null){
            throw new IllegalArgumentException("COMPARATOR NULL");
        }
                for (int i = 1 ; i < size ; i++){
                    E e =data[i];
                    int j =0;
                    for( j = i ; j > 0&&c.compare(data[j-1],e)>0; j--){
                        data[j]=data[j-1];
                    }
                    data[j]=e;
                }
    }

• 截取线性表的一段

public List<E> subList(int fromIndex, int toIndex) {
        if (fromIndex<0||toIndex>=size||fromIndex >toIndex){
            throw new IllegalArgumentException("error");
        }
        ArrayList<E> List =new ArrayList<>();
        for(int i =fromIndex;i<=toIndex;i++){
            List.add(data[i]);
        }
        return List;
    }

关于线性表的扩容/缩容

 private void resize(int newLen){
        E[] newdate = (E[]) new Object[newLen];
        for(int i=0;i<size;i++){
            newdate[i]=data[i];
        }
        data = newdate;
    }