ArrayList

构造方法：

• 默认构造方法：ArrayList()
  1、将空的Object数组赋值给elementData
• 设定集合大小构造方法：ArrayList(int initialCapacity)
  1、判断initialCapacity < 0, 抛异常，
  2、initialCapacity > 0 ,给elementData创建对应大小的Object数组
  3、initialCapacity == 0，给elementData赋值一个空的Object数组
• 传入一个集合构造方法：ArrayList(Collection<? extends E> c)
  1、先将传入的Collection对象转成数组，赋值给elementData
  2、判断elementData.length == 0, 给elementData赋值空数组
  3、判断elementData.length != 0, 接着会重新copy一个与1操作相同的数组

add(E e)添加元素

1、首先拿到当前elementData的数组大小记为size
2、接着，如果elementData数组为空数组，则会将size + 1 与 默认大小DEFAULT_CAPACITY = 10 取最大值，如果里面存有元素，则不会进行比较后赋值

3、只有当数组满载情况下会触发扩容算法 (elementData数组有元素时minCapacity = elementData.length + 1，elementData为空数组时，minCapacity = 10)

4、扩充集合容器算法：拿到当前elementData数组大小通过右移1位位运算后 + elementData数组大小，记为newCapacity(新容器容量)。如果newCapacity < minCapacity(默认容量 或者 当前elementData数组大小 + 1) 会将 minCapacity 赋值给 newCapacity。容器的最大容量为Integer.MAX_VALUE - 8，如果预设定的容量 > 最大值，则强制设为最大值。定好容器容量后copy一个新容量的数组并将之前老的元素存储到新数组中。

5、容器扩容完后，进行添加元素到新数组中

add(int index , E element)

1、首先会检查插入的角标是否合法，如果角标 > 数组长度 或者 角标 < 0，都会报角标越界异常
2、同样扩容规则和add(E e)的扩容规则一致
3、通过System.arraycopy(Object[] src, int srcPos, Object[] dest, int destPos, int length)，方法进行拷贝,srcPos从指定原数组位置开始取元素，destPos从目标数组位置开始存元素，length取的元素长度，之后将得到新数组后，会预留指定元素位置用于插入新值

remove(int index)

1、先检查下标合法性
2、取出移除指定位置的元素，用于返回给客户端
3、同样移除操作也是借助于System.arraycopy()方法进行复制操作
4、操作完后，将数组大小进行–size，然后把最后一个元素置空等待GC回收内存

remove(Object o)

1、该方法与remove(int index)方法移除的逻辑大致相同
2、根据指定的object去移除元素，是先根据指定的object找到在数组中的下标，之后再通过下标去移除元素

LinkedList

构造方法

• 默认构造方法LinkedList()：空实现
• 传参构造方法LinkedList(Collection<? extends E> c)：会调用默认构造方法，然后在调用addAll()将c集合添加进去

LinkedList.add(E e)方法

1、内部调用了LinkedList.linkLast(E e)
2、跟进linkLast(E e)：
----a、定义一个节点l(作用类似交换2个变量的temp变量)用于记录last节点指向的节点，可进行后面newNode(新插入元素节点)插入位置的确定。同时把l节点指向last节点(作用可在步骤f查看)
----b、接着创建一个newNode节点，并为newNode指定前一个节点为l。接着把last节点单指向newNode节点(作用可在步骤e、f查看)
----c、如果当前集合是空的，那么直接将first节点指向newNode节点。
----d、如果在插入之前集合存在元素，那么步骤b已经确定了newNode节点的前一个节点为l，接下来设置l的下一个节点是newNode节点，这样就确定了l节点和newNode节点的位置关系。
----e、由于在步骤b结束后，会重新让last节点指向newNode节点，那么在步骤d结束后，确定了newNode节点位置，于此同时last的位置也已确定。
----f、l节点位置的确定：在该方法一开始就让l节点指向上一次添加到集合中元素的节点位置及last节点，而每次添加元素时，last节点是位置已经确定。

3、例：第一次插入元素，那么last节点指向newNode节点，然后让first指向newNode节点，即newNode节点位置已经确定好同时last节点指向newNode节点，所以last节点也确定位置。接着插入第二个元素时，last节点指向第一个已经确定的位置，并让l节点指向last，致使l节点的位置也确定，通过步骤d操作就确定了newNode节点的位置，后面插入元素以此类推

4、添加元素的流程图：

LinkedList.addAll(Collection<? extends E> c)

1、该方法内部调用addAll(int index,Collection<? extends E> c)
2、继续跟进：如果当前集合不为空时，调用了node(int index)，其内部是进行二分法查找(由此发现，LinkedList查找元素性能低)，找到指定位置的节点，目的是在后面进行设置指定节点与插入元素的一个位置关系。

3、确定了插入元素节点的前一个节点，然后进行遍历插入的集合元素，并且对元素节点建立链关系(建立链关系与add(E e)方式雷同)

LinkedList.remove(int index)

1、删除原理：同样是通过调用node(int index)进行二分法查找指定位置的元素节点，然后开始对指定的节点进行断链、置null，然后让分开的两段链相互链接形成一个整链，最后使其成为孤立的null对象，最后由GC回收。
2、在remove(int index)中调用了unlink(Node<E> x)，该方法是做了断链、置空、连接链操作

总结

• ArrayList：底层是数组实现的，默认容器容量为10，动态扩容算法是当数组长度达最大时，继续添加元素，扩大容量是以原数组的容量的1.5倍扩大创建一个新的数组，然后将原有的元素复制到新数组中。删除元素，从需要删除的元素位置开始，遍历数组，将后面的元素从删除位置开始重新赋值，将数组末尾元素置空，让GC回收，来达到删除目的。由此可见，ArrayList集合在增删效率上比较差，由于底层数组，查找可直接通过索引去取，所以查找会逊色一点。
• LinkedList：底层是链表数据结构，既然是链表，那么集合不存在扩容一说，插入和删除元素只需要断链、再合链即可。如果是插入/删除指定位置，那么首先需要通过二分法进行查找指定位置的元素，然后再对其进行锻炼、再合链等操作。由此可见LinkedList集合在查找性能上会较低，在增删(非指定位置)效率上会逊色一点。

补充：
1、<< 左移1位 => 原数 * 2，左移2位 => 原数 * 2 * 2…以此类推（左移 右边添0）
2、>> 右移1位 => 原数 / 2 取整，右移2位 => 原数 / 2 / 2… 以此类推（右移 左边添0）