我们先了解一下数组Array的概念
数组是一种顺序储存的线性表，所有的元素的内容地址都是连续的
数组有个致命缺点，就是无法动态的修改容量
而 ArrayList 的底层是基于数组实现的，其容量大小可动态变化
1.是否保证线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全
2.底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构
3.是否支持快速随机访问：** LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
4.内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间浪费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。
这两个类都实现了List接口，他们都是有序集合，即存储在这两个集合中的元素的位置都是有顺序的
（1）同步性：
Vector是线程安全的，它的方法之间是线程同步的。ArrayList是线程序不安全的，它的方法之间是线程不同步的。在不考虑线程安全的情况下，使用ArrayList，因为它效率高；如果考虑线程安全的安全，使用Vector
（2）数据增长：
ArrayList与Vector都有一个初始的容量大小，10。
当添加元素超过集合的长度时，会对原数组进行扩容
Vector扩容的长度为原来数组 ✖ 2 ，ArrayList扩容的长度为原来数组 ✖ 1.5
当ArrayList调用 add() 方法时，当 size == elementData.length 的时候，会调用 grow() 方法对ArrayList进行扩容
// 数组扩容方法 // minCapacity = size + 1 private int newCapacity(int minCapacity) { // 当前数组长度 int oldCapacity = elementData.length; // 新的数组容量 = 旧数组长度 + 旧数组长度 / 2 // oldCapacity = 10 oldCapacity >> 1 --- 5 // 例如10的二进制为 : 0000 1010 >> 1 -----> 0000 0101 = 5 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity <= 0) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 如果一开始没有定义初始容量这时newCapacity=0,返回默认容量10 // 可以得出当无参new 一个ArrayList()时候，这个ArrayList()为空集合，size为0 return Math.max(DEFAULT_CAPACITY, minCapacity); if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return minCapacity; } return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity // 这里返回的长度为原数组的1.5倍 : hugeCapacity(minCapacity); }
由此可得出结论
通过无参构造器实例化的ArrayList初始容量为 0
在首次调用add()方法之后，返回一个容量为10的数组，后面每次扩容后新数组的长度为原数组长度的 1.5 倍
可以简单理解为：首次扩容为10 ，后面每次扩容为原数组的1.5倍
解决方案：通过有参构造器 ，提前设置好容量， 空间换时间
public static void main(String[] args) { // 创建集合对象 ArrayList<String> list = new ArrayList<>(); // 添加元素 list.add("A"); list.add("B"); list.add("C"); Long startTime = System.currentTimeMillis(); // 需求：需要添加100W跳数据 for (int i = 0; i < 1000000; i++) { list.add(i+""); } Long endTime = System.currentTimeMillis(); // 添加100W条数据用时：129 System.out.println("添加100W条数据用时：" + (endTime - startTime)); // ArrayList(initialCapacity) 通过有参构造器指定ArrayList集合容量 ArrayList<String> list1 = new ArrayList<>(1000000); startTime = System.currentTimeMillis(); for (int i = 0; i < 1000000; i++) { list1.add(i+""); } endTime = System.currentTimeMillis(); // 提前声明数组长度后,添加100W条数据用时：51 System.out.println("提前声明数组长度后,添加100W条数据用时：" + (endTime - startTime)); }不一定
先看下ArrayList删除功能的源码 public E remove(int index) { // 范围校验 Objects.checkIndex(index, size); // 将源数组赋给es final Object[] es = elementData; // 将index对应的元素赋值给 oldValue E oldValue = (E) es[index]; // 调用fastRemove方法 fastRemove(es, index); return oldValue; } private void fastRemove(Object[] es, int i) { // 修改次数+1 modCount++; // newSize新数组的长度 final int newSize; if ((newSize = size - 1) > i) // 如果新数组长度newSize 大于 源数组size所要删除元素的索引 // 使用arraycopy方法进行拷贝 //注意 ：这里源数组跟目标数组都为es,说明没有创建新数组 System.arraycopy(es, i + 1, es, i, newSize - i); // 将源数组最后一个元素设置为null，今早让垃圾回收机制对其进行回收 es[size = newSize] = null; }通过源码分析，我们得出一个结论
ArrayList删除元素的时候，并没有创建一个新的数组
而是把数组中要删除的元素从后往前给覆盖了，然后把最后一个元素设为值null
在对比一下LinkedList删除功能的源码 public E remove(int index) { // 校验索引 checkElementIndex(index); /* if(return index >= 0 && index < size){ throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } */ return unlink(node(index)); } 看下unlink()方法里的node()方法 Node<E> node(int index) { // 如果删除索引index小于LinkedList集合长度的一半 if (index < (size >> 1)) { // 如果小于，那么把第一个节点赋值给x Node<E> x = first; // 从头开始往后找 for (int i = 0; i < index; i++) x = x.next; // 返回找到的节点 return x; } else { // 把最后一个节点赋值给x Node<E> x = last; // 从最后一个位置往前找 for (int i = size - 1; i > index; i--) x = x.prev; // 返回找到的节点 return x; } }根据源码得出结论，LinkedList每次删除元素的时候都要逐个检索元素
如果LinkedList容量很大，删除的元素索引处于中间部位
这时LinkedList删除效率并不见的比ArrayList效率快
1. 使用clone()方法
这里是浅拷贝操作，不是添加操作 public Object clone() { try { // 把源集合中的成员信息拷贝到 V ArrayList<?> v = (ArrayList<?>) super.clone(); // 把源集合中的数组元素拷贝到v的数组元素中 v.elementData = Arrays.copyOf(elementData, size); // 把v中的修改次数变量重置为0 v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }2. 使用ArrayList构造方法
这里回顾之前ArrayList的有参构造方法 public ArrayList(Collection<? extends E> c) { // ArrayList的toArray()返回结果是object类型的数组 elementData = c.toArray(); if ((size = elementData.length) != 0) { // 当c.toArray转换的数组类型不是object[]类型时 // 即c可能为其他类型的toArray()方法返回的不是object类型 if (elementData.getClass() != Object[].class) // 这时就使用Arrays.copyOf(original,newLength,newType)方法 // 通过Arrays.copyOf()方法把 c 转换为object类型的数组 (对应ArrayList的数组类型) // @param original 要复制的数组 // @param newLength 新数组的长度 // @param newType 新数组的类型 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 否则弄个空的数组给他 this.elementData = EMPTY_ELEMENTDATA; } }3. 使用addAll用法
这里不是拷贝操作，而是将新集合添加到ArrayList集合的后面 public boolean addAll(Collection<? extends E> c) { // 把传入的集合转换为数组 给Object类型的数组elementData Object[] a = c.toArray(); modCount++; int numNew = a.length; if (numNew == 0) return false; Object[] elementData; final int s; // 这里判断，如果新集合长度加上源集合的元素个数 大于源集合容量时，进行grow()扩容 if (numNew > (elementData = this.elementData).length - (s = size)) elementData = grow(s + numNew); // 调用 System.arraycopy ()方法进行数组的拷贝 System.arraycopy(a, 0, elementData, s, numNew); size = s + numNew; return true; }会初始化数组大小
但是ArrayList大小没有变，即 size = 0因为在ArrayList的有参构造函数中，没有把int initialCapacity赋值给size
ArrayList中获得元素个数 size()方法 这里我们猜想一下，当调用set，remove方法时，肯定会有索引校验的方法如果这个时候调用set()方法，就会出现索引越界异常
这是Java Bug里面的一个经典问题了，大家仔细品读一下。
可能大家会觉得 那也只能硬啃，慢慢品 ArrayList在面试里面问的频率没HashMap，ConcurrentHashMap高，但是也有一定概率问到的，还是那句话，小心使得万年船
