LinkedList类是List接口和Queue接口的底层实现类，它的底层通过双向链表实现，是一种线性的数据结构。
一、链表的基础知识
链表是由一系列非连续的节点组成的存储结构，简单分下类的话主要分为单向链表、单向循环链表、双向链表、双向循环链表四种。
其实LinkedList的底层就是双向链表实现的，之前一直错误的认为是单向链表= = 。 
二、结构图
LinkedList是Collection集合中的底层实现类。它主要实现了List和Queue两个接口。虽然它名字里有个”List”但他也实现了Queue队列，这点要记住。
* 继承 AbstractSequentiaList，实现了List。提供了添加、删除、修改、遍历等功能
* 实现Deque接口，提供了Queue接口队列的相关功能
* 实现Cloneable接口，重写clone( )函数，可以被复制
* 实现java.io.Serializable接口，支持序列化，能通过序列化去传输
通过结构图，我有一点一直比较迷惑，LinkedList类继承了AbstractSequentiaList类，AbstractSequentiaList类实现了List接口，那为什么LinkedList还要自己再直接实现List接口。这么做明显是做了很多重复的工作，这样有什么好处呢？
三、LinkedList类简介
1. 定义
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.SerializableLinkedList支持泛型
2. 属性
transient int size = 0;
// LinkedList底层链表的头和尾
transient Node<E> first;
transient Node<E> last;
// 链表中结点的结构
private static class Node<E> {
E item;
// 通过这里看出来LinkedList是双向链表
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
通过类的属性和Node结点的定义，我们可以发现两个很有意思的地方：
- LinkedList底层链表中，有两个链表指针，first指向链表第一个结点，end指向链表最后一个结点
- LinkedList是双向链表，结点Node类中next指向下一结点，prev指向上一节点
3. 构造函数
// 构造函数一
public LinkedList() {
}
// 构造函数二
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
一共有两个构造函数，分别构造空链表/将其他Collention构造成链表
4.api列表
// List中定义的方法
int size();
boolean isEmpty();
boolean add(E e);
void add(int index, E element);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c); //从index位置开始插入c中所有元素
boolean remove(Object o);
E remove(int index);
boolean contains(Object o);
E set(int index, E element);
E get(int index);
void clear();
boolean equals(Object o); // 在AbstractList类中实现
int indexOf(Object o);
int lastIndexOf(Object o);
Object[] toArray();
boolean contains(Object o);
// Queue中定义的方法
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// 其他
Object clone();三、源码分析
LinkedList是List和Queue的实现类，这两个类的方法LinkedList都有实现。
源码分析里我们就不把所有方法都列出分析了，只把其中值得注意、有意思的地方拿出来分析，其他的方法可以自己再去看源码。
1. 增加新元素 add( )
public boolean add(E e) {
// 在链表尾部增加新节点
linkLast(e);
return true;
}
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++;
}
// 根据索引位置添加新元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
Node<E> node(int index) {
// 由于LinkedList类中链表是双向链表，且有头尾first、last，所以按索引位置寻找结点时，从近的一头开始寻找
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;
}
}3. 添加全部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;
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（）方法在执行时，直接把原来Collection
public class Run {
public static void main(String[] args) {
List<Stack<Integer>> list = new LinkedList<>();
Stack<Integer> s1 = new Stack<>();
s1.push(1);
s1.push(2);
Stack<Integer> s2 = new Stack<>();
s2.push(3);
s2.push(4);
list.add(s1);
list.add(s2);
List<Stack<Integer>> cloneList = new LinkedList<>(list);
list.get(1).push(5);
// 此处运行结果为 5
// 说明list中Stack类变化时，listClone中一同变化，这正是因为addAll（）复制的是引用
System.out.println(cloneList.get(1).pop());
}
}3. 复制clone( )
public Object clone() {
LinkedList<E> clone = superClone();
// 将clone对象初始值均设为空
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
//调用父类的clone(),函数生成LinkedList类
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
可以看到， LinkedList的 Clone方法只是简单的将原来每个 node的 item放到克隆后的对象中，和 ArrayList的 clone方法一样， LinkedList的 Clone方法也只是浅复制，如果元素为引用类型，那么修改原 list的值会影响克隆的 list的值。
四、 总结
通过查看LinkedList源码，我们知道以下几点
linkedList本质上是一个双向链表，通过一个Node内部类实现的这种链表结构。
能存储null值
是List和Queue的实现类
基于链表的实现，觉得了它插入/删除速度快，读取速度慢