浅谈LinkedList
LinkedList简介
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。
LinkedList相对于ArrayList来说，是可以快速添加，删除元素，ArrayList添加删除元素的话需移动数组元素，可能还需要考虑到扩容数组长度。
LinkedList继承体系
LinkedList源码分析
属性
LinkedList本身的属性比较少，主要有三个，一个是size，表名当前有多少个节点；一个是first代表第一个节点；一个是last代表最后一个节点。
构造方法
- 无参构造
默认构造方法是空的，什么都没做，表示初始化的时候size为0，first和last的节点都为空：
- 带Collection集合的构造
执行逻辑：
1、使用this（）调用默认的无参构造函数。
2、调用addAll（）方法，传入当前的节点个数size，此时size为0，并将collection对象传递进去
3、检查index有没有数组越界的嫌疑
4、将collection转换成数组对象a
5、循环遍历a数组，然后将a数组里面的元素创建成拥有前后连接的节点，然后一个个按照顺序连起来。
6、修改当前的节点个数size的值
7、操作次数modCount自增1.
源码如下：
addAll方法：
add方法
- add(E e)方法
实际上就是调用在尾部添加元素的方法
- add(int index，E element )方法
指定位置往数组链表中添加元素
1、检查添加的位置index 有没有小于等于当前的长度链表size，并且要求大于0
2、如果是index是等于size，那么直接往链表的最后面添加元素，相当于调用add(E e)方法
3、如果index不等于size，则先是索引到处于index位置的元素，然后在index的位置前面添加新增的元素。
get方法
- getFirst方法
返回第一个节点元素
- getLast方法
返回最后一个结点元素
remove方法
- remove()方法
remove()方法本质是调用removeFirst方法，删除第一个结点
- remove(int index)方法
删除指定位置的结点。先是检查移除的位置是否在链表长度的范围内，如果不在则抛出异常，根据索引index获取需要移除的节点，将移除的节点置空，让其上一个节点和下一个节点对接起来。
unlink方法：
- remove(Object o)方法
删除链表中的指定结点
- removeFirst()方法
移除链表中的第一个结点。将第一个节点置空，让下一个节点变成第一个节点，链表长度减1，修改次数加1，返回移除的第一个节点。
- removeLast()方法
移除最后一个节点，将最后一个节点置空，最后一个节点的上一个节点变成last节点，，链表长度减1，修改次数加1，返回移除的最后一个节点。
set方法
set方法不修改modCount值。
clear方法
将所有链表元素置空，然后将链表长度修改成0，修改次数加1
toArray方法
创建一个Object的数组对象，然后将所有的节点都添加到Object对象中，返回Object数组对象。
listIterator方法
这个方法返回的是一个内部类ListIterator，用户可以使用这个内部类变量当前的链表元素，但是由于LinkedList也是非线程安全的类，所以和ArrayList中的 Iterator一样，多线程下面使用，也可能会产生多线程修改的异常。
小结
LinkedList 是双向列表。
- 链表批量增加，是靠for循环遍历原数组，依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的。增加一定会修改modCount。
- 通过下标获取某个node 的时候，（add select），会根据index处于前半段还是后半段 进行一个折半，以提升查询效率
- 删也一定会修改modCount。 按下标删，也是先根据index找到Node，然后去链表上unlink掉这个Node。 按元素删，会先去遍历链表寻找是否有该Node，如果有，去链表上unlink掉这个Node。
- 改也是先根据index找到Node，然后替换值。改不修改modCount。
- 查本身就是根据index找到Node。
- 所以它的CRUD操作里，都涉及到根据index去找到Node的操作。
