---

该篇博客不适合小白，只做针对性的api源码解析，以及适合我自身的案例研究

---

1. 使用多个线程往LinkedList中添加元素

   for (int i = 0; i < 50; i++) { new Thread(()->{ list.add(UUID.randomUUID().toString().substring(0,8)); System.out.println(list); },String.valueOf(i)).start(); }

2. 故障现象

   Exception in thread "3" java.util.ConcurrentModificationException

   我们知道LinkedList是线程不安全的，当多线程操作时，线程操作迭代器的同时其他线程改变了元素的值就会产生ConcurrentModificationException异常，ConcurrentModificationException是在操作Iterator时抛出的异常

3. 故障原因

   从前一篇的ArrayList中的解析中得出，我们最终都会经过迭代器中的代码检查modCount 和 expectedModCount的值相不相等

   所以我们这里就不追踪栈异常信息，而直接看看源码中的操作是如何让modCount 和expectedModCount不相等的

   1. 首先找出问题的关键代码

      private Node<E> lastReturned; //最近一次返回的节点，也是当前持有的节点 private Node<E> next; //对下一个元素的引用 private int nextIndex; //下一个节点的索引 private int expectedModCount = modCount; public E next() { checkForComodification(); //每次添加元素前，都检查一次modCount和expectedModCount是否相等，如果不相等就直接返回ConcurrentModificationException异常，产生快速失败,多线程环境下这里通不过 if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; //当前节点-->下一个节点 next = next.next; //下下个节点的指正往前移一个节点 nextIndex++; //index++ return lastReturned.item; //返回移动后的节点的数据 }

      final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }

   2. 在解析如何修改modCount 值之前我们应该弄明白，LinkedList中的Node节点是如何实现的

      //私有节点类Node，在1.8版本之前叫做Entry 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; } }

   3. 源码中是如何修改modCount 的值的(不包括作为队列和双端队列的方法)(开始怼源码)

      transient int size = 0; //元素数量 transient Node<E> first; //首节点引用，为null transient Node<E> last; //尾结点引用，为null //追加一个元素到列表的末尾 public boolean add(E e) { //把元素存放到链表的末尾 linkLast(e); return true; } //尾部添加元素 void linkLast(E e) { //获取当前尾节点的引用 final Node<E> l = last; //构建一个新节点，prev的值为l(尾节点)、节点数据为e、next的值为null final Node<E> newNode = new Node<>(l, e, null); //新节点作为尾结点 last = newNode; //如果原尾节点为null if (l == null) //即原链表为null，链表的首节点也是newNode first = newNode; else //否则，原节点的next设置为newNode l.next = newNode; //数量+1 size++; //修改modCount modCount++; } //将指定元素插入到列表中的指定位置。 public void add(int index, E element) { //检查index是否在有效范围内 checkPositionIndex(index); //如果index==size，说明添加的位置是末尾 if (index == size) //在末尾添加元素 linkLast(element); else //把element元素插入到index指定的节点位置 linkBefore(element, node(index)); } //检查index是否在有效范围内 private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } //返回指定元素索引处的(非空)节点。(注意这里有技巧) Node<E> node(int index) { //如果index小于size的1/2长度 if (index < (size >> 1)) { //获取头结点的引用 Node<E> x = first; //从前到后遍历index个节点，最后返回 for (int i = 0; i < index; i++) x = x.next; return x; } else { //否则获取最后一个节点的引用 Node<E> x = last; //从后到前遍历index个节点，最后返回 for (int i = size - 1; i > index; i--) x = x.prev; return x; } } //在非空节点succ之前插入元素e。 void linkBefore(E e, Node<E> succ) { //获取succ节点(index)的前一个节点的引用 final Node<E> pred = succ.prev; //创建一个新的节点，维护的新节点的前一个节点是pred、元素本身、和元素的下一个节点succ final Node<E> newNode = new Node<>(pred, e, succ); //succ节点的上一个节点指向newNode succ.prev = newNode; if (pred == null) //如果pred节点为null，则说明没有值，则newNode就是第一个节点 first = newNode; else //否则pred的下一个节点指向newNode pred.next = newNode; //数量+1 size++; //修改modCount modCount++; } //将指定集合中的所有元素追加到这个列表 public boolean addAll(Collection<? extends E> c) { //调用了插入集合元素的方法，指定了index=size return addAll(size, c); } //将指定集合中的所有元素插入其中列表 public boolean addAll(int index, Collection<? extends E> c) { //检查index是否有效 checkPositionIndex(index); //先把集合转换成数组，这也就限定了集合必须是List下的实现类 Object[] a = c.toArray(); //获取集合的长度 int numNew = a.length; //如果集合的长度为0，即为空 if (numNew == 0) return false; //定义两个节点，succ指向当前需要插入节点的位置，pred指向其前一个节点 Node<E> pred, succ; //如果在尾部插入元素 if (index == size) { //当前节点为空 succ = null; //当前节点的上一个节点就是最后一个节点 pred = last; } else { //否则获取index位置的节点指向succ succ = node(index); //index位置节点的前一个引用指向pred pred = succ.prev; } //遍历集合，每一个节点都做重复创建，添加引用 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //创建节点，该节点的pred指向pred节点(最初的index节点的前一个节点)，元素本身e，下一个节点指向null。 Node<E> newNode = new Node<>(pred, e, null); //判断是否为链表头 if (pred == null) first = newNode; else //pred节点的next也指向新节点 pred.next = newNode; //新节点又继续作为pred节点存在 pred = newNode; } //集合遍历完成后，如果当前节点为空节点，即在链表的末尾添加元素，就把pred指向尾结点，succ节点不存在 if (succ == null) { last = pred; } else { //如果是在链表中间插入的集合，当前节点succ是作位pred的next元素存在 pred.next = succ; //同时pred指向succ的上一个节点引用，相互引用 succ.prev = pred; } //size+numNew个数 size += numNew; //修改modCount modCount++; return true; } //删除列表中指定位置的元素。 public E remove(int index) { //检查index是否有效 checkElementIndex(index); //删除index节点的元素 return unlink(node(index)); } //删除节点 E unlink(Node<E> x) { //获取节点的元素 final E element = x.item; //获取元素的下一个节点的引用 final Node<E> next = x.next; //获取元素的上一个节点的引用 final Node<E> prev = x.prev; //如果上一个节点等于null，则说明前面没有节点，把next节点的下一个节点引用为第一个节点 if (prev == null) { first = next; } else { //否则把next节点引用为prev节点的next指向的节点 prev.next = next; //x节点的上一个节点置空 x.prev = null; } //如果next节点等于null，为空值，就直接把prev赋值为last节点 if (next == null) { last = prev; } else { //否则把next节点的上一个节点指向prev next.prev = prev; //x节点的下一个节点置空 x.next = null; } //最后把x的数据置空 x.item = null; size--; //修改modCount modCount++; //返回已经删除的元素值 return element; } //从列表中删除指定元素的第一个匹配项 public boolean remove(Object o) { //如果对象o等于null(这里说明linkedList允许存放null值) if (o == null) { //从头到尾遍历找出第一个符合数据为null的节点 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { //删除节点 unlink(x); return true; } } } else { //否则 从头到尾遍历找出第一个符合数据为null的节点 for (Node<E> x = first; x != null; x = x.next) { //找出符合qeuals条件的对象 if (o.equals(x.item)) { //删除 unlink(x); return true; } } } return false; } //从列表中删除所有元素。 public void clear() { //注意使用的是for循环遍历全部节点 for (Node<E> x = first; x != null; ) { //每个节点的所有信息全部置空 Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; //循环赋值 x = next; } //首节点和尾结点赋值为null first = last = null; size = 0; modCount++; } //获取指定位置节点元素 public E get(int index) { //检查index是否有效 checkElementIndex(index); //返回index节点的数据 return node(index).item; } //将列表中指定位置的元素替换为指定元素。 public E set(int index, E element) { //检查index是否有效 checkElementIndex(index); //获取index的节点 Node<E> x = node(index); //获取节点的item E oldVal = x.item; //新的元素替换旧的元素 x.item = element; //返回旧元素 return oldVal; } //将双向链表转换成数组 public Object[] toArray() { //创建一个Size大小的数组 Object[] result = new Object[size]; int i = 0; //循环遍历所有节点 for (Node<E> x = first; x != null; x = x.next) //将节点数据存入数组 result[i++] = x.item; //返回数组 return result; }

      和ArrayList一样，无论add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount(全局)的值。由此回到next()方法中我们发现当 ‘A’ 线程正在做迭代器遍历操作时，modCount赋值给了expectedModCount，每次调用next()方法都会做一次modCount != expectedModCount的校验，此时线程 ’B‘ 进来了调用了add方法修改了modCount的值，此时modCount变成了N+1，判断为false，抛出ConcurrentModificationException异常，产生fail-fast事件 。

