注：博主java集合框架源码剖析系列的源码全部基于JDK1.8.0版本。
在实际项目中LinkedList也是使用频率非常高的一种集合，本博客将从源码角度带领大家学习关于LinkedList的知识。
一LinkedList类的定义：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
从上述代码可以看到：LinkedList继承自AbstractSequentialList同时实现了List，Deque，Cloneable与Serializable接口，所以LinkedList可以当作双端队列使用。
二LinkedList类一些重要属性：
transient int size = 0;
transient Node<E> first;//指向第一个节点的指针
transient Node<E> last;//指向最后一个节点的指针
从这里可以看到LinkedList全部操作是基于Node数据结构的，而Node是LinkedList的一个内部类，本质上是一个双向链表，即LinkedList底层是基于双向链表实现的，因此LinkedList具备较好的插入，删除的能力。Node类定义如下：
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;
}
}
三LinkedList内部实现原理：我们先来看一下LinkedList的构造器
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
可以看到在构造器重调用了addAll(c),我们来看一下addAll的源码：
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;//pred表示前驱节点，succ表示后继节点
if (index == size) {// 如果插入位置为链表末尾，则后继为null，前驱为尾结点
succ = null;
pred = last;
} else {
succ = node(index);//调用node()函数找到下标为index的结点
pred = succ.prev;//保存该结点的前驱
}
for (Object o : a) {//遍历数组的同时将数组中的元素转化为Node类型插入到恰当位置
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)// 表示在第一个元素之前插入(索引为0的结点)
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,c)该方法实现的功能即是在index位置处插入Collection集合c中全部的元素，可以看到插入操作之前先将集合c转换为了数组结构，然后再将数组中的元素转化为Node节点插入的，同时可以看到在该函数中调用了node函数，node函数源码如下：
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 判断插入的位置在链表前半段或者是后半段
if (index < (size >> 1)) {// 当index < size/2时，插入位置在前半段
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;
}
}
它的作用就是返回一个不为null的节点的根据传入的位置参数index，可以看到该函数首先会通过index < (size >> 1)这个语句来判断查询的index位于前半段还是后半段，结点在前半段则从头开始遍历，在后半段则从尾开始遍历，这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。提高了查找效率。
即当创建一个用集合参数初始化的LindedList的时候，LindedList的内部是先将该集合转化为数组，然后然后再将数组中的元素转化为Node节点插入从而构造出一个元素为集合c的LinkedList。
四LinkedList一些重要的函数：
1. add函数
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
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++;
}
从上述代码可以看到add函数实际上是调用的LinkLast(E)函数，即add函数添加一个元素到LinkedList中是添加到linkedList的末尾。
2get函数
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
可以看到get函数实际上是调用的node函数，即返回一个不为null的节点的根据传入的位置参数index。
3getFirst/getLast
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
因为first节点始终指向的是LinkedList中的第一个节点，所以直接返回first.item，同理last节点始终指向的是LinkedList中的最后一个节点，所以直接返回last.item。
4remove函数
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
将元素o从集合LinkedList中删除，其中调用到了unLink()函数，该函数用来将指定的结点从链表中断开。
五：总结：
1LinkedList的内部是基于双向循环链表实现的，双向循环链表的定义为Node，它是LinkedList的一个内部类。
2当用一个集合作为参数来构造一个LinkedList时，其内部是是先将该集合转化为数组，然后然后再将数组中的元素转化为Node节点插入从而构造出一个元素为集合c的LinkedList。
3可以看到LinkedList中的方法都未使用synchronized关键字修饰，即LinkedList是非同步的，如果要创建一个同步的LinkedList则需要使用Collections.synchronizedList函数来进行构造：即List list = Collections.synchronizedList(new LinkedList(...));
3LinkedList实现了Deque，因此LinkedList可以作为双端队列使用，当需要使用队列结构时，可以考虑LinkedList。
4LinkedList允许重复元素存在，因为在add元素的过程中不存在HashMap中put时判重替换的过程，只是进行简单的插入操作。