1. 动态数组-ArrayList

区别于array，数组为基本的数据结构为定死的. ArrayList 则是动态扩容的数组相当于C++或Python的List.

1.1 数组的底层原理

内存管理器在你申请一个新数组的时候开辟了一段新的内存地址:
注意一个int类型为32位, 一个内存地址只能存储8位, 因此数组中的一个数据对应的是一个地址块地址块中包含4个连续的地址, 地址是32位的. 两个相邻的数据相差一个地址块即32位, 因此数组指针的单位为4Bytes-每次加一相当于加了32bits.

1.2动态数组的特性

1.21 数组对元素的访问

通过指针可以迅速访问到任何一个元素, 这时查询只进行一次复杂度是常数O(1).

1.22 数组的增添

数组增添操作的复杂度

数组增加元素都涉及到插入位置之下元素的平移, 因此复杂度与插入位置成线性关系所以为线性复杂度O(n).

接下来会深究源码:

a. 向末尾添加-Public boolean add(E e){}

上图是调用addFunction的时候实际的Function的访问顺序
上述代码是在末尾添加, 若数组容量不够会复制扩容, 再在数组末尾加上该元素. 注意其中的ensureCapacityInternal(size+1) 这是用来确保数组当前容量够用的函数.

上述代码中的elementData是ArrayList类中数组(基础数据类型)存储的当前动态数组内容.
从这里我们可以看出动态数组的底层实现还是数组只不过用了复制等方法封装了函数扩容.
这一部分中的minCapacity其实就是上面传进来的size+1也很形象啊满足需求所需的最小值.
这一步进行了数组是否为空的判断为空不用想了一定不够用, 因此当数组为空时将输入的size+1 与 类里定义的最小容量10作比较取最大值(如果size+1<10 也取10因为这是动态数组的最小值. 这一步的目的是明确最小所需容量到底是多少引入了是否为空的判断. 揭晓来进入确保明确的容量, 很明显当明确的容量值得到后就该确保有这么多了.

这一步的功能十分简单就是判断上面得到的明确的size是否满足, 注意此时minSize有两种可能性

1. 此时minSize=10, 这是elementData=[]的情况, 因为此情况下size+1=0肯定小于10.
2. 此时minSize=size+1, 这是elementData!=[]的情况这时肯定容量至少为10minSize>10.
   接下来进入了ArrayList的核心方法-grow()-实现动态扩容的方法.
   
   其中第二句新的容量等于旧的容量的1.5倍, >>1代表右移1位(2进制)比如旧容量为8就是1000那么右移以为就变成0100就是4, 所以这一步其实是新容量=旧容量+0.5旧容量. 接下来再进行判断, 如果说还是不够就不费事了就直接让新容量=最小所需容量(注意这里不一定是10或者size+1, 很有可能是直接调用了这个方法. 接下来在判断新容量和最大容量的关系, 最大容量的定义是最大整数值-4. 如果新的容量大于了最大容量则返回能给的最大值. 接下来这一步很重要就是把旧的数组拷贝到新的容量为newCapacity的数组里(基本类型).
   
   这个便是返回最大容量的函数了, 按理说传到这步不可能再等0了可能是为了防止直接被调用出错, 又加入了一个minSize和0的判断, 若小于0直接扔出异常, 判断minCapacity是否大于最大容量, 大于返回整数的最大值, 否则返回定义好的最大容量
   
   注意这里的minCapacity是上一步传进来的最小容量而不是新的容量, 因为新的容量扩展为两倍大于最大容量, 理所当然应该传进来最小的满足容量. 换句话说grow() 倾向于将容量扩充为两倍当扩充为两倍后大于了最大容量是不是应该把最小满足条件传过去判断能给的最大值是多少? 因为很有可能最小满足容量不大于最大值呀. 但是这个函数的处理有些问题如果可能的话应该尽可能地返回最小满足容量.

b. 按指针位置插入- Public void add(int index, E element){}

上述代码是在指定位置插入元素, 并且将后续元素后移, 本质是通过数组的复制实现的.
第一位为原始的数组, 第三位是最终复制后得到的数组, 复制的内容是由第2位和第5位决定的, 第二位决定的是复制的起始位置, 第5位确定的是复制的从复制起点开始的长度, 第四位决定的是复制的内容在最后得到的数组中的位置.

1.23 数组的删除

和