LinkedList底层详解

LinkedList详解

• 一、List引发的思考
• • 1. List接口
  • 2. LinkedList继承体系
  • 3. AbstractList抽象类
  • 4. AbstractSequentialList
• 二、LinkedList的底层实现
• • 1. Node的理解
  • 2. 双向链表
• 三、并发修改异常
• 四、如何避免并发修改异常
• 五、LinkedList多线程情况下解决线程安全问题

一、List引发的思考

思考：LinkedList中实现的方法为什么和ArrayList中相似呢？

• 因为它们都是属于单列集合下的，所以它们实现的方法都是一致的，为了让它们的体系完整，进而设计出了List接口，让LinkedList和ArrayList实现List接口。

1. List接口

包含的共性的方法

public interface List<E>{int size()boolean isEmpty()boolean contains(E element)void add(E element)E get(int index)E set(int index, E element)void add(int index, E element)E remove(int index)int indexOf(E element)void clear()
}

2. LinkedList继承体系

3. AbstractList抽象类

由于List中的方法都需要实现，如果采用直接实现的方式会造成冗余，所以定义了AbstractList抽象类专门用来实现 LinkedList 和 ArrayList 中共有的方法，实现代码的复用。
实现共性的方法，实现List

public abstract class AbstractList implements List<E>{int size;int size(){}boolean isEmpty(){}boolean contains(E element){}//add方法都会调用add(int index, E element)void add(E element){}
}public class LinkedList <E> extends AbstractList<E>{//重写其它方法
}

4. AbstractSequentialList

AbstractSequentialList 继承自 AbstractList，是 LinkedList 的父类，是 List 接口 的简化版实现。
简化在哪儿呢？简化在 AbstractSequentialList 只支持按次序访问，而不像 AbstractList 那样支持随机访问。
AbstractSequentialList 在 AbstractList 的基础上实现了以下方法：

总结
AbstractSequentialList 把父类 AbstractList 中没有实现或者没有支持的操作都实现了，而且都是调用的 ListIterator 相关方法进行操作。

AbstractSequentialList 只支持迭代器按顺序 访问，不支持 RandomAccess，所以遍历 AbstractSequentialList 的子类，使用 for 循环 get() 的效率要 <= 迭代器遍历

二、LinkedList的底层实现

1. Node的理解

首先 LinkedList 中有一个一个的 Node，这些 Node 中封装着数据值和地址值，所以这里的 Node 肯定是一个类，并且是所属于 LinkedList 的（理解：实例化了 LinkedList ，并没有对 Node 进行操作，但同时 Node 也被创建了出来）

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;}}

2. 双向链表

LinkedList 的底层使用的是双向链表的存储结构, 在 LinkedList 内部，有 size first last 属性以及一个内部类 Node
如图所示：

优势：遍历效率优于单向链表（查找靠近尾巴的节点）

先去判断要查找的 index 是否大于 size 的一半， 大于就从后往前查找…

源码

/*** Returns the (non-null) Node at the specified element index.*/
Node<E> node(int index) {// assert isElementIndex(index);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;}
}

三、并发修改异常

遍历 LinkedList 的方式：（使用迭代器）

运行以上程序结果如下：

发现出现异常的位置在第 22 行

原因分析

1. 首先点进 LinkedList 的 iterator() 方法
   
   
2. 这个在 AbstractList 中的 listIterator 方法中 new 的 ListItr 类我们发现在 LinkedList 中存在，所以调用的肯定是 子类 LinkedList 中的实现类
   
3. 此时调用 iterator() 方法执行完毕
   
4. 接着进入 while 循环中的 hasNext() 方法
   
5. 接着进入 add() 方法，发现 modCount 进行了 ++ 操作
   
   
6. 接着再查看 next() 方法
   
   
7. 所以此时会抛出 ConcurrentModificationException 异常

四、如何避免并发修改异常

方法：

这里的 iter 是 LinkedList 的内部类 ListItr 的对象

我们再来分析 iter 调用 add() 方法时不出现异常的原因！！！

五、LinkedList多线程情况下解决线程安全问题

//调用集合工具类的方法 ---> 加锁
Collection c = Collections.synchronizedCollection(linkedList);
//使用 juc 包下的类 ---> cas(无锁化机制) + volatile关键字解决的
ConcurrentLinkedQueue c = new ConcurrentLinkedQueue();
//ConcurrentLinkedQueue只保证集合的线程安全，不保证打印的线程安全 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！