LinkedList源码解析
先对LinkedList的特性进行一个概述：
（1）LinkedList底层实现为双向循环链表。链表的特点就是插入删除数据快，而查询数据慢。
（2）因为使用链表的原因，所以不存在容量不足的问题，没有扩容机制。
（3）从后面的源码分析中我们也可以看出，LinkedList支持null并且LinkedList没有同步机制。
（4）LinkedList直接继承于AbstractSequentialList，同时实现了List接口，也实现了Deque接口。
AbstractSequentialList为顺序访问的数据存储结构提供了一个骨架类实现，如果要支持随机访问，则优先选择AbstractList类继承。LinkedList 基于链表实现，因此它继承了AbstractSequentialList。本文原创，转载请注明出处：[http://blog.csdn.net/seu_calvin/article/details/53012654]
LinkedList的数据存储格式：
private static class Node<E>{
E item;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev,E item,Node<E> next){
this.prev = prev;
this.item = item;
this.next = next;
}
}
LinkedList中定义了三个临时的变量
transient int size = 0;//链表大小
transient Node<E> first;//头节点
transient Node<E> last; //尾节点
LinkedList的构造方法有两种，如下：
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
可以看到在有参的构造方法中，首先先调用了无参的构造方法，然后调用addAll()方法，下边讲解下这个方法，首先判断第一个参数index的大小，如果大于size或者小于0则抛出越界异常，然后设置了两个Node类型的量，pred表示插入集合C的头节点的前一个节点，succ表示插入集合C的尾节点的后一个节点，如果index==size,说明插入的位置是在链表的尾部，那么头结点就是原来的last,尾节点就是Null;否则，则是中间插入的方式，那么首先将该节点的头尾节点分别赋值给pred和succ，然后使用一个for循环输出集合C中的数据，每个都使用Node进行包装，这部分只要注意pred在里边类似于指针的作用，每次循环，pred 都将指向下一个节点；这样循环到最后，还要对插入位置进行判断，如果succ为Null,则是在链表尾插入，则直接设置last=pred,否则将pred.next=succ;succ.prev = pred;对插入节点尾部进行一个头尾的指针指向。
LinkedList的一些内部方法，仅供内部方法调用
private void linkFirst(E e)//插入头结点
void linkLast(E e)//插入尾节点
void linkBefore(E e, Node<E> succ)//在某个节点前插入
private E unlinkFirst(Node<E> f)//删除头结点
private E unlinkLast(Node<E> l)//删除尾节点
E unlink(Node<E> x)//删除某个节点
//插入头结点
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//插入尾节点
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//在某个节点前插入
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
//删除头结点
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;
size--;
modCount++;
return element;
}
//删除尾节点
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;
}
//删除某个节点
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;
}
注意一个点，添加和删除节点，都会对first和last进行相关的处理工作，并且这些方法中创建的节点都是final的。
LinkedList常用的一些方法：
public E getFirst()
public E getLast()
public E removeFirst()
public E removeLast()
public void addFirst(E e)
public void addLast(E e)
这六个方法是LinkedList中对于首尾节点的操作方法，直接调用上面的内部方法就能够解决了。
下面介绍几个其他的方法：
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;
}
}
node()方法是根据传入的索引，返回具体的节点，这个方法有意思，他不是死脑筋的从头遍历到尾，他首先将index和size的中间值进行了判断，如果index<size的中间值，则只需遍历左半边的，如果index>size的中间值，则遍历右半边。这样在遍历右半边的时候，将大大的提高程序的执行效率。
public int indexOf(Object o)和方法 public int lastIndexOf(Object o)类似，前一个是从头找到跟o数据匹配的节点索引，后一个是从尾找到跟o数据匹配的节点索引，这边就将第一个方法吧，代码如下：
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
看到这段代码有没有点熟悉感，没错，先进行了o是否是空值的判断，空值用==进行比较，非空值用equals进行比较，最后返回Index的值大小。
对List的其他相关方法总结一下：
public boolean contains(Object o)//集合中是否包含o数据
public boolean add(E e)//从尾节点新增一个节点，数据为e
public boolean remove(Object o)//从头开始，删除一个集合中数据为o的节点
public void clear()//清空集合所有的节点
public E get(int index)//获取索引位置为Index的数据信息
public E set(int index, E element)//设置Index位置的节点数据为element
public void add(int index, E element)//在index位置新增一个节点数据为element
public E remove(int index)//删除Index位置的节点
public boolean removeFirstOccurrence(Object o)//里边调用的是remove(Object o)的方法，跟这个方法作用相同
public boolean removeLastOccurrence(Object o)//从尾开始，删除一个集合中数据为o的节点。
关于list的方法方面讲完了，下面介绍LinkedList实现deque和stack的方法：
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E element() {
return getFirst();
}
peek()方法和element()方法都是 获取但不移除第一个元素，区别在于，如果第一个元素为空，peek返回Null,而element抛出异常
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E remove() {
return removeFirst();
}
poll()方法和remove()方法都是获取并且会移除第一个元素，区别在于，如果第一个元素为空，poll()返回Null,而remove抛出异常。
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
前两个方法获取头尾节点的值但不移除头尾节点，如果为空则返回null,
后两个方法获取头尾节点的值，并且会移除头尾节点，如果为空则返回null
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
这两个方法是属于stack方面的，入栈和出栈，符合先进先出的规则，如果遇到空元素则抛出异常
这两天研究了ArrayList和LinkedList的源码，下面对这两个集合类进行对比
共同点：
1、都是线程不安全的集合
2、都支持null值
3、都实现了List接口
不同点：
1、ArrayList的底层是用数组实现的，每次增加数据都要考虑扩容的情况，LinkedList底层是通过链表实现的，不需要考虑扩容的情况
2、LinkedList 基于链表实现，便于顺序访问，它继承了AbstractSequentialList。而ArrayList支持随机访问，继承了AbstractList类
3、通过源码我们知道，如果要对数据进行查询，那么ArrayList比较合适，因为ArrayList是通过数组实现的，那么只需要获取索引就可以获取该值，但是LinkedList需要从头或尾遍历到值才行；如果要对数据进行增删操作，则LinkedList比较合适，通过代码我们知道，ArrayList需要通过System.arraycopy移动数组来实现，而LinkedList只需要修改前后的指针指向就可以完成增删操作，所以在增删操作上，LinkedList比较合适，当然如果是在头部或者尾部，二者的效率没有多大的区别
参考链接：
https://blog.csdn.net/wangbiao007/article/details/52539061
https://blog.csdn.net/seu_calvin/article/details/53012654
