LinkedList源码解析
源码解析对应JDK1.7
JDK1.7源码下载地址：JDK1.7下载地址
链表
LinkedList是基于链表实现的，链表与数组一样，都作为数据的基本存储结构，但是在存储原理上二者是不同。
数组中，数据是存储在一段连续的内存空间中，可以通过下标方式访问数组中的元素。
链表中，元素是存储在不同的内存空间中，前一个元素的位置维护了后一个元素在内存中的地址。
单向链表
我们将链表中的每一个元素称之为一个节点(Node)，链表的数据结构可以用下图表示：
(感谢原作者的图，画的非常贴切)
上图显示了一个链表的数据结构，链表中的每个Node都维护了2个信息：
a. 这个Node(节点)自身存储的数据Data
b. 下一个Node的引用信息(图中用Next表示)
对于最后一个Node，因为没有了下一个元素，所以并没有引用其他的元素，在图中用紫色狂表示。
在《数据结构与算法分析-Java语言分析》一书中，对链表的描述：
链表是由一系列节点组成，这些节点不必在内存中相连。
每一个节点均含有数据元素Data(原文是"表元素"，感觉会有歧义) 和 到包含该元素后继节点的链(link)。
我们称之为next链表。
最后一个单元的next链引用为null。
通过上图，可以发现向链表插入或者删除某一项的操作不需要移动很多项，而只要涉及常数个节点链的改变
双向链表
如果上面了理解了单向链表，那么双向链表也是很好理解的。
同单向链表不同，双向链表有三部分组成：上一个节点，当前节点，下一个节点。
当链表中只有一个节点的时候，这个节点指向上一个节点是空，下一个节点也是空。
LinkedList是基于链表实现的，更确切的说，是基于双向链表实现的。
a. 双向链表中任意一个存储单元都可以通过向前或者向后寻址获取到前一个存储单元或后一个存储单元。
b. 双向链表的尾节点向后一个节点是链表的头结点；双向链表头结点向前一个节点是链表的尾节点。(原文作者的理解，表示赞同)
关于LinkedList首先记住结论
a. LinkedList 允许为空(null)
b. LinkedList 允许数据重复
c. LinkedList 是有序的
d.LinkedList 非线程安全
LinkedList存储单元
LinkedList既然是双向链表，必然有一个存储单元，我们看下源码：
private static class Node<E> {
// 节点值
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;
}
}
从上面可以看出，E item 是真正存储节点元素的。
Node<E> next 和 Node<E> prev 表示的就是这个存储节点 前一个存储单元 和 后一个存储单元的引用地址
(上面双线链表的图，就是很好的示例)
LinkedList主要参数
// 双向链表中节点的个数
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;
LinkedList构造方法
LinkedList()：
构造一个空列表
LinkedList(Collection<? extends E> c)：
构造一个包含指定集合的元素的列表，按照集合的迭代器返回的顺序
这里我们来分析下带参数的构造方法：
/**往下调用了 addAll 方法
* Constructs a list containing the elements of the specified collection, in
* the order they are returned by the collection's iterator.<br>
* 构造一个包含指定集合的元素的列表，按照集合的迭代器返回的顺序。
*
* @param c
* the collection whose elements are to be placed into this list
* @throws NullPointerException
* if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**往下继续调用 addAdd () 方法，不过这个方法是重载的。
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the specified
* collection's iterator. The behavior of this operation is undefined if the
* specified collection is modified while the operation is in progress.
* (Note that this will occur if the specified collection is this list, and
* it's nonempty.)
*
* 按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到该列表的末尾。<br>
* 如果在操作进行中修改了指定的集合，则此操作的行为是未定义的。<br>
* （注意，如果指定的集合是此列表，并且它是非空的，则会发生这种情况。）<br>
*
* @param c
* collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException
* if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**参数index表示在索引下标为index的节点(实际上是第index+1个节点)的前面插入。
* Inserts all of the elements in the specified collection into this list,
* starting at the specified position. Shifts the element currently at that
* position (if any) and any subsequent elements to the right (increases
* their indices). The new elements will appear in the list in the order
* that they are returned by the specified collection's iterator.
* 将指定集合中的所有元素插入到此列表中，从指定的位置开始。<br>
* 将当前位于该位置的元素（如果有的话）和随后的任何元素移动到右边（增加它们的索引）。<br>
* 新元素按照它们由指定集合的迭代器返回的顺序显示在列表中。<br>
*
* @param index
* index at which to insert the first element from the specified
* collection<br>
* 从中指定集合插入第一个元素的索引
* @param c
* collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException
* {@inheritDoc}
* @throws NullPointerException
* if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检查插入的位置是否合法
checkPositionIndex(index);
// 将集合转换为数组a
Object[] a = c.toArray();
// 保存集合大小
int numNew = a.length;
// 集合为空，直接返回
if (numNew == 0)
return false;
// 创建两个节点，前驱，后继
Node<E> pred, succ;
// 下标=链表中节点个数(链表尾部)
if (index == size) {// 如果插入位置为链表末尾，则后继为null，前驱为尾节点
succ = null;// 后继为null
pred = last;// 前驱为last
} else {// 插入位置为其他的某个位置
succ = node(index);// 寻找到该节点，后继为该节点(在index位置前插入)
pred = succ.prev;// 保存该节点的前驱节点
}
// 遍历数组
for (Object o : a) {
@SuppressWarnings("unchecked")
// 向下转型
E e = (E) o;
// 生成新节点
Node<E> newNode = new Node<>(pred, e, null);
// 如果把o插入到链表头部(在第一个元素之前插入(索引为0的节点))
if (pred == null)
first = newNode;// 更新头节点
else// 插入链表中间或尾部
pred.next = newNode;// 让index位置的前一个节点的next指向包含o的新节点
pred = newNode;// 向后移动，把newNode节点作为前驱节点
}
if (succ == null) {// 插入链表尾部，更新尾节点
last = pred;
} else {// 插入链表首部，中间位置
pred.next = succ;
succ.prev = pred;
}
// 修改实际元素个数
size += numNew;
// 修改次数+1
modCount++;
return true;
}
在上面还调用了node()方法
/**
* Returns the (non-null) Node at the specified element index.<br>
* 返回指定元素索引处的（非空）节点。
*/
Node<E> node(int index) {
// assert isElementIndex(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;// 返回该节点
}
}
遍历最多一半节点就能找出指定索引的节点。
举个栗子：
List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.addAll(0, Arrays.asList(2, 3, 4, 5));
图例：
LinkedList常用方法
add(E e)方法
源码：
/**add()方法用于向LinkedList中添加一个元素，并且添加到链表末尾。
* Appends the specified element to the end of this list.<br>
* 默认将指定的元素追加到此列表的末尾。
* <p>
* This method is equivalent to {@link #addLast}.
*
* @param e
* element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 添加到链表末尾
linkLast(e);
return true;
}
具体添加的逻辑由linkLast()方法完成。
/**
* Links e as last element.<br>
* 链接e作为最后一个元素。
*/
void linkLast(E e) {
// 保存尾节点，l为final类型，不可更改
final Node<E> l = last;
// 新生成节点的前驱是l，后继为null
final Node<E> newNode = new Node<>(l, e, null);
// 重新赋值尾节点
last = newNode;
if (l == null)// 尾节点为空
first = newNode;// 赋值头节点
else// 尾节点不为空
l.next = newNode;// 尾节点的后继节点为新生成的节点
// 链表长度+1
size++;
// 修改次数+1
modCount++;
}
举个栗子
List<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);
首先调用无参构造函数，然后添加5,6
链表示意图：(感谢原作者制作的图)
addFirst(E e)方法
源码：
/**
* Inserts the specified element at the beginning of this list.<br>
* 在此列表开头插入指定的元素。
*
* @param e
* the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Links e as first element.<br>
* 链接e作为第一个元素。
*/
private void linkFirst(E e) {
// f指向头结点
final Node<E> f = first;
// 生成一个新节点e,其前向指针为null，后向指针为f
// 构造一个前驱为null，后继为f的node对象
final Node<E> newNode = new Node<>(null, e, f);
// first指向新生成的节点，f保存着老的头结点信息
// 第一个元素指向刚刚构造出来的对象
first = newNode;
// 如果这个链表为空，则第一个元素也是最后一个元素，否则把以前的前驱指向刚刚构造出来的元素
if (f == null)
last = newNode;// 如果f为null，则表示整个链表目前是空的，则尾节点也指向新节点
else
f.prev = newNode;
// 列表大小+1
size++;
modCount++;
}
addLast(E e)方法
源码：
/**linkLast()方法在上面已经讲过，不再赘述。
* Appends the specified element to the end of this list.<br>
* 将指定的元素追加到此列表的末尾。
*
* <p>
* This method is equivalent to {@link #add}.
*
* @param e
* the element to add
*/
public void addLast(E e) {
linkLast(e);
}
get(int index)方法
源码：
/**node()方法在上面已经讲过，不再赘述。
* Returns the element at the specified position in this list.<br>
* 返回此列表中指定位置的元素。
*
* @param index
* index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException
* {@inheritDoc}
*/
public E get(int index) {
// 下标参数校验
checkElementIndex(index);
//返回指定元素索引处的（非空）节点。
return node(index).item;
}
getFirst()方法
源码：
/**直接获取链表头部
* Returns the first element in this list.<br>
* 返回此列表中的第一个元素。
*
* @return the first element in this list
* @throws NoSuchElementException
* if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
getLast()方法
源码：
/**直接获取链表尾部，并返回
* Returns the last element in this list.<br>
* 返回此列表中的最后一个元素。
*
* @return the last element in this list
* @throws NoSuchElementException
* if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
poll()方法
源码：
/**
* Retrieves and removes the head (first element) of this list.<br>
* 检索并删除此列表的头（第一个元素）。
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E poll() {
// 首先获取表头
final Node<E> f = first;
// 如果为null返回null，不为null，调用unlinkFirst
return (f == null) ? null : unlinkFirst(f);
}
/**
* Unlinks non-null first node f.<br>
* 取消链接非空第一个节点f。
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 获取当前节点的数据
final E element = f.item;
// 获取当前节点的后继节点
final Node<E> next = f.next;
// 节点数据和后继节点置为null，加快GC回收？
f.item = null;
f.next = null; // help GC
// 将后继节点更新到链表表头
first = next;
if (next == null)// 节点后继节点为null(说明链表只有一个节点)
last = null;// 链表尾节点为null
else// 后继节点不为null
next.prev = null;// 前驱置为null
// 链表长度-1
size--;
//修改次数+1
modCount++;
//返回节点数据
return element;
}
上面这几个常用方法看明白之后，其他方法应该也游刃有余了 ..
LinkedList优缺点
优点：
a. LinkedList 插入新元素和删除已有元素的开销很小，速度很快。
缺点：
a. LinkedList 不容易操作索引，因此对get的调用比较昂贵，除非调用非常接近表的端点。
ArrayList与LinkedList对比
通过之前阅读学习了ArrayList 和 LinkedList 的源码之后，我们来对比下它们之间的区别。
(网上的资料很多，不过这里还是总结一下)
1. 顺序插入
顺序插入的速度，ArrayList比较快，因为ArrayList是数组实现，一开始就new好了，往指定位置塞值就行。
LinkedList不同，每次插入都需要new一个对象，如果读对象较大，new的时间势必会长一些。
LinkedList还维护了前驱节点Node和后继节点Node，如果LinkedList钟的节点非常多，那LinkedList将比ArrayList更耗内存。
2. 数据遍历
数据遍历，网上很多测试说明，这里不再赘述。
总之：使用各自遍历效率最高的方式，ArrayList遍历效率比LinkedList效率更高。
注意：
LinkedList做插入、删除的时候，慢在寻址，快在只要改变前后Node节点的引用地址
ArrayList做插入、删除的时候，慢在数组的批量copy，快在寻址。
参考资料：
http://www.cnblogs.com/xrq730/p/5005347.html
http://www.bkjia.com/Javabc/1069146.html
http://hovertree.com/h/bjaf/l9bqickc.htm
《数据结构与算法分析-Java语言分析》