LinkedList源码分析之 add 方法(二)

1 目标

本次源码分析的目标是深入了解LinkedList类中add(int index, E e) 方法的实现机制。

2 分析方法

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

测试代码如下：

3 分析流程

先点击运行按钮，运行结果如上，可以看到我们在“2222”与“3333”之间添加了新元素“4444”，LinkLisk是怎么实现的呢？点击调试按钮，开始分析流程。

3.1 add(int index, Eelement)方法

我们直接进行add方法分析，在断点1处点击 Shift+F7进入方法内部实现。

点击进入后，我们会看到如上代码，此方法共有五行代码，共调用了三个方法。

首先调用了checkPositionIndex方法，按住Ctrl+B键进入其源码实现：

这个方法里面又调用了一个isPositionIndex方法，我们继续进入查看其源码：

不难看出此方法是用来判断索引是否处于[0~size]之间，由此我们就知道checkPositionIndex方法是用于检查索引位置是否合法，如果不合法就抛出数组越界的异常。

接着做了对索引与size的大小做了一个判断，如果index==size则调用linkLast方法，在链表尾部添加元素。否则调用linkBefore方法，在链表中间添加元素。

对于linkLast方法之前已经具体介绍过，具体可以参考LinkedList源码分析之 add 方法（一）。

接下来将重点介绍linkBefore方法的实现。

3.2 linkBefore(E e,Node<E> succ)方法

从上一节可以看到，在调用linkBefore方法的时候，先调用了node（int index）方法，所以在介绍linkBefore方法之前我们先来看看node方法，该方法返回指定位置的结点，具体实现如下：

此方法通过索引定位时先判断索引是在链表的上半部分还是在下半部分，如果是在上半部分就从头开始找起，如果是下半部分就从尾部开始找起。

由于链表中是没有下标索引的，要得到指定位置处的结点，就要遍历该链表，得到该节点后就将其返回。从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果index>size/2，就只从位置size往前遍历到位置index处。因此通过下标的查找和修改操作的时间复杂度为o（n/2）,提升了程序的运行效率。

再看linkBefore()方法，实现如下：

执行完此方法，则一次add操作完成。我们通过方法执行过程图来直观的看一下该方法的运行过程：

图3-1  linkBefore()添加节点示意图

上述描述的是双向链表在某固定位置插入新节点的执行流程图。

4 总结

本文对LinkedList的add(int index, E e)方法的源码进行了详细分析，了解了LinkedList集合在指定位置添加元素的实现方法，重点介绍了linkBefore方法，我们可以总结得出linkBefore主要分为三步：

第一步：创建newNode节点，将newNode的后继指针指向succ，前驱指针指向pred。

第二步：将succ的前驱指针指向newNode。

第三步：根据pred是否为null，进行不同操作。

- 如果pred为null，说明该节点插入在头节点之前，要重置first头节点。

- 如果pred不为null，那么直接将pred的后继指针指向newNode即可。

结合上一讲我们将LinkedList的add方法的两种形式都已经介绍完毕，明白了LinkedList是通过修改相邻结点之间的引用关系进行add操作，效率是比较高的。

本文作者系四川旅游学院2016级信息管理与信息系统专业张承财投稿。