ArrayList
ArrayList 内部维护了一个动态的Object 数组，ArrayList 的动态增删就是对这个数组的动态增删。
1、ArrayList 的构造以及初始化
ArrayList 实例变量
ArrayList构造函数：
ArrayList 构造函数
ArrayList 在调用构造函数初始化时（new），如果是无参构造，则是为elementData赋值为Object[0]，即创建一个容量为0的空数组；有参数，则创建指定容量大小的空数组。
2、ArrayList的容量分配机制
ArrayList 的容量上限：ArrayList 容量是有上限的，理论上允许分配Integer.Max_VALUE - 8大小的容量。
ArrayList 最大容量
调用 add 方法时扩容规则：
add 源码
当使用无参构造函数初始化 ArrayList 时，在第一次 add 时会将容量大小设置为默认值10；当容量大小少于元素个数时，会进行扩容，扩容大概会增长50%。
总结：每次扩容都会伴随数组的复制操作，因此一次给定恰当的容量会提高一点性能。
ArrayList 扩容流程
3、ArrayList 迭代器
ArrayList 迭代器源码
checkForComodification 是 java-collection-framwork 中的一种 fast-fail 的错误检测机制。
fast-fail事件产生的条件：当多个线程对Collection进行操作时，若其中某一个线程通过iterator去遍历集合时，该集合的内容被其他线程所改变，则会抛出ConcurrentModificationException异常。
Itr 迭代器定义了一个exceptedModCount， 记录 modCount 副本，在 ArrayList 执行改变结构的操作时，例如 add，remove，clear 方法时，modCount 的值会改变。故通过 iterator 去遍历集合，使用list的 add，remove，clear 方法时，由于modCount 的值改变了，但是Itr 迭代器里的 exceptedModCount 未改变，导致 checkForComodification 会抛出 ConcurrentModificationException 异常。解决方案：使用 Itr 的add，remove 方法（高并发场景不适用）。注：for(String str : strs) 该形式的遍历底层是 Itr 迭代器。
使用J.U.C中的 CopyOnWriteArrayList 解决 fast-fail 问题：
CopyOnWriteArrayList 是线程安全的，具体看下它的 add 方法源码：
add 源码
CopyOnWriteArrayList 就是写时复制的 ArrayList。当开始写数据的操作时，ArrayList.copyOf 一个新的数组，这样不会影响读操作。
这样的代价就是会损耗内存，带来性能的问题。CopyOnWriteArrayList 写的时候在内存中生成一个副本对象（容量+1），然后将新增的元素放入数组最后一位，最后将新的副本数组覆盖原来数组。
CopyOnWriteArrayList 无法保证数据实时的一致，只能保证结果一致。适用于并发下读多写少的场景，例如缓存。
LinkedList
LinkedList 即链表，相对于顺序表，链表存储数据不需要使用地址连续的内存单元。减少了修改容器结构而带来的移动元素的问题。
1.结点（Node）的定义
LinkedList是双向链表， 每个结点分别存有上一个结点和下一个结点的信息。它的定义如下：
Node 结点
2、LinkedList 构造以及初始化
成员：LinkedList中维护了三个成员变量，用以记录链表中的结点个数，结点的前驱（表头）以及后继（表尾）。
LinkedList 成员变量
构造方法
LinkedList 没有容量的属性，即没有扩容的概念。
3、LinkedList 的结构操作
add:
几种add 源码
get:
get 源码
get 下node方法 源码
size >> 1：位运算，将size 的二进制向右移一位，相当于 size/2；举个栗子：
4的二进制位：0100，向右移一位得：0010（2），故相当于取一半。
node(int index) 源码中，我们发现，当 index 属于前半部分的计数，从头遍历查找（最后一个下标为 index - 1，即为所需数据）；当 index 属于后半部分的计数，从末尾遍历查找，充分利用了双向链表的特点。
remove:
remove 源码
删除元素，遍历整个表。
LinkedList，ArrayList 总结
ArrayList 是基于动态数组的数据结构，LinkedList 基于链表的数据结构。
对于随机访问get 和set 方法，ArrayList 优于 LinkedList，因为 LinkedList 要根据传入的 index，遍历链表获取元素。
对于add，LinkedList 比较占优势，它直接放入链表尾部就行了，而 ArrayList需要扩容。对于 remove 方法，因情况而定，因为 LinkedList 是需要遍历整个表的，如果数据量很大的话，与 ArrayList 的移动数据所消耗的性能是差不多的。
网友评论