1 定义

顺序表，全名顺序存储结构，是线性表的一种。可用于存储逻辑关系为“一对一”的数据。

物理存储结构
顺序表对数据的物理存储结构也有着特殊的要求：
顺序表在存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依此存储起来，存储时，做到数据元素之间不留一丝缝隙。

例如：
使用顺序表存储集合 { 1,3,5,7,9 } ，数据在物理存储上的状态如下图所示：

从图中的存储状态我们可以看出，顺序表存储数据和数组非常相似。实际上，顺序表存储数据使用的就是数组。

2 顺序表的实现

2.1 初始化

在使用顺序表存储数据之前，首先需要申请足够大小的物理空间。申请空间的时候，需要根据外部传进来的指定值大小来设置，或者根据我们的默认值来进行设置，所以，就需要一个属性来保存顺序表的空间大小。另外，我们的表里面，存了多少数据，也需要一个属性来进行保存。

public class ArrayList<E> {
    // 保存数据的数组
    private Object[] datas;
    // 如果用户没有设置长度，则使用默认长度
    private static final int DEFAULT_LENGTH = 16;
    // 顺序表设置的长度（即申请的内存空间的长度）
    private int max_length;
    // 顺序表保存的数据的长度
    private int size;
}

构造函数

    public ArrayList() {
        this(DEFAULT_LENGTH);
    }
    public ArrayList(int initialSize){
        if(initialSize>=0){
            this.max_length = initialSize;
            datas = new Object[initialSize];
        }else{
            throw new IllegalArgumentException("初始化失败，不标准的参数值 initialSize："+initialSize);
        }
    }

2.2 添加元素

在初始化完成后，当然就是向顺序表中添加数据：add()方法的实现。
注意：
在向数组中添加数据之前，首先要判断该数组是否还有剩余空间？
当没有剩余空间后，则需要进行扩容操作

    public boolean add(E e){
        //首先判断是否还有多余的空间来进行数据保存
        if(size==max_length){
            //相等，说明已经没有空间来添加数据
            //则需要扩容
            growMax_length();
        }
        //表示已有空间进行数据添加
        datas[size++] = e;
        return true;
    }

2.3 插入元素

当我们需要在已添加过数据部分中间插入一个元素的时候，所需要执行的工作：
1.判断该数组是否还有剩余空间，没有空间则进行扩容。
2.找到插入位置。
3.将插入位置及后继的元素都向后移动一位。
4.将元素放到插入位置。

2.4 扩容

在添加或者插入元素的时候，当数组空间不够的时候，就需要进行扩容。
注意：
扩容后的大小是否超出了int 类型的最大范围值？

数据结构与算法