【原】LinkedList源码分析之 add 方法（一）

算法与编程之美 2020-08-08

展开全文

之前对ArrayList集合的add方法进行了源码分析(ArrayList源码分析之add 方法)，知道了ArrayList底层是基于数组实现的。今天我们来介绍List接口的另一种实现LinkedList，一种基于双向链表的实现方式，这种实现方式还可以实现队列和栈的功能。本次重点介绍add方法的实现。

1 目标

本次源码分析的目标是深入了解LinkedList类中 add（E e）方法的实现机制。

2 分析方法

首先编写测试代码，然后利用 Intellij Idea 的单步调试功能，逐步的分析其实现思路。

测试代码如下：

List<Object>mList=new LinkedList<Object>();//断点1
mList.add("1111");//断点2
mList.add("2222");
mList.add("3333");

3 分析流程

点击调试按钮，开始分析流程。

3.1 构造函数

首先进行的是构造函数的分析，在断点1处点击Shift+F7进入构造函数实现。
public LinkedList() {
}

点击进入后，我们会看到LinkedList的构造方法，这是一个空参构造。同时我们可以看到LinkedList这个类的继承关系

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

这里看到LinkedList继承自AbstractSequentialList而不是像ArrayList那样直接继承自AbstractList。它还实现了Deque, Cloneable, java.io.Serializable三个接口，分别使它能作为双端队列使用，可以使用clone()复制链表，使LinkedList支持序列化。这三个接口以后我们有机会再详细介绍。因为LinkedList既实现了List接口，又实现了Deque接口，所以LinkedList既可以将元素添加到尾部，也可以将元素添加到指定索引位置，还可以添加整个集合。

我们会分别从List接口和Deque接口分别介绍，他们分别对应add（E e）方法和add(int index,E e)。这篇文章我们着重介绍add（E e）方法，介绍之前我们先来看看LinkedList的成员变量。

transient int size = 0; //集合元素个数
transient Node<E> first; //头结点引用
transient Node<E> last; //尾结点引用

3.2 add（E e）方法

接下来我们分析add( E e)方法的实现机制。在断点2处点击shift+F7进入其实现源码。

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

这个方法就两行代码，看起来是不是特别简单呢。这里可以看到它调用了一个linkLast方法，然后返回true。那这个linkLast方法放在这里实现了什么功能呢？他具体是怎么实现的呢？

继续F7调试，进入此方法内部，看到如下代码。

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

可以看到这里面频繁出现了Node这个词，这个Node是什么意思呢？这里我们可以先猜测一下，之前我们已经知道LinkedList是基于双向链表实现的，而链表中有一个词“结点”，根据字面意思Node也是代表结点，所以我们根据字面意思猜测这段代码的意思就是：先取到之前的最后一个元素，创建新的节点，新节点的后继指向原来的头节点，即将原头节点向后移一位，新节点代替头结点的位置。它的后一个结点由于还没有存放元素，因此设为空值。还对初始链表为空的时候做了判断和处理，size++将链表大小增加。modCount++修改次数增加。

现在我们来验证一下我们的猜想是否正确：

我们定位在Node上，点击Ctrl+B查看其源码

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

可以看到Node是一个内部类，这个类定义了三个成员变量:

item代表要添加的元素,

next表示下一个结点的引用，

prev表示上一个节点的引用；

和一个构造器，通过构造器传入上面这三个值。继续往下调试，果然，他开始执行上面的代码，对三个成员变量进行了引用。继续调试，会发现，我们上面的猜测基本上正确。但是我们还不知道当它整个链表为空的时候为空的时候他是怎么处理的。

看如下代码

if (l == null)
        first = newNode;
    else
        l.next = newNode;

当对前结点的引用为空的时候新节点即为头结点，不为空的时候就将新的结点赋值给头节点的引用的下一个结点。最后进行size++和modCount++操作。至此就完成了LinkedList的第一次add操作。当进行第二次操作的时候，会再次执行上述过程。由此我们可以分析出LinkedList的基本数据结构。我们用图来说明它的结构，首先是结点（Node）的结构。