LinkedList源码阅读

发表于 更新于 分类于
在List接口实现的类中，最常用的一个类：LinkedList，常被用来实现队列和类似于ArrayList的数据结构。

LinkedList的数据结构

LinkedList的底层数据结构是基于双向链表实现的，如图：
因为链表在物理内存上可以是不连续的，所以理论上，只要计算机的内存足够大的情况下，LinkedList的长度可以无限长。

顶部注释

双向链表实现了List和Deque接口。 实现所有可选列表操作，并允许所有元素（包括null ）。
所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。

请注意，此实现不同步。 如果多个线程同时访问链接列表，并且至少有一个线程在结构上修改列表，则必须在外部进行同步。 （结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。）这通常通过在自然封装列表的对象上进行同步来实现。 如果没有这样的对象存在，列表应该使用Collections.synchronizedList方法“包装”。 这最好在创建时完成，以防止意外的不同步访问列表：
List list = Collections.synchronizedList(new LinkedList(...));

该类的iterator和listIterator方法返回的迭代器是fail-fast的 ：如果列表在迭代器创建后的任何时间进行结构修改，除了通过Iterator自己的remove或add方法外，迭代器将抛出一个ConcurrentModificationException 。 因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。

请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。 失败快速的迭代器ConcurrentModificationException扔掉ConcurrentModificationException 。 因此，编写依赖于此异常的程序的正确性将是错误的： 迭代器的故障快速行为应仅用于检测错误。

从上面LinkedList的源码顶部注释可以总结以下几点：

  • 底部实现：双向链表。
  • 是否允许null值：允许所有元素，包括null。
  • 线程安全：线程不安全。
  • 迭代器：迭代器是fast-fail，但是迭代器的快速失败行为不能得到保证。
  • 运行时间：因为是链表的实现，所以任何需要查询到操作都需要遍历链表，即O(n)的时间。

LinkedList的定义

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  • LinkedList：支持泛型的存储模式。
  • extends AbstractSequentialList：继承于AbstractSequentialList，继承了其中的方法，方便操作。
  • implements List：实现了List接口，实现该接口提供的方法，方便了实现。
  • implements Deque：实现了双端队列的接口，因此双向链表操作起来更方便。
  • implements Cloneable：实现了Cloneable接口，内部可以调用clone()方法来返回实例的浅拷贝(shallow copy)。
  • implements Serializable：实现了Serializable接口，表明该类是可以序列化的。

全局变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//记录元素个数的常量
transient int size = 0;

//静态内部类Node，即存储每个数据的节点
private static class Node<E> {
/**
* 内存保存的内容有三个，分别是：
* item:储存的元素
* next:该节点后面一个节点
* prev:该节点前面一个节点
*/
       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;
       }
   }

   /**
    *	 指向第一个节点的指针。
    */
   transient Node<E> first;

   /**
    * 	指向最后一个节点的指针。
    */
   transient Node<E> last;

构造方法

LinkedList只有两个构造方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
    * 构造一个空列表。
    */
   public LinkedList() {
   }

   /**
    * 构造包含指定集合的元素的列表，按集合的迭代器返回元素的顺序排列。
    *
    * @param  c 要将其元素放入此列表的集合
    * @throws NullPointerException 如果指定的集合为空
    */
   public LinkedList(Collection<? extends E> c) {
       this();
       addAll(c);
   }

可以从上面的代码中看出，两个构造方法分别是无参方法和传入一个集合的方法。

无参方法的方法体为空，因为是链表结构，而链表的头指针和尾指针已经在上面定义过了，而且不同于数组结构，不需要指定大小和扩容，所以方便很多，因此无参方法什么都不需要做。

传入一个集合的构造方法使用addAll()方法将传入的集合按顺序添加到链表的尾部，addAll()方法可以的具体实现可以看下面的核心方法部分。

核心方法

getFirst和getLast方法

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 返回列表中的第一个元素。
 *
 * @return 列表中的第一个元素
 * @throws NoSuchElementException 如果这个列表是空的
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

根据代码可以看出，获取到first节点，如果列表中没有元素，所以列表是空的，first节点自然是null，所以抛出NoSuchElementException异常；否则返回first节点的数据。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 返回列表中的最后一个元素。
 *
 * @return 列表中的最后一个元素
 * @throws NoSuchElementException 如果这个列表是空的
 */
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

