【震精】LinkedList源码竟然可以这样玩！！

如果本文中有不正确的地方请指出

由于没有留言可以在公众号添加我的好友共同讨论。

• 目录

• 介绍

• 继承结构

• 属性

• 构造方法

• 添加元素

1.介绍

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 对象一个连着一个组成手构成，可以看下方的图可以看上面的四个元素，分别就是四个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 c)一个是addAll(int index, Collection c),其实
addAll(Collection c)=addAll(int index, Collection c)
可以看下面的截图:源码如下：

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

   
   
   

    
    
    
 Object[] a = c.toArray();
   
   
   

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

   
   
   

    
    
    
if (numNew == 0)
    
    
    
 return false;
   
   
   

如果插入的位置等于链表的长度就把新增加的元素放在尾部。

   
   
   

    
    
    
Node<E> pred, succ;
    
    
    
 if (index == size) {
    
    
    
 succ = null;
    
    
    
 pred = last;
    
    
    
 } else {
    
    
    
 succ = node(index);
    
    
    
 pred = succ.prev;
    
    
    
 }
   
   
   

最后在循环要插入的元素。这里我们可以看到上面也有modCount。

5.3 addFirst()

addFirst是将元素插入到LinkedList的头部。如果现在的结构是下图的：addFirst执行的操作就是：红色是使用addFirst插入后的位置。一下是源码

调用了linkFirst方法。上面的操作时：

• 首先执行final Node  f = first;将头节点赋值给 f

• final Node  newNode = new Node<>(null, e, f);将指定元素构造成一个新节点，此节点的指向下一个节点的引用为头节点

   
   
   

    
    
    
 //将新节点设为头节点，那么原先的头节点 f 变为第二个节点
    
    
    
 first = newNode;
    
    
    
 //如果第二个节点为空，也就是原先链表是空
    
    
    
 if (f == null)
    
    
    
 //将这个新节点也设为尾节点（前面已经设为头节点了）
    
    
    
 last = newNode;
    
    
    
 else
    
    
    
 f.prev = newNode;//将原先的头节点的上一个节点指向新节点
    
    
    
 size++;//节点数加1
    
    
    
 modCount++;//和ArrayList中一样记录修改次数
   
   
   

5.4 addLast方法

addLast是将元素插入到尾部如图(黄色元素)：

黄色node是新增加。注意add也是把元素添加到尾部。我们来看一下源码：

这里看到addLast和add是调用的同一方法，这里就不在讲解。可以看上方的代码。

由于文章比较长分为两次更新。请关注我下一篇文章继续分析

原创不易,如果你喜欢本文或者对你有帮助就

请转发或者点个再看

文章好看就点这里