Java – LinkedList源码分析

标签：publicstatpollhttp关系one问题predal

java提高篇(二二)—LinkedList

一、概述

LinkedList与ArrayList一样实现List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。

LinkedList实现所有可选的列表操作，并允许所有的元素包括null。

除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。

所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。

同时，与ArrayList一样此实现不是同步的。

（以上摘自JDK 6.0 API）。

二、源码分析
2.1、定义

首先我们先看LinkedList的定义：

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

从这段代码中我们可以清晰地看出LinkedList继承AbstractSequentialList，实现List、Deque、Cloneable、Serializable。其中AbstractSequentialList提供了 List 接口的骨干实现，从而最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作,从而以减少实现List接口的复杂度。Deque一个线性 collection，支持在两端插入和移除元素，定义了双端队列的操作。

2.2、属性

在LinkedList中提供了两个基本属性size、header。

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

其中size表示的LinkedList的大小，header表示链表的表头，Entry为节点对象。

private static class Entry<E> {
E element; //元素节点
Entry<E> next; //下一个元素
Entry<E> previous; //上一个元素

Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}

上面为Entry对象的源代码，Entry为LinkedList的内部类，它定义了存储的元素。该元素的前一个元素、后一个元素，这是典型的双向链表定义方式。

2.3、构造方法

LinkedList提高了两个构造方法：LinkedLis()和LinkedList(Collection<? extends E> c)。

/**
* 构造一个空列表。
*/
public LinkedList() {
header.next = header.previous =