本笔记研究LinkedList源码。LinkedList从名字都可以看出，这是一个基于链表实现的容器，只要是基于链表实现的，那肯定都非常简单(链表跟红黑树相比，简单的掉渣)；同时，由于LinkedList实现了Deque接口，所以他具有队列的一些 特性。在我看来，LinkedList就是记录了链表的头结点和尾节点，而此链表的节点有记录了前驱节点和后继节点，所以在操作链表的时候，比如插入，移除，获取元素等，既可以从表头开始，右可以从表尾开始，这就是LinkedList具有队列的部分特性的原因。好了，不啰嗦了，123，上源码：
//注意实现了Deque接口；Deque接口是Queue的子接口，我们知道Queue是
//一种队列形式,而Deque则是双向队列,它支持从两个端点方向检索和插入元素
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//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;
/**
* Constructs an empty list.
*
* 无参构造函数
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*
* 基于一个Collection对象构造一个LinkedList
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
//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;
}
}
}
国际惯例，先从添加元素的方法开始分析:
/**
* Appends the specified element to the end of this list.
*
* <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})
*
* 添加元素e
*/
public boolean add(E e) {
//简单的调用linkLast；同时也可以看出
//，添加元素，默认是添加到链表的尾部的
linkLast(e);
return true;
}
add方法的核心是linkLast，下面分析：
/**
* Links e as last element.
*
* 传入一个元素e，把它放在链表尾部
*/
void linkLast(E e) {
//先记录尾节点
final Node<E> l = last;
//根据e创建一个节点newNode，第一个参数代表他的前驱节
//点是原来的尾节点，他自身就成了尾节点；最后一个参数代表
//他的后继节点是空；这很好理解，尾节点肯定是没有后继节点的
final Node<E> newNode = new Node<>(l, e, null);
//将LinkedList的尾节点指向刚才创建的节点
last = newNode;
//如果原来的尾节点是空，那么说明链表不存在
//此时刚刚创建的节点不光是尾结点，还是头节点
if (l == null)
first = newNode;
//如果链表存在，那么将原来的尾节点的后继节点指向刚刚创建的节点
else
l.next = newNode;
//LinkedList元素个数+1
size++;
//modCount自增
modCount++;
}
整个添加元素的过程还是蛮简单的，就是改变链表中节点的指向。
既然有add，就有get:
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*
* 此方法需要传入一个索引index，代表要返回链表哪个位置的元素
*/
public E get(int index) {
//检查索引是否越界
checkElementIndex(index);
//调用node方法查找指定的节点，然后返回他的数据
return node(index).item;
}
get方法的核心是node(int index)，下面分析：
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//类似于二分查找；如果索引index小于元素个数的一半，那么从头
//结点开始查找，否则从尾节点开始查找，这样的判断能提高查找效率
if (index < (size >> 1)) {
//先保存头结点
Node<E> x = first;
//for循环从头结点开始往死里遍历链表
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;
}
}
除了add和get方法，再研究下其他几个方法：
/**
* Links e as first element.
*
* 传入一个元素e，把它放在链表头部
*/
private void linkFirst(E e) {
//把原来的头结点赋值给f
final Node<E> f = first;
//根据e创建一个节点newNode，第一个参数代表他没有前驱节点他
//自身就是头结点；最后一个参数代表他的后继节点是原来的头结点
final Node<E> newNode = new Node<>(null, e, f);
//把刚创建的节点赋值给头结点
first = newNode;
//如果原来的头节点为空，说明链表不存在，此
//时刚刚创建的节点不但是头节点，还是尾节点
if (f == null)
last = newNode;
//如果链表存在，那么将原来的头结点的前驱节点指向刚刚创建的节点
else
f.prev = newNode;
//LinkedList元素个数+1
size++;
//modCount自增
modCount++;
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*
* 从peek这个名字就可以看出，这是类似于栈的方法，返回的是栈顶的元
* 素；在这里返回的是链表头结点的数据，不删除节点，非常简单，不啰嗦
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*
* 从poll这个名字就可以看出，这是类似于队列的方法，返回的是队列队头的节点，并删除节点；
* 这里的实现就是unlinkFirst，过程分析过，删除头结点，并返回头结点的数据，简单，不啰嗦了
*/
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*
* 将元素添加到链表头部，调用的是linkFirst(分析过)
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*
* 将元素添加到链表尾部，调用的是linkLast(分析过)
*/
public void addLast(E e) {
linkLast(e);
}
/**
* Unlinks non-null first node f.
*
* 删除头节点，f就是一个非空的头结点
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//首先拿到头节点的值
final E element = f.item;
//拿到头节点的后继节点，也就是链表的第二个节点
final Node<E> next = f.next;
//将头节点的值置空
f.item = null;
//将头节点的后继节点置为空，便于垃圾回收;因为上面
//已经保存了第二个节点的引用，所以这里置空是没毛病的
f.next = null; // help GC
//将第二个节点置为新的头结点
first = next;
//如果第二个节点为空，说明此链表就一个节点
//；删除了唯一的节点后，链表为空，没有尾节点
if (next == null)
last = null;
//因为第二个节点将成为新的头结点，所以他是没有头结点的
else
next.prev = null;
//LinkedList元素个数 - 1
size--;
//modCount自增
modCount++;
//返回头结点数据(第一步就保存了这个数据)
return element;
}
/**
* Unlinks non-null last node l.
*
* 删除尾节点，l就是一个非空的尾结点
* 道理同上，不啰嗦了
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null node x.
*
* 删除一个指定的非空的节点，类似于上面两个方法，非常简单，不啰嗦
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
LinkedList的本质是操作链表，非常简单，其他的方法就不啰嗦了，上一篇笔记分析了ArrayList的迭代，接下来也研究下LinkedList的迭代；ArrayList的迭代比较简单，就是把游标指向下一个数组索引，然后获取数组元素；那么LinkedList是怎么实现的呢？
private class ListItr implements ListIterator<E> {
//最近被迭代的节点
private Node<E> lastReturned;
//下一个被迭代到的节点
private Node<E> next;
//下个节点的索引
private int nextIndex;
//迭代前肯定要判断modCount，防止多线程操作LinkedList
private int expectedModCount = modCount;
//index是创建迭代器的时候传进来的，第一次迭代的时候index是0
ListItr(int index) {
// assert isPositionIndex(index);
//如果迭代的索引等于元素个数，那么下个迭代的节点就是空
//("游标"都指向最后一个元素了，没有什么可以迭代的了)
//否则调用node方法去获取index上的节点，这个方法分析过
next = (index == size) ? null : node(index);
//下个迭代节点的索引，当调用next的时候,nextIndex会自增的
nextIndex = index;
}
//迭代的条件，当然是迭代的索引不能大于元素个数
public boolean hasNext() {
return nextIndex < size;
}
//真正迭代的方法
public E next() {
//检查modCount，防止多线程操作LinkedList
checkForComodification();
//如果迭代索引越界，就抛出异常
if (!hasNext())
throw new NoSuchElementException();
//把next赋值给lastRetrened，最终返回
lastReturned = next;
//将next指向下个节点
next = next.next;
//迭代索引自增
nextIndex++;
//返回结果
return lastReturned.item;
}
//迭代条件，不过这里是从尾节点开始迭代
public boolean hasPrevious() {
return nextIndex > 0;
}
//之前分析过，LinkedList具有队列的部分特性，既可以
//从头结点操作他也可以从尾节点操作他，上面的迭代过程
//是从头结点开始迭代，这里是从尾节点开始迭代LinkedList
public E previous() {
//检查modCount，防止多线程操作LinkedList
checkForComodification();
//如果迭代到了头结点，那么应该停住，否则就抛出异常给你尝尝
if (!hasPrevious())
throw new NoSuchElementException();
//将next赋值给lastReturned；如果next是null，说明是第一次迭代
//这时候就把尾节点赋值给next，否者就把next的前驱节点赋值给next
lastReturned = next = (next == null) ? last : next.prev;
//索引自减，如果从尾节点开始迭代，那么整个索引的初值是链表长度
nextIndex--;
//返回节点数据
return lastReturned.item;
}
}
LinkedList基本上就是这么多内容了吧，要想理解带有Linked类型的集合，链表肯定是需要理解的。
最近两篇笔记研究了ArrayList和LinkedList的源码，从源码可以看出，他们底层的数据存储方式是不一样的：
ArrayList采用数组的方式存储数据，数组的查找、更新效率很高，因为数组保存了首元素的地址，传入一个索引，就可以根据 首地址 + 元素占用空间*索引 的方式找到该数据；而插入和删除效率就比较低了，因为数组元素之间的地址是连续的，一旦删除某个元素，为了保证这种连续性，需要把被删除元素后面的元素往前移动，这种移动是个耗时操作；数组 的插入过程也比较耗时，因为可能涉及到扩容，扩容也是需要操作整个数组的内存的。
LinkedList采用链式方式存储数据。采用这种方式存储数据，查找、更新效率较低(相对于数组)，因为需要遍历链表；但是插入和删除相对于数组来说比较高效，他只需要遍历链表，无需移动元素。
