一.线性表
什么是线性表，字面意思，就是可以连成一条线的表，这里的线可以是物理上的一条线，也可以是逻辑上的一条线
物理上的一条线就是类似于数组，即它在内存上是有一块连续的空间，叫做顺序表，如下：
还有一种是逻辑上的一条线，就是再内存中不一定是一段连续的空间，但根据上一个内存可以找到下一块内存，叫做链表，如下：
二.顺序表
今天我们要谈到的ArrayList就是顺序表，也就是说，此ArrayList类的底层是一个数组，它是用数组来组织对象的
三.ArrayList简介
1.它在Java.util包底下，使用时需要导入包
2.它是一个普通的类，实现了List接口；
3.而且他是一个泛型类，要存放什么类型的数据，就要对应传入其包装类，同时在使用时要创建对象
4.它实现了Cloneable接口，表示它可以被克隆；实现了RandomAccess接口，表示可以被随机访问
5.与Vector不同，它不是线程安全的，在单线程情况下可以使用，而在多线程情况下，一般不使用ArrayList
6.它的底层是一个数组，并且可以动态扩容，是可以动态扩容的顺序表
四.ArrayList的使用
1.ArrayList的构造
首先要注意以上这几个成员变量
DEFAULT_CAPACITY是一个默认初始容量
后面这三个数组，前俩个是static final修饰的，属于类独有的，且不可修改（注意，这里的不可修改，只是不可以修改指向，即在内存中的地址，但里面的数可以改）所以内存上独有一份，注意，这俩个数组都没有用到new这个关键字，而且大括号里也没有存放数据，这等同于并没有分配内存！！！
看绿色的英文：We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.指的是，这俩个数组要区分开来，以便知道要添加第一个元素时要扩容多少
最后一个数组elementData是最终存放数据的数组，它暂时也没有指向
看英文，表示这时存储数组列表元素的缓冲区。数组列表的容量为这个数组缓冲区的长度。当添加第一个元素时，elementData=DEFAULT_EMPTY_ELEMENTDATA的空数组将被扩展为DEFAULT_CAPACITY即默认长度
(1).无参构造方法
绿色英文：构造一个空表，并让其初始容量为10
但看代码发现它的初始容量还是0.这是因为，将在第一个添加元素时进行扩容
(2).有参构造方法一
构造一个带有指定容量的数组。
如果传入的初始容量为0，就直接指向那个共有的空数组EMPTY_ELEMENTDATA（这里就和刚才无参的构造方法区分开来了，对于无参构造方法，数组容量初始是0，此个有参构造方法初始容量也是0，但在添加第一个元素时，代码会进行检验，看它们都指向了哪个空数组，如果指向了DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那就会将其扩容为10，如果指向了ELEMPTY_ELEMENTDATA，那就另当别论。）
如果传入的初始容量大于0，那么就会开辟一个新数组，并制定好容量。
(3).有参构造方法二
首先看参数，它必须是一个实现了Collection接口的类，其次，里面传入的数据类型的包装类是继承了E的，E是什么？E是我们的ArrayList里面存放的数据类型的包装类。
然后，c.toArray()可能返回的不是Object类型（这个我会专门写一篇博客来解释），所以可能会进入到第二个if中。而要是初始时c中没有元素，就会直接指向ELEMENTDATA。
2.添加元素
(1).末尾添加元素
先是确定初始容量，第一次添加时可能会涉及到扩容机制（因为如果用了无参构造方法，默认初始容量为10，但还没有分配内存），以第一次添加为例，此时的size就是0，所以传入ensureCapacityInternal的参数就是1：
此时又进入另一个方法，minCapacity是1
这里就把调用哪个构造方法给区分开来了，如果调用了无参构造方法，就会进入if，然后minCapacity就会更新为10，反之直接返回1
explicit表示明确的，就是确定具体的容量。如果minCapacity大于elementData的长度，就会扩容。对于使用了无参构造和使用了传入容量大于1的构造方法的，就会进入if语句，而对于使用了无参构造，以及传入的容量为0或1的，就不会会进入grow方法
对于使用了无参构造的，oldCapacity是0，newCapacity是oldCapacity的1.5倍，这里还是0.进入第一个if之后，newCapacity更新为10！！，然后扩容为10
对于使用了有参构造的，newCapacity更新为1，然后扩容
original就是elementData，newlength就是10或1。newType就是elementData的类型
先看使用了无参构造的，如果elementData是object类型的，就会创建一个新的object数组，长度是10，如果不是object类型，就先更新成object类型，最后将elementData中的元素拷贝到新数组，并且返回
而使用了有参构造的（能进入这一步的，要么是使用了有参构造一且传入的参数为0，要么是有参构造二中掺入一个没有元素的集合，它们的newlength都是1），newlength就是1.
总结：
1.elementData必须是object类，如果不是，就要copy成object，因为由上述代码可看出，所有的操作都是基于object类进行的，因为会涉及到System.arraycopy:
它的参数类型就是object！！！
2.elementData最终不会指向我们最初提到的那俩个static native修饰的数组，由上述add扩容即使可知，只要用到了copyOf方法，就会创建新的对象
3.ArrayList的扩容机制：是1.5倍扩容
(2).指定位置添加元素
(3).将其他集合中的元素添加到ArrayList中
第二个是插入到指定位置
3.删除元素
这个是删除指定下标的元素，注意将末尾元素置为null
这个是删除具体对象，注意用到了对象的比较，equals方法
都调用了fastRemove方法，这个方法相比于remove方法来说，少了一步边界检查，所以叫快速删除
4.clone方法
调用了object类的克隆方法，它的返回值是object，所以要进行向下转型。注意，只进行这一步是不够的，这只是浅拷贝，只进行到了如下图这一步：
它的确是有了一个新的v并且在堆上产生了一个新的对象，但由于调用了copy，所以将原来的数据就元丰不动的拷贝到了新对象上，所以旧的和新的ArrayList对象都指向了0x67这个数组，只是浅拷贝，所以要再进行源码中的数组拷贝，将v对应的对象中的数组在新地址再拷贝一份。
5.ArrayList的遍历
法一：
法二：
法三，用迭代器：
这是源码中生成迭代器的代码，其中ListIterator是一个类，Iterator是一个接口，用哪个都可以
源码中还有一个如下的代码：
这个是可以指定从哪里开始遍历
6.其他方法
subList，返回顺序表中的一部分
还有一些get，set，等方法，看源码就可以看懂
五.ArrayList存在的问题
1.在指定下标添加或删除元素，不仅要遍历数组，还得将剩余数据前移或后移，这导致时间复杂度为O(N)。
2.扩容不是在原始数组上进行，而是申请新的空间，然后拷贝旧数据，最后释放就空间，这样的操作会有很大的资源消耗
3.可能存在空间浪费现象，比如数组长度为100，存放满了，还想再放一个数据，就要1.5倍扩容，此时又多了50个空间，但只用了1个，剩下的就浪费了。
