第二天打卡

数组 Array

数组是一种线性表数据结构，它用一组连续的内存空间来存储一组具有相同数据类型的集合。

数组中各个元素的存储是有先后顺序的，它们在内存中按照这个顺序连续存放到一起，内存地址连续。

数组获取元素的时间复杂度为O(1)

一维数组是最常用的数组，其他很多数据结构的变种也都是从一维数组来的。

二维数组及多维数组在开发场景中所用不多，大多在算法及数学计算上。

初始化ArrayList时，如果不指定大小，默认会初始化一个空的元素，这个时候是没有默认长度的，但是当你首次添加元素的时候，就会给初始化的长度，因为所有添加元素操作，都是需要判断容量以及是否扩容的。但随着元素的添加，容量不足时需要扩容操作，这时需要把旧数据迁移到新数组上，数据迁移算是一个比较耗时的操作了。

System.arraycopy

System.arraycopy(elementData,index,elementData,index+1,size - index);
原数组、原数组的起始位置、目标数组、目标数组的起始位置、复制的长度。

ArrayList 的重点离不开对 System.arraycopy 的使用，当添加或者删除操作涉及到数组元素移动或者数组扩容时都会用到System.arraycopy。

就目前我所学到的数据结构中链表和数组都是线性表数据结构，后面需要学习的栈和队列也是线性表数据结构。

数组的元素插入中，头插和中间插入的时间复杂度都为O(n),尾插的时间复杂度需要判断是否需要扩容。数组的元素删除中，头删和中间删除的时间复杂度为O(n),尾删为O(1),而数组的元素获取比较简单，直接从elementData使用索引直接获取即可，时间复杂度为O(1)，正因为搜索元素的便捷，才让ArrayList使用那么广泛。

比较特别的是当数组为空，其插入也算添加操作，时间复杂度为O(1)。而当这个空数组没有预分配容量时即ArrayList默认构造函数，则需要先进行扩容即初始化默认数组（如容量10）再进行插入操作，其扩容操作的时间复杂度为O(n)，但均摊时间复杂度仍为O(1)。

ArrayList 中默认的初始化长度为10，其扩容的范围为当前容量的一半，至于为何选择1.5倍扩容，1.5倍扩容较2倍和1.25倍而言是时间复杂度和空间利用率之间的最优平衡点，这也是Java ArrayList 选择它的根本原因，而其扩容核心在grow()方法上。

经过这两天的打卡学习，可以思考下，LinkedList和ArrayList的插入效率：
在超大数据量的情况下例如1000w数据量，对于头插，可以发现ArrayList需要做大量的位移和复制操作而LinkedList则只需要实例化一个对象，毫无疑问对于大数据的头插操作来说LinkedList完胜。
接下来我们再对比大数据量情况下的尾插操作，ArrayList并不需要做位移拷贝，自然也就不那么耗时了，而LinkedList则需要创建大量的对象，此时ArrayList尾插效果更好些。
最后让我们再对比下中间插入操作，我们都知道LinkedList在插入前是需要遍历寻找位置的，而ArrayList则通过数组索引直接访问，毫无疑问对于中间插入无论是小数据还是大数据ArrayList都是最优解。