LinkedList源码阅读

双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项前后项即可，插入数据较快；其实主要是数据结构的东西

三个属性：头尾节点、size

L1.jpg

Node节点(内部静态私有类)

L2.jpg

构造方法：

无参：构造一个空链表。

有参构造函数：

public LinkedList(Collection<? extends E> c) {
        this();//调用无参构造方法构造一个空的链表
        addAll(c);
    }

先产生一个空链表，再调用addAll(Collection<? extends E> c)方法，再有addAll调用addAll(int index, Collection<? extends E> c)，传入的index为size，在构造函数这也就是从0开始覆盖，

add过程：先对index的两种情况进行了处理：一种是index==size（在尾部插入），另一种是index，遍历传入的c（将c转换为Object），创建newNode，依次循环即可

支持放入null元素，但不是说节点为null，而是节点中的item为null

add方法：

直接调用linkLast，在尾部添加节点

L3.jpg

linkLast的步骤：

获得last节点为l，创建新对象（设置传入的对象的prev为l节点，next为null），再设置last为新创建的对象，最后判断l是否为空，如果是，first为新创立的节点，否则，l.next为新创立的对象，再修改size

此时堆栈的形式为：

L4.jpg

最后，双向链表：

L5.jpg

remove方法：

嗯，记得先覆盖equals方法

L6.jpg

util集合支持往里面放入null值元素（不是null）。当然了，代码主要功能是调用了unlink方法

unlink步骤为：先判断前后节点是否为空并设置，最后另x.item = null，更新size等，返回

复杂度：

LinkedList底层链表删除元素只是简单的修改了一下引用地址，时间复杂度为O(1)。

参考：https://zhuanlan.zhihu.com/p/28101975