同getFirst方法很相似，获取到last节点的值，依旧判断last是否为空，为空则抛出异常；否则返回最后一个节点last的值。

removeFirst方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 	从列表中移除并返回第一个元素。.
 *
 * @return 列表中的第一个元素
 * @throws NoSuchElementException 如果这个列表是空的
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * 	断开第一个非空节点f的链接。
 */
private E unlinkFirst(Node<E> f) {
    // 判断 f == first && f != null;
    final E element = f.item;
    //头节点的下一个节点，当头节点移除后，它就是头节点
    final Node<E> next = f.next;
    /**
     * 	因为头节点是第一个节点，所以它的prev自然为null
     * 	把头结点的值和next字段赋值为null，有助于GC回收
     */
    f.item = null;
    f.next = null; // 有助于 GC
    //然后把next作为头节点
    first = next;
    /**
     * 	如果头节点的下一个节点是null，那么说明列表中只有一个节点
     * 	因此把last也赋值为null，说明至此链表中已无元素
     * 
     * 	否则把头结点的prev字段置为null，说明该节点是头节点
     */
    if (next == null)
        last = null;
    else
        next.prev = null;
    /**
     * 	列表中元素数量减一
     * 	修改次数加一
     * 	返回被删除节点的值
     */
    size--;
    modCount++;
    return element;
}

removeLast方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 	从列表中移除并返回最后一个元素。
 *
 * @return 列表中的最后一个元素
 * @throws NoSuchElementException 如果这个列表是空的
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

/**
 *	 断开最后非空的一个节点l。
 */
private E unlinkLast(Node<E> l) {
    // 判断 l == last && l != null;
    final E element = l.item;
    //尾节点的前一个节点，当尾节点移除后，它就是尾节点
    final Node<E> prev = l.prev;
    /**
     * 	因为尾节点是第一个节点，所以它的next自然为null
     * 	把头结点的值和prev字段赋值为null，有助于GC回收
     */
    l.item = null;
    l.prev = null; // 有助于 GC
  //然后把prev作为头节点
    last = prev;
    /**
     * 	如果尾节点的前一个节点是null，那么说明列表中只有一个节点
     * 	因此把first也赋值为null，说明至此链表中已无元素
     * 
     * 	否则把尾结点的next字段置为null，说明该节点是尾节点
     */
    if (prev == null)
        first = null;
    else
        prev.next = null;
    /**
     * 	列表中元素数量减一
     * 	修改次数加一
     * 	返回被删除节点的值
     */
    size--;
    modCount++;
    return element;
}

addFirst方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 	在列表的开头插入指定的元素。
 *
 * @param e 要添加的元素
 */
public void addFirst(E e) {
    linkFirst(e);
}

/**
 * 	链接e作为第一个元素。
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    //调用Node的构造方法，定义一个prev字段为null、next字段为f的newNode节点
    final Node<E> newNode = new Node<>(null, e, f);
    //然后把newNode作为头节点
    first = newNode;
    /**
     * 	如果原来的头节点f为空的话，说明列表中原来没有任何元素
     * 	所以现在插入了一个新的节点，自然头节点和尾节点都是它，所以尾节点也是它。
     */
    if (f == null)
        last = newNode;
    else
    	/**
    	 *	否则列表中原来不为空，只需要把新节点和原来的头节点连起来就好了
    	 *	连起来的方法就是把原结点f的prev字段赋为现在的新头节点即可
    	 *	即f节点是链表中第二个节点
    	 */
        f.prev = newNode;
    /**
     * 	元素数量加一
     * 	修改次数加一
     */
    size++;
    modCount++;
}

add和addLast方法

add和addLast方法中同是调用了linkLast方法，将新的元素添加到链表的尾部，二者的唯一却别就是add方法添加成功的话，会返回true表示插入成功，而addLast方法则无返回值，在内部实现上无任何区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 *	将指定的元素追加到此列表的末尾。
 *
 * <p>这个方法相当于 addLast() 方法
 *
 * @param e 要附加到此列表中的元素
 * @return true （由 Collection.add(E)指定） 
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
	
/**
 * 	将指定的元素追加到此列表的末尾。
 *
 * <p>这个方法相当于 add() 方法
 *
 * @param e 要添加的元素
 */
public void addLast(E e) {
    linkLast(e);
}

