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的操作。