4. fail-fast`事件

   当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常。与此对应的安全失败，在后面再解析。

5. 解决方法

   使用Collections.synchronizedList()方法包装，但是效率低下，这种方法实际上只是将原来非线程安全的LinkedList中的方法加上一个synchronized同步代码块 (哭了。。。)

6. 优化建议

   在多线程下如果有按数据索引访问元素的情形，采用Collections.synchronizedList(new LinkedList<>())方法

7. LinkedList的常用API

   方法	描述
   add(E e)	将指定的元素添加到列表的末尾。
   addFirst(E e)	在此列表的开始处插入指定的元素。
   addLast(E e)	将指定的元素列表的结束。
   get(int index)	返回此列表中指定位置的元素。
   remove(int index)	移除此列表中指定位置的元素。
   size()	返回此列表中元素的数目。
   toArray()	返回一个数组，包含在这个列表中的所有元素在适当的顺序（从第一个到最后一个元素）。
   clear()	从这个列表中移除所有的元素。
   indexOf(Object o)	返回此列表中指定元素的第一个出现的索引
   peek()	检索，但不删除，此列表的头（第一个元素）。
   poll()	检索并删除此列表的头（第一个元素）。
   pop()	从这个列表所表示的堆栈中弹出一个元素。
   push(E e)	将一个元素推到由该列表所表示的堆栈上。
   offer(E e)	将指定的元素添加到列表的尾部（最后一个元素）。