/**
 *	 链接e作为最后一个元素。
 */
void linkLast(E e) {
    final Node<E> l = last;
    //定义一个前驱节点是last、后置节点是null的节点newNode，即将作为尾节点
    final Node<E> newNode = new Node<>(l, e, null);
    //把刚刚新定义的节点作为新的尾节点
    last = newNode;
    /**
     *	如果原来的尾节点是null的话，说明原来列表中无元素，所以first自然也为null
     *	所以这里新插入一个元素后，first和last节点同时指向仅有的一个元素节点
     *	仅有的该元素节点既是头节点，也是尾节点
     */
    if (l == null)
        first = newNode;
    else
    	/**
    	 * 	如果原来列表中元素不为空，就把新的尾节点和旧的尾节点连接起来
    	 * 	方法就是把旧的尾节点的next字段置为新的尾节点，即l节点是倒数第二个节点
    	 */
        l.next = newNode;
    /**
     * 	元素数量加一
     * 	修改次数加一
     */
    size++;
    modCount++;
}

contains和indexOf方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * 	如果此列表包含指定的元素，则返回true。更正式地说，当且仅当此列表包含至少一个元素e，使得Objects.equals(o, e)。
 * 
 *
 * @param o 其在此列表中的存在性将被测试的元素
 * @return {@code true} 如果此列表包含指定的元素
 */
public boolean contains(Object o) {
	/**
	 *	内部则调用indexOf方法，判断该元素的下标是否大于等于零
	 *	下标大于等于零则表示元素存在，如果不存在，indexOf方法会返回-1
	 */
    return indexOf(o) >= 0;
}

/**
 *	返回此列表中指定元素的第一个出现项的索引，如果该列表不包含该元素，则返回-1。
 *	更正式地说，返回最低索引i满足Objects.equals(o, get(i))，如果没有这样的索引，则为-1。
 * 
 *
 * @param o 要搜索的元素
 * @return 此列表中指定元素的首次出现的索引，如果此列表不包含元素，则为-1 
 */
