1.说说ArrayList
1.基本原理
ArrayList，原理就是底层基于数组来实现。
01.基本原理：
这个数组扩容+元素拷贝的过程，相对来说会慢一些
02.缺点：
01：不要频繁的往arralist里面去塞数据，导致他频繁的数组扩容，避免扩容的时候较差的性能影响了系统的运行。
02： 数组来实现，数组你要是往数组的中间加一个元素，是不是要把数组中那个新增元素后面的元素全部往后面挪动一位，所以说，如果你是往ArrayList中间插入一个元素，或者随机删除某个元素，性能比较差，会导致他后面的大量的元素挪动一个位置。
03.优点：
基于数组来实现，非常适合随机读，你可以随机的去读数组中的某个元素。
04.常用场景：
05.场景示例：
2.源码剖析
01.核心方法的剖析
咱们来启动一个demo工程，在里面写写集合的代码，跟进去看看各种集合的实现原理，直接可以看JDK底层的源码。
(1).示例代码：
public class ArrayListDemo {
public static void main(String[] args) {
ArrayList<String> sayLove =new ArrayList<String>();
sayLove.add("老婆，早上好");
sayLove.add("老婆，下午好");
sayLove.add("老婆，下班啦，我去找你");
sayLove.set(0,"老婆，早上好,我们一起吃早饭吧");
sayLove.add(2,"老婆，注意坐姿，不要久坐哦");
}
}
(2).构造函数分析：
默认的构造函数，直接初始化一个ArrayList实例的话，会将内部的数组做成一个默认的空数组，{}，Object[]，他有一个默认的初始化的数组的大小的数值，是10，也就是我们可以认为他默认的数组初始化的大小就是只有10个元素。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
private static final int DEFAULT_CAPACITY = 10;//初始容量 10
注意点：
(3).add(E)方法
分析如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
#2 ensureCapacityInternal(size + 1);：判断一下当前的数组容量是不是满了，如果满了会进行扩容；
if (minCapacity - elementData.length > 0)
grow(minCapacity);
1).第一次进入这个方法时，minCapacity=10，默认值，而此时底层还是个空数组，自然会进行数组的扩容。扩容代码如下：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
通过计算，确认本次数组增加的容量就是默认大小10，然后通过Arrays.copyOf进行数组的数据拷贝和创建新数组。
#3 elementData[size++] = e;，就是将添加数据数据放到index=0的位置上，并且size+1；
2).然后就返回添加成功了。
数组的变化：
size=0，elementData={}变成了size=1，elementData=["老婆，早上好"]
依次执行三次,就完成今天的sayLove日常了。
(4).set(index,E)方法
sayLove.set(0,"老婆，早上好,我们一起吃早饭吧");
分析如下：
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
#2 rangeCheck(index);：还记得我们那些年学Java的青葱岁月吗？都得喊一嗓子：角标越界，错误就在这里了，熟悉的异常，值得的青葱岁月。
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
#3 E oldValue = elementData(index);：操作很简单，返回原来位置上的值，将新值插入想插入的位置，并返回旧值。
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
(5).add(index,E)方法
sayLove.add(2,"老婆，注意坐姿，不要久坐哦");
分析如下：
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
#2,#4,还是熟悉的检查角标是否越界以及检查容量是否已满。
#5,调用native方法System.arraycopy，进行数组中元素的移位，参数如下所示：
index=2,size=3;
System.arraycopy(elementData, 新增的角标位=2, elementData, 往后移动的起始角标位=3,
要往后移动的个数=1);
#5,#6,插入新值到指定位置，size+1。
完成指定位置插入数据的操作。
(6).remove(index)方法
sayLove.remove(2);//加班，所以，不能去找媳妇了。撤回 “老婆，下班啦，我去找你” 这句话。
分析如下：
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
#7 int numMoved = size - index - 1;：numoved=4-2-1=1,要移动的个数，当前大于0，调用native方法，进行数组元素移动，System.arraycopy(elementData, 3, elementData, 2,1);,从当前数组的index=3位置，共一个元素，从index=2位置开始拷贝。
说到底，就是删除位置后的所有元素都往前移位，然后将最后位置上的元素设置为null。so easy。
2.谈谈LinkedList
1.基本原理
底层是基于链表来实现的。
01.基本原理：
02.优点：
03.缺点：
04.常用场景：
05.场景示例：
2.源码剖析
01.插入元素
在尾部插入元素、在头部插入元素、在中间插入元素
add()，默认就是在队列的尾部插入一个元素，在那个双向链表的尾部插入一个元素
add(index, element)，是在队列的中间插入一个元素
addFirst()，在队列的头部插入一个元素
addLast()，跟add()方法是一样的，也是在尾部插入一个元素
(1).示例代码：
public static void main(String[] args) {
LinkedList<String> housework=new LinkedList<String>();
housework.add("洗菜");
housework.add("切肉");
housework.add("炒菜");
housework.add(1,"给老婆倒杯水");
}
(2).add(E)方法
分析如下：
public boolean add(E e) {
linkLast(e);
return true;
}
#2 linkLast(e);：将元素直接插入到队尾代码如下：
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
1). #2~#4： 第一次last肯定是null，创建了一个Node节点，对象结构Node<preNode,元素,next节点>；并且该节点赋值给了last变量。
2). #5~#8： 第一次last节点是null，所以first节点也被赋值成创建的node节点。而如果是第二次进行add操作的话，就是会将新的Node节点挂在到前一个Node节点的next节点上去。
3).size+1，操作成功。
(3).add(index,E)方法
housework.add(1,"给老婆倒杯水");
分析如下：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
#2 checkPositionIndex(index);：对于指定位置的插入数据，我们都是需要进行角标是否越界的检查的；
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
#4-#7：如果正好是最后一个位置，就直接插入到队尾；
如果不是，就要进行指定位置的插入，这里走的是这个分支。
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
1).先根据index获取到之前位置的node；
2).#3~#5: 1. 新创建一个Node，新Node的pre节点设置为原Node节点的pre节点，next节点设置为原node节点。
- 将原来的Node节点的pre节点设置为新Node节点。
2).#6~#9：如果原节点的pre节点是null，就把新Node节点设置为first节点；
否则就是将原Node节点的next节点设置为新创建Node节点。
3).size+1，然后就返回添加成功了。
02.获取元素
(1).get(index)方法
示例代码：
public static void main(String[] args) {
LinkedList<String> loveStory=new LinkedList<String>();
loveStory.add("看电影");
loveStory.add("去野餐");
loveStory.add("摩天轮");
loveStory.add("去海边");
loveStory.get(2);
}
我们来分析这一行代码：
loveStory.get(2);
分析如下：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
#2 checkElementIndex;：角标是否越界的检查。
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
#3 node(index);：这里就极为关键了，LinkedList底层是如何遍历查找指定位置的元素呢？来看如下分析：
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
#4~#6：
1).size/2,取了中间数，然后判断我们要找的位置是在中间数的前部分还是后部分。
如果是前半部分就从first节点开始往后查找，
如果是后半部分，就从last节点开始往前查找，有点二分法查找的感觉。
2).我们这里index=2, 2>2不成立，走else分支，然后，我们可以看到他通过一个for循环进行遍历，从最后一个节点开始，每次都查找Node节点的prev节点，直到index+1的位置时，就跳出循环了，而index+1节点的prev节点不正是我们要获取的index节点么？完美！
03.删除元素
(1).get(index)方法
示例代码：
public static void main(String[] args) {
LinkedList<String> loveStory=new LinkedList<String>();
loveStory.add("看电影");
loveStory.add("去野餐");
loveStory.add("摩天轮");
loveStory.add("惹老婆生气");
loveStory.add("去海边");
loveStory.get(2);
}
我们来分析这一行代码：
loveStory.remove(2);
分析如下：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
#2 checkElementIndex;：角标是否越界的检查。
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
#3 unlink(node(index));：先遍历找到index对应的Node节点，然后进行删除工作。
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
#3~#5：获取index对应的Node节点的prev节点和next节点；
#7~#12：如果prev节点为null，就把Node节点的next节点设置为first节点；
否则就将prev节点的next节点设置为Node节点的next节点。
#14~#19：如果next节点为null，就把Node节点的prev节点设置为last节点；
否则就将next节点的prev节点设置为Node节点的prev节点。
#21~#24：将node节点的值设置为null，size-1，最终返回原来Node的元素值。
3).对比总结
最后谢谢大家阅读，有不足之处欢迎指出。