Java学习笔记 LinkedList源码分析

一、概念

LinkedList底层是一个双向链表，除了存储自身值之外，还额外存储了其前一个和后一个元素的地址，所以也就可以很方便地根据当前元素获取到其前后的元素。

实现接口：

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
    // 略...
}

可以看到、LinkedList实现了List接口，又实现了Deque接口，所以既可以添加将元素添加到尾部，也可以将元素添加到指定索引位置，还可以添加添加整个集合。

属性如下：

// 链表长度
transient int size = 0;
// 指向第一个节点
transient Node<E> first;
// 指向最后一个节点
transient Node<E> last;

Node节点：

是在LinkedList类里边定义的静态内部类，如下：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

如下分析：

item就是存储要添加的数据。
next指针域指向下一个节点。
prev指针域指向前一个节点。

示意图如下：

所以：LinkedList删除和添加的效率非常高，而查询会比较慢。

因为查询需要一个节点一个节点的找，而删除和添加只需要修改目标节点的前一个节点的next域和后一个节点的prev域即可。

二、分析

2.1.构造函数

1、无参构造

public LinkedList() {
}

因为是链表，不是数组，所以不需要刚开始就扩容，添加数据创建节点即可。

2、有参构造

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

可以看到，在里边还是调用了无参构造方法，然后调用addAll()方法，将参数直接传入，如下代码：

// 定义list2集合
List<Integer> list2 = new LinkedList<>();
list2.add(1);
list2.add(2);
// 将list2集合作为参数传入到list3集合的构造方法当中
List<Integer> list3 = new ArrayList<>(list2);
// 输出  1   2
list3.forEach(x -> System.out.println(x));

2.2.方法

1、add方法

public boolean add(E e) {
    linkLast(e);
    return true;
}

内部调用了一个linkLast()方法，看名字就知道是将新节点添加到链表的尾部，跟进去如下：

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++;
}

如下分析：

如果l == null：
1. 首先将指向尾节点的last赋值给了 l，所以l为null，因为刚开始啥都没有，last为空。
2. 然后新建Node节点，构造函数里边prev指向l，中间是数据，next域为null。
3. 将新创建的Node节点赋值给last。这时尾指针指向新节点。
4. 进入判断里边让first也指向新节点。这个时候first和last同时指向新节点，同时prev和next都为空。
如果l != null：
1. 首先将指向尾节点的last赋值给了 l，也就是先把尾节点保存起来，因为添加新节点后last要向后移动。
2. 创建新节点，prev指向原先的尾节点。
3. 将新节点赋值给last，也就是last指向新的节点，因为新的节点是添加到末尾的。
4. 进入判断里边让原先尾节点的next域指向新节点。
最后size++，modCount++，也就是长度加一，修改次数加一。

2、addFirst()方法

public void addFirst(E e) {
    linkFirst(e);
}

这是往头部添加数据，进入linkFirst()方法内部：

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

这里整体逻辑就是：

先保存原先指向第一个节点的first，创建新节点，next域为原先第一个节点，然后让first指向新节点。
判断f是否为空，如果为空说明链表为空，最后就是将first和last都指向新节点。
如果不为空，则让原先第一个节点的prev指向新节点，最后size++和modCount++。

常用的方法还有很多，比如getLast()方法、getFirst()方法、addLast(E e)方法等等，都是对链表的操作，也就是修改first和last，或者prev和next域。这里的源码是JDK8版本，不同版本可能会有所差异，但是基本原理都是一样的。

三、结尾

3.1.LinkedList和ArrayList的区别

ArrayList的顺序插入的速度快，LinkedList的速度回稍慢一些。因为ArrarList只是在指定的位置上赋值即可，而LinkedList则需要创建Node节点，并且需要建立前后关联，如果对象较大的话，速度回慢一些。
LinkedList的占用的内存空间要大，因为有next域和prev以及first和last等等。