public int indexOf(Object o) {
    int index = 0;
    /**
     *	因为LinkedList允许元素为null，所以要分开判断元素是null和非null的情况
     *	因为null的判定方法是 == 号，而非null的元素则使用Objects.equals(o, get(i))方法
     */
    if (o == null) {
    	/**
    	 *	当要查找的元素是null的时候，从头节点first节点开始遍历
    	 *	直到找到值为null或者节点为null为止，节点为null的也就是last之后的那个节点为止
    	 */
        for (Node<E> x = first; x != null; x = x.next) {
        	/**
        	 *	如果节点中的值为null，则返回其下标
        	 *	否则继续向后遍历，下标加一
        	 */
            if (x.item == null)
                return index;
            index++;
        }
    } else {
    	/**
    	 *	当要查找的元素是非null的时候，从头节点first节点开始遍历
    	 *	直到找到o.equals(x.item)或者节点为空为止，也就是last之后的那个节点为止
    	 */
        for (Node<E> x = first; x != null; x = x.next) {
        	/**
        	 *	如果节点中的值为与要查找的节点一致，则返回其下标
        	 *	否则继续向后遍历，下标加一
        	 */
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    //如果遍历过整个链表都没有找到符合要求的节点的话，就返回-1
    return -1;
}

size方法

1
2
3
4
5
6
7
8
9
   /**
    * 返回此列表中的元素数量。
    *
    * @return 列表中元素的数量
    */
   public int size() {
//即返回记录链表中元素数量的遍历size
       return size;
   }

remove方法

remove方法有三个重载方法，分别是无参方法、传入下标和传入指定对象的方法。

remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
  *	从列表中删除指定元素的第一个出现项(如果存在)。如果这个列表不包含这个元素，它将保持不变。
  *	更正式地说，删除索引i最低的元素，使得Objects.equals(o, get(i)) (如果存在这样一个元素)。
  *	如果此列表包含指定的元素，则返回true(如果此列表由于调用而更改，则返回true)。
  * 
  * @param o 元素，如果存在，则从该列表中删除
  * @return {@code true} 如果此列表包含指定的元素
  */
 public boolean remove(Object o) {
     if (o == null) {
     	/**
     	 *	如果传入的对象是null，则遍历链表，找到第一个值为null的节点
     	 *	然后调用unlink方法将其删除
     	 */
         for (Node<E> x = first; x != null; x = x.next) {
             if (x.item == null) {
                 unlink(x);
                 return true;
             }
         }
     } else {
     	/**
     	 *	如果传入的对象是非null的，则遍历链表，找到第一个符合o.equals(x.item)的节点
     	 *	然后调用unlink方法将其删除
     	 */
         for (Node<E> x = first; x != null; x = x.next) {
             if (o.equals(x.item)) {
                 unlink(x);
                 return true;
             }
         }
     }
     //如果删除成功，则返回true，否则返回false。
     return false;
 }
 
 /**
  *	断开非空节点x的链接。
  */
 E unlink(Node<E> x) {
     /**
      * 	判断 x != null
      * 	记录要删除的节点和其前驱节点和后置节点
      */
     final E element = x.item;
     final Node<E> next = x.next;
     final Node<E> prev = x.prev;
     /**
      *	如果前驱节点是null的话，说明要删除的节点就是第一个节点
      *	故删除后就把它的后置节点（也就是第二节点）作为新的头节点
      *
      *	否则把前驱节点的下一个节点赋为当前节点的后一个节点
      *	然后把当前节点的前驱节点置为null
      */
     if (prev == null) {
         first = next;
     } else {
         prev.next = next;
         x.prev = null;
     }
     
     /**
      *	如果后置节点是null的话，说明要删除的节点就是最后一个节点
      *	故删除后就把它的前驱节点（也就是倒数第二个节点）作为新的头节点
      *
      *	否则把后置节点的前一个节点赋为当前节点的前一个节点
      *	然后把当前节点的后置节点置为null
      */
     if (next == null) {
         last = prev;
     } else {
         next.prev = prev;
         x.next = null;
     }
     
     /**
      *	经过上面两个if判断，当前节点的前驱节点和后置节点已经全部赋值为null
      *	并且已经把它的前驱节点和后置节点相互连接了
      *	这里当前节点把值赋为null，就意味着删除了，然后等待GC回收即可
      */
     x.item = null;
     /**
      *	元素数量减一
      *	修改次数加一
      *	返回被删除的节点的值
      */
     size--;
     modCount++;
     return element;
 }

remove(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 移除列表中指定位置的元素。将任何后续元素向左移动(从它们的索引中减去一个)。返回从列表中删除的元素。 
 *
 * @param index 要删除的元素的索引
 * @return 先前位于指定位置的元素
 * @throws IndexOutOfBoundsException 表示某种索引(如数组索引、收敛索引或向量索引)超出范围。
 */
public E remove(int index) {
	/**
	 * 这里先对传入的下标进行检查，判断是否越界
	 * 如果没有越界则使用node(index)方法找到指定位置的结点
	 * 然后使用unlink方法将这个节点删除
	 */
    checkElementIndex(index);
    return unlink(node(index));
}

先看以下判断下标是否越界的checkElementIndex方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * checkElementIndex 方法实际调用了这个方法判断下标是否越界
 * 如果越界则抛出异常
 * 
 * @param index
 * @return
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

在下标符合要求后，使用node方法查找到指定位置的节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 返回指定元素索引处的(非空)节点。
 */
Node<E> node(int index) {
	/**
	 * 这里先判断要查找的下标是在链表的前半部分还是后半部分
	 * 如果是在前半部分就从头指针开始查找
	 * 如果是在后半部分就从尾指针开始查找
	 */
    if (index < (size >> 1)) {
    	//在前半部分，从头指针开始查找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
    	//在后半部分，从尾指针开始查找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

在使用node方法找到指定下标位置的节点之后，使用unlink方法将该节点删除掉，unlink方法在上面remove(Object o)方法中有讲过。

remove()

1
2
3
4
5
6
7
8
9
10
11
/**
 * 检索并删除此列表的头部(第一个元素)。
 * 该方法与removeFirst无差别，不多赘述，二者一模一样。
 *
 * @return 这个列表的头
 * @throws NoSuchElementException 如果这个列表是空的
 * @since 1.5
 */
public E remove() {
    return removeFirst();
}

lastIndexOf方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 返回此列表中指定元素的最后一次出现的索引，如果该列表不包含该元素，则返回-1。
 * 更正式地说，返回最高索引i，满足Objects.equals(o, get(i))，如果没有这样的索引，则为-1。
 * 
 *
 * @param o 要搜索的元素
 * @return 此列表中指定元素的最后一次出现的索引，如果该列表不包含该元素，则为-1     
 */
public int lastIndexOf(Object o) {
	/**
	 * 这个方法实现indexOf方法唯一的区别就是：这个方法从后向前查找，而indexOf方法从前向后查找，其余部分无区别
	 */
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

toArray方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * 返回一个数组，该数组按适当的顺序(从第一个元素到最后一个元素)包含列表中的所有元素。
 *
 * 返回的数组将是“安全的”，因为这个列表不维护对它的引用。(换句话说，这个方法必须分配一个新的数组)。
 * 因此，调用者可以自由地修改返回的数组。
 *
 * 此方法充当基于数组和基于集合的api之间的桥梁。
 *
 * @return 一个数组，按适当的顺序包含列表中的所有元素
 */
public Object[] toArray() {
	/**
	 * 实现方法就是先创建一个与size大小相等的数组
	 * 然后从头结点开始遍历整个链表，把链表中的每个节点的值存入数组中
	 * 最后把数组返回
	 */
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

/**
 * 以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 
 * 返回的数组的运行时类型是指定数组的运行时类型。
 * 如果列表适合指定的数组，则返回其中。 否则，将为指定数组的运行时类型和此列表的大小分配一个新数组。 
 * 
 *
 * 如果列表适用于指定的数组，并有空余余地（即数组的列表null更多），
 * 则紧跟在列表末尾的数组中的元素设置为null 。 （这仅在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。） 
 * 
 * 像toArray()方法一样，此方法充当基于阵列和基于集合的API之间的桥梁。 
 * 此外，该方法允许精确地控制输出阵列的运行时类型，并且在某些情况下可以用于节省分配成本。 
 * 
 *
 * 假设x是一个已知只包含字符串的列表。 以下代码可用于将列表转储到新分配的String数组中： 
 * String[] y = x.toArray(new String[0]); 
 * 请注意， toArray(new Object[0])功能与toArray()相同。 
 *   
 *
 * @param a  要存储列表的元素的数组，如果它足够大; 否则，为此目的分配相同运行时类型的新数组。 
 * 
 * @return 一个包含列表元素的数组 
 * @throws ArrayStoreException 如果指定数组的运行时类型不是此列表中每个元素的运行时类型的父类型 
 * @throws NullPointerException 如果指定的数组为空
 */
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
	//先检查传入的数组长度是否足够，如果不够就将数组扩容为size大小
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    //在容量足够的前提下，将链表中的元素按顺序放入数组中
    int i = 0;
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    //将第一个空出来的位置赋值为null，表示无元素
    if (a.length > size)
        a[size] = null;

    return a;
}

队列操作的方法

因为Queue和Deque都是使用LinkedList实现的，所以这里也顺便提一下把，但是实际上有关队列操作的方法实则都是使用上面的核心方法实现的，所以这里就列一个表格对比一下：

  • peek() ：等于getFirst()方法，唯一区别就是当链表为空时，peek方法返回null，getFirst抛出异常。
  • element()：等于getFirst()方法。
  • poll()：等于removeFirst()方法，唯一区别就是当链表为空时，poll方法返回null，removeFirst抛出异常。
  • remove():等于removeFirst()方法。
  • offer()：等于add()方法。
  • offerFirst()：等于addFirst()方法。
  • offerLast()：等于addLas()方法。
  • peekFirst()：等于peek()方法。
  • peekLast()：等于getLast()方法，唯一区别就是当链表为空时，peekLast方法返回null，getLast抛出异常。
  • pollFirst()：等于removeFirst()方法，唯一区别就是当链表为空时，pollFirst方法返回null，removeFirst抛出异常。
  • pollLast()：等于removeLast()方法，唯一区别就是当链表为空时，pollLast方法返回null，removeLast抛出异常。
  • push()：等于addFirst()方法.
  • pop()：等于removeFirst()方法。
  • removeFirstOccurrence()：等于remove()方法。
  • removeLastOccurrence()：等于removeLast()方法。

总结

总体来说，LinkedList的源码十分简单，从源码中可以简单得出以下几点：

  • LinkedList的底层是双向链表。
  • 有序。链表是有序的。
  • 元素可重复，元素可为null。
  • 随机访问效率低，增删效率高。