**linkedList：**linkedList是一个以双向链表实现的List，它除了作为List使用，还可以作为队列或者栈来使用。
从继承体系可以看出，linkedList实现了Cloneable和Serializable接口，说明其可以被克隆，也可以被序列化！同样的，linkedList被克隆的时候，和ArrayList一样二者均是浅拷贝。
下面进入正题 --------- 分析源码：
2、linkedLIst的基本属性transient int size = 0; //链表的头结点 transient Nodefirst; //链表的尾节点 transient Node last;
三个基本属性同股票关键字transient修饰，使其不被序列化。
3、Node内部类private static class Node{ E item; //node节点存储的元素 Node next; //后驱指针 Node prev; //前驱指针 Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
从代码中可以看出，这是双向链表的结构。
4、构造方法空参构造
public linkedList() {
}
有参构造（参数是一个Collection）
//有参构造函数 参数是一个集合
public linkedList(Collection c) {
this();
addAll(c);
}
//将指定集合中的所有元素都追加到此列表的末尾
public boolean addAll(Collection c) {
//参数有集合中元素的个数 说明是从末尾插入（具体后面代码解释）
return addAll(size, c);
}
//从指定位置开始，将指定集合中的所有元素插入此集合 注意 index是下标 代表从0开始
//总体过程是这样的 集合元素的插入是根据前驱结点的改变来进行插入的
//首先根据插入索引后继节点来算出前驱节点 然后依次进行插入 最后判断是否是从尾部插入
public boolean addAll(int index, Collection c) { //从指定位置开始，
checkPositionIndex(index); //检查index是否越界 index>=0 && index<=size
Object[] a = c.toArray(); //将集合转成Object类型的数组
int numNew = a.length; //获取该数组长度
if (numNew == 0) //如果要添加的集合没有元素的话 就返回false结束添加(不报错)
return false;
//代表要插入位置的前驱节点和后继节点
Node pred, succ;
if (index == size) { //当前要插入位置的索引（从0开始）位于链表最后一个元素处
succ = null; //后继节点置空
pred = last; //要拼接的集合前驱节点为原始链表的尾节点
} else {
//从指定位置（非尾部）添加的情况：后继节点就是index索引上的节点
succ = node(index);
pred = succ.prev; //前驱节点就是index索引上的节点的前驱节点
}
//确立了前驱和后继节点 遍历数据，将数据插入
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建节点
Node newNode = new Node<>(pred, e, null);
if (pred == null)
//空链表插入的情况
first = newNode;
else
//非空链表插入情况 将新创建的节点放入前驱节点后面
pred.next = newNode;
//更新前驱节点为最新插入节点
pred = newNode;
}
if (succ == null) { //如果是从尾部插入的，则把最后一个插入的元素置为last
last = pred;
} else { //如果不是从尾部插入的 则把尾部的数据和之前的节点连接起来
pred.next = succ;
succ.prev = pred;
}
//链表元素大小+num
size += numNew;
//被修改次数+1
modCount++;
return true;
}
//获取指定索引上的节点
Node node(int index) {
if (index < (size >> 1)) { //如果给定的index索引的值小于节点数量 说明该节点在链表的前半段
//则应该从头结点开始循环查找
Node x = first;
for (int i = 0; i < index; i++)
x = x.next; //指针移动index(索引值)个位置
return x; //将该节点内容返回
} else { //如果该索引位于链表的后一半
Node x = last; //从尾节点开始定位index的值
for (int i = size - 1; i > index; i--)
x = x.prev; //指针移动到index位置
return x; //将该节点内容返回
}
}
由两个无参构造方法得出，这是一个无界的双端队列。
5、添加元素对于双端队列的性质，添加元素的时候，一种是在队列尾部添加元素，一种是在队列首部添加元素，这两种形式在linkedList中主要是通过下面两个方法来实现的：
public void addFirst(E e) {
linkFirst(e); //头部添加
}
public void addLast(E e) {
linkLast(e); //尾部添加
}
//作为无界队列，添加元素总是会成功的
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
头部添加
private void linkFirst(E e) {
final Node f = first; //首节点
final Node newNode = new Node<>(null, e, f); //创建新节点，新节点的next是首节点
first = newNode; //让新节点作为新的首节点
if (f == null) //判断是不是第一个添加的元素
last = newNode; //如果是就把last尾节点也设置为新节点
else //如果不是第一次添加节点，就把原首节点的prev设置为新节点
f.prev = newNode;
size++; //元素个数+1
modCount++; //被修改次数+1
}
尾部添加
void linkLast(E e) {
final Node l = last; //队列尾节点
final Node newNode = new Node<>(l, e, null); //创建新节点，新节点的prev是尾节点
last = newNode; //让新节点作为新的尾节点
if (l == null) //判断是不是第一个添加的元素
first = newNode; //如果是就把first首节点也设置为新结点
else //如果不是第一次添加节点 就把原尾节点的next设置为新结点
l.next = newNode;
size++; //元素个数+1
modCount++; //被修改次数+1
}
中间指定位置添加
linkedList作为集合，需要在中间其他位置添加元素，该功能是通过下面的方法实现的：
//在指定index索引位置处添加元素
public void add(int index, E element) {
//判断是否越界 index>=0 && index<=size
checkPositionIndex(index);
if (index == size) //如果是在队列尾节点之后的一个位置
linkLast(element); //把新结点直接添加到尾节点之后
else //否则调用linkBefore()方法在中间添加节点
linkBefore(element, node(index));
}
//获取指定索引上的节点
Node node(int index) {
if (index < (size >> 1)) { //如果给定的index索引的值小于节点数量 说明该节点在链表的前半段
//则应该从头结点开始循环查找
Node x = first;
for (int i = 0; i < index; i++)
x = x.next; //指针移动index(索引值)个位置
return x; //将该节点内容返回
} else { //如果该索引位于链表的后一半
Node x = last; //从尾节点开始定位index的值
for (int i = size - 1; i > index; i--)
x = x.prev; //指针移动到index位置
return x; //将该节点内容返回
}
}
//寻找index索引位置的节点，返回指定元素索引处的（非空）节点
void linkBefore(E e, Node succ) { //在非空节点succ前插入元素e
final Node pred = succ.prev; //找到待添加节点的前置节点
//在其前驱节点和后继节点之间创建一个新节点
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode; //修改后继节点的前置指针指向新节点
if (pred == null) //判断前置节点是否为空
first = newNode; //如果为空，说明在头结点处插入元素，修改first
else //如果不为空 修改前置节点的next为新节点
pred.next = newNode;
size++; //修改集合数量+1
modCount++; //集合修改次数加1
}
linkedList在中间添加元素的方法实现原理就是，典型的双链表在中间添加元素的流程：
- 在队列首尾添加元素很高效，时间复杂度为O(1)
- 在中间添加元素比较低效，首先要先找到插入位置的节点，再修改前后的节点的指针，时间复杂度为O(n)
作为双端队列，删除元素也有两种方式，一种是对垒首删除元素，一种是队列尾部删除元素。
作为List，又要支持中间删除元素，所以删除元素一共有三个方法，分别如下：
头部删除
//头部删除元素
public E removeFirst() { //执行remove的时候 如果集合中没有元素则抛出异常
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node f) {
final E element = f.item; //首节点的元素值
final Node next = f.next; //首节点的next指针
f.item = null;
f.next = null; // help GC
first = next; //把首节点的next作为作为新的首节点
if (next == null) //如果只有一个元素，删除了，把last也置为空
last = null;
else //否则把next的前置指针置空
next.prev = null;
size--; //元素怒个数-1
modCount++; //被修改次数+1
return element; //返回删除的元素
}
尾部删除
//尾部删除元素
public E removeLast() { //执行remove的时候 如果集合中没有元素则抛出异常
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//从尾部删除元素，l代表尾节点
private E unlinkLast(Node l) {
final E element = l.item; //尾节点的元素值
final Node prev = l.prev; //尾节点的前置指针
l.item = null;
l.prev = null; // help GC
last = prev; //让前置节点成为新的尾节点
if (prev == null) //如果只有一个元素，删除了把first置为空
first = null;
else //否则把前置节点next置为空
prev.next = null;
size--; //元素数量-1
modCount++; //被修改次数+1
return element; //返回返回的元素
}
中间指定位置删除元素
public E remove(int index) {// 删除中间index处的节点
checkElementIndex(index);// 检查是否越界
return unlink(node(index));// 删除指定index位置的节点
}
E unlink(Node x) {
final E element = x.item; //获取x的元素值
final Node next = x.next; //x的后置节点
final Node prev = x.prev; //x的前置节点
if (prev == null) { //如果前置节点为空 说明是首节点，让first指向x的后置节点
first = next;
} else { //否则修改前置节点的next为x的后继节点
prev.next = next;
x.prev = null; //x的前驱置为空
}
if (next == null) { //如果后置节点为空，说明是尾部节点，让last指向prev
last = prev;
} else { //否则修改后置节点的prev为x的前驱节点
next.prev = prev;
x.next = null; //x的后继置为空
}
x.item = null; //清空x的元素值，帮助GC
size--; //元素个数-1
modCount++; //被修改次数+1
return element; //返回删除的呀u盛怒值
}
7、修改元素
根据索引修改元素很简单：
public E set(int index, E element) {
checkElementIndex(index); //检查索引是否合法 index>=0 && index x = node(index); //获取指定索引位置的元素
E oldVal = x.item;
x.item = element;
return oldVal;
}
8、可以作为队列
另外，因为linkedList本身除了继承于List，还继承于**Deque，**说明其也具有队列的peek()，poll()与其类似的就是pollFirst()，pollLast()，peekLast()，peekFirst()等，其实现原理相同，这里简单列举两个：
// poll的时候如果没有元素返回null
public E pollFirst() {
final Node f = first;
return (f == null) ? null : unlinkFirst(f);
}
// poll的时候如果没有元素返回null
public E pollLast() {
final Node l = last;
return (l == null) ? null : unlinkLast(l);
}
删除元素的三种方法都是典型的双链表删除元素的方法，大致流程如下图所示：
- 在队列首尾删除元素很高效，时间复杂度为O(1)
- 在中间删除元素比较低效，首先要找到删除位置的节点，再修改前后指针，时间复杂度为O(n)
linkedList是双端队列，双端队列可以作为栈使用。
其也具有如下方法：
// 弹出末尾元素
public E pop() {
// 队列的头元素就是栈的末尾元素
return removeFirst();
}
// 入栈
public void push(E e) {
// 队列的头元素就是栈的末尾元素
addFirst(e);
}
10、总结
- linkedList是一个以双向链表实现的List
- linkedList还是一个双端队列，具有队列、双端队列、栈的特性
- linkedList再队列首尾添加、删除元素非常高效，时间复杂度为O(1)
- linkedList再中间添加、删除元素比较低效，时间复杂度为O(n)
- linkedList不支持随机访问，所以访问非队列首尾的元素比较低效
- linkedList再功能上等于ArrayList+ArrayDeque；
ArrayList代表了List的典型实现，linkedList代表了Deque的典型实现，同时linkedList也实现了List。
11、扩展linkedList的并发修改异常
举例：
@Test
public void test02(){
linkedList linkedList= new linkedList();
linkedList.add("aaa");
linkedList.add("bbb");
linkedList.add("ccc");
Iterator iterator=linkedList.iterator();
while (iterator.hasNext()){ //使用迭代器遍历的时候
linkedList.add("eee");
System.out.println(iterator.next());
}
}
在使用迭代器遍历的时候，又进行改动链表结构，就会出现并发修改异常错误：
java.util.ConcurrentModificationException at java.util.linkedList$ListItr.checkForComodification(linkedList.java:966) at java.util.linkedList$ListItr.next(linkedList.java:888) at com.linkedList1.test02(linkedList1.java:22) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
我们来研究下异常产生的原因：
首先，我们从迭代器linkedList.iterator();入手，点进去看源码，逐层点击，进入AbstractList类中，可以看到如下代码：
public ListIteratorlistIterator(final int index) { rangeCheckForAdd(index); return new ListItr(index); }
我们点进去返回的ListItr(index)查看：
//这里的modCount=3，因为我们初始化linkedList集合的时候为其添加了三个元素 //分别是：aaa bbb ccc //令期望修改次数等于链表修改的次数 private int expectedModCount=modCount; //所以现在expectedModCount再执行完linkedList.iterator()；之后其预期修改次数是3
当执行完linkedList.iterator();之后进入while循环，循环条件是iterator.hasNext()，之后进入循环体内部执行add添加操作，调用：
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l = last;// 队列尾节点
final Node newNode = new Node<>(l, e, null);// 创建新
last = newNode;// 让新节点成为新的尾节点
if (l == null)// 判断是不是第一个添加的元素
first = newNode;// 如果是就把first也置为新节点
else// 否则把原尾节点的next指针置为新节点
l.next = newNode;
size++;// 元素个数加1
modCount++;// 这里再加1后，实际链表修改次数由3--->变为4
}
add添加操作完成后，执行输出语句中的iterator.next()，进入next()源码，发现：
public E next() {
// 检查链表预期修改次数和实际链表修改次数是否匹配
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
final void checkForComodification() {
// 这里实际修改次数4和期望修改次数不相等
if (modCount != expectedModCount)
// 抛出并发修改异常
throw new ConcurrentModificationException();
}
解决方案：
// 解决方案：使用 Iterator 换用 ListIterator迭代器
ListIterator listIterator = linkedList.listIterator()
while (listIterator.hasNext()){
listIterator.add("eee");// 用listIterator为集合添加元素
System.out.println(iterator.next());
}
输出结果（正常）：
aaa bbb ccc
listIterator的listIterator()和原来的iterator()基本相同，而其之所以可以解决并发修改异常原因在于，listIterator.add("eee")该代码段，其添加元素的流程如下：
public void add(E e) {
// 添加之前先检查是否有并发修改异常，这时候预期修改次数和实际修改次数还是相等的，都是3
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);// 执行完成后modCount++变为4
nextIndex++;
// 重点就在于此：当执行完添加后，将预期修改次数也+1，这样就能保证其与实际修改次数同步+1,二者目前都为4
expectedModCount++;
}
