LinkedList源码分析：JDK源码分析系列

LinkedList 是线程不安全的，允许元素为null的双向链表。

2.继承结构

我们来看一下LinkedList的继承结构图：

代码实现:

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

Cloneable实现克隆

Serializable序列化

List 定义了一些集合类的方法

Deque双向队列接口(就是两端都可以进行增加删除操作)

注意一点LinkedList并没有实现RandomAccess所以随机访问是非常慢的。

3.属性

元素个数

transient int size = 0;

指向第一个节点的指针(注释直接就写着)

/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first;

指向最后一个节点的指针

/** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;

transient关键字的作用是保持变量不被序列化具体的百度。

不过我们注意到LinkedList是有Node类，这里的Node是一个内部类：

item存储的元素

next指向后置节点

prev指向前置节点

内部类同时包含了一个构造函数

其实LinkedList 集合就是由许多个 Node 对象y一个连着一个组成手构成，可以看下方的图

可以看上面的四个元素，分别就是四个Node对象，可以看到node1所指向的prev上一个节点是空也就是没有上节点,node4所指向的next节点为空也就是没有下一个节点。

4.构造方法

LinkedList共有两个构造方法，一个是创建一个空的构造函数，一个是将已有的Collection添加到LinkedList中。

因为LinkedList不同于ArrayList所以初始化不需要指定大小取分配内存空间。

5.添加元素

LinkedList有几种添加方法我们先从add()开始。

5.1 add方法

checkPositionIndex(index);

可以看到在调用Add方法首先校验一下索引是否合法，如果不合法就会抛出异常。

if (index == size) linkLast(element); else linkBefore(element, node(index));

然后如果索引值等于size的值则直接调用linkLast插入到尾部节点。

否则就linkBefore方法。
linkLast方法：

void linkLast(E e) { //将l设为尾节点 final Node<E> l = last; //构造一个新节点，节点上一个节点引用指向尾节点l final Node<E> newNode = new Node<>(l, e, null); //将尾节点设为创建的新节点 last = newNode; //如果尾节点为空，表示原先链表为空 if (l == null) //将头节点设为新创建的节点（尾节点也是新创建的节点） first = newNode; else //将原来尾节点下一个节点的引用指向新节点 l.next = newNode; size++;//节点数加1 modCount++; }

注意一下这里出现了modCount方法，和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
linkBefore:

void linkBefore(E e, Node<E> succ) { //将pred设为插入节点的上一个节点 final Node<E> pred = succ.prev; //将新节点的上引用设为pred,下引用设为succ final Node<E> newNode = new Node<>(pred, e, succ); //succ的上一个节点的引用设为新节点 succ.prev = newNode; //如果插入节点的上一个节点引用为空 if (pred == null) //新节点就是头节点 first = newNode; else //插入节点的下一个节点引用设为新节点 pred.next = newNode; size++; //同上 modCount++; } 5.2 addAll()

在LinkedList中有两个addAll方法一个是 addAll(Collection<? extends E> c)一个是addAll(int index, Collection<? extends E> c),其实

addAll(Collection<? extends E> c)=addAll(int index, Collection<? extends E> c)

可以看下面的截图:

源码如下：

现在开始分析源码：
首先我们可以看到先调用了checkPositionIndex(index);方法来检查索引是否合法。
然后将传进来的Collection转成Object数组

Object[] a = c.toArray();

如果集合为空就直接返回false

if (numNew == 0) return false;