一、源码解析
<span style="font-size:14px;"><span style="font-family:SimHei;font-size:10px;">public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable</span></span>
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。
2、LinkedList数据结构原理
LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：
既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：
3、私有属性
LinkedList中之定义了3个属性：
<span style="font-size:14px;"><span style="font-family:SimHei;font-size:10px;">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;
</span></span>
java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。
fist是双向链表的头节点，last是链表尾节点,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。size是双向链表中节点实例的个数。
首先来了解节点类Node类的代码。
<span style="font-size:14px;"> 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;
}
}</span>
4、构造方法
LinkedList提供了两个构造方法。
第一个构造方法不接受参数，将first实例的previous和next全部指向自身实例（注意，这个是一个双向循环链表，如果不是循环链表，空链表的情况应该是节点的前一节点和后一节点均为null），这样整个链表其实就只有一个节点，用于表示一个空的链表。
执行完构造函数后，header实例自身形成一个闭环，如下图所示：
第二个构造方法接收一个Collection参数c，调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中。
5、元素添加
<span style="font-size:14px;">public boolean addAll(int index, Collection<? extends E> c) {
// 插入位置超过了链表的长度或小于0，报IndexOutOfBoundsException异常
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
// 若需要插入的节点个数为0则返回false，表示没有插入元素
if (numNew == 0)
return false;
// 保存index处的节点。插入位置如果是size，则在头结点前面插入，否则在获取index处的节点插入
// 获取前一个节点，插入时需要修改这个节点的next引用
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// 按顺序将a数组中的第一个元素插入到index处，将之后的元素插在这个元素后面
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// 结合Node的构造方法，这条语句是插入操作，相当于C语言中链表中插入节点并修改指针
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode; // 插入节点后将前一节点的next指向当前节点，相当于修改前一节点的next指针
pred = newNode; // 相当于C语言中成功插入元素后将指针向后移动一个位置以实现循环的功能
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew; // 修改size
modCount++; //否则，插入对象，链表修改次数加1
return true;
}</span>
下面说明双向链表添加元素的原理:
添加数据：add()
<span style="font-size:14px;"> /**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index); // 插入位置超过了链表的长度或小于0，报IndexOutOfBoundsException异常
if (index == size)
linkLast(element); // 如果相等，则从最后的节点插入
else
linkBefore(element, node(index)); // 按顺序将a数组中的第一个元素插入到index处，将之后的元素插在这个元素后面
}
/**
* e ：元素数据;succ：查找到目标的顺序元素
*/
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); //创建新的节点newNode
succ.prev = newNode; //目标元素的父节点设置成新节点
if (pred == null)
first = newNode; //第一个节点
else
pred.next = newNode; //目标元素的父节点的下一个节点设置成新节点
size++;
modCount++;
}</span>
addBefore(E e,Node<E> succ)先通过Node的构造方法创建e的节点newNode（包含了将其下一个节点设置为node，上一个节点设置为node.previous的操作，相当于修改newnode的“指针”），之后修改插入位置后newnode的前一节点的next引用和后一节点的previous引用，使链表节点间的引用关系保持正确。之后修改和size大小和记录modCount，然后返回新插入的节点。
下面分解“添加第一个数据”的步骤：
第一步：初始化后LinkedList实例的情况：
第二步：初始化一个预添加的Node实例（newNode）。
final Node<E> newNode = new Node<>(pred, e, succ);
第三步：调整新加入节点和头结点的前后指针。
6、删除数据remove()
几个remove方法最终都是调用了一个私有方法：unlink(Node<E> x)，只是其他简单逻辑上的区别。下面分析unlink(Node<E> x)方法。
<span style="font-size:14px;">public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item; // 保留将被移除的节点e的内容
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next; // 将前一节点的next引用赋值为e的下一节点
x.prev = null; // 解除了e节点对前后节点的引用
}
if (next == null) {
last = prev;
} else {
next.prev = prev; // 将e的下一节点的previous赋值为e的上一节点
x.next = null; // 解除了e节点对前后节点的引用
}
x.item = null; // 将被移除的节点的内容设为null
size--;
modCount++;
return element;
}</span>
7、数据获取get()
Get(int)方法的实现在remove(int)中已经涉及过了。首先判断位置信息是否合法（大于等于0，小于当前LinkedList实例的Size），然后遍历到具体位置，获得节点的业务数据（element）并返回。
注意：为了提高效率，需要根据获取的位置判断是从头还是从尾开始遍历。
<span style="font-size:14px;"> /**
* // 获取双向链表中指定位置的节点
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 获取index处的节点。
// 若index < 双向链表长度的1/2,则从前先后查找;
// 否则，从后向前查找。
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;
}
}</span>
下面自定义LinkedList,便于更好的理解LinkedList内部数据结构；
<span style="font-size:14px;">public class CustomLinkeList<E> {
private transient int size;
private transient Node<E> firstNode;
private transient Node<E> last;
public CustomLinkeList() {
super();
}
public void add(E element){
Node<E> node=null;
if(firstNode==null){ //没有值
node=new Node<E>(element, null, null);
firstNode=node;
last=node;
}else{
node=new Node<E>(element, last, null);
last.next=node;
last=node;
}
size++;
}
public void add(int index,E element){
rangeCheck(index);
//查找到需要插入的Node位置
Node<E> temp=findNode(index);
if(temp!=null){
Node<E> up = temp.prev;
Node<E> newNode = new Node<E>(element,up, temp);
up.next=newNode;
temp.prev=newNode;
size++;
}
}
public void remove(int index){
rangeCheck(index);
//查找到需要插入的Node位置
Node<E> temp=findNode(index);
if(temp!=null){
Node<E> up = temp.prev;
Node<E> dowm = temp.next;
up.next=dowm;
dowm.prev=up;
size--;
}
}
private Node<E> findNode(int index) {
Node<E> temp=null;
if(firstNode!=null){
int _point=size>>1 ;//二分查找
if(index<_point){ //往前查找
temp = firstNode;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
}else{
temp=last;
for (int i = size-1; i > index; i--) {
temp = temp.prev;
}
}
}
return temp;
}
private void rangeCheck(int index){
if(index<0 || index>=size){
try {
throw new Exception("越界");
} catch (Exception e) {
e.printStackTrace();
}
}
}
/**
* 查看元素
* @param index
* @return
*/
public Object get(int index){
rangeCheck(index);
//查找到需要插入的Node位置
Node<E> temp=findNode(index);
if(temp!=null){
return temp.element;
}
return null;
}
public int size(){
return size;
}
class Node<E>{
private E element;
private Node<E> prev;
private Node<E> next;
public Node(E element, Node<E> prev, Node<E> next) {
super();
this.element = element;
this.prev = prev;
this.next = next;
}
}
public static void main(String[] args) {
CustomLinkeList<String> list=new CustomLinkeList<String>();
list.add("aaa");
list.add("bbb");
list.add(1,"BBBB");
list.add("ccc");
list.add("ddd");
list.add("eee");
//list.remove(1);
System.out.println(list.get(1));
System.out.println(list.size());
}
}
</span>