古巴比伦王颁布了汉谟拉比法典，刻在黑色的玄武岩，距今已经三千七百多年，你在橱窗前，凝视菜单的字眼，我却在旁静静欣赏我巩固到的知识点--ArrayList（动态列表）
扩容
ArrayList
当我们添加数据到末尾的时候，会先去确认一下需不需要扩容，扩容的话就要增加到当前容量的1.5倍，然后再把原来数据复制一份，再做正常的添加。System.arrayCopy() 如果做插入的话，会把split前后的数据分别复制到新数组里面，顺便留出位置来给需要的元素。 这里可以发现，频繁的扩容或者插入的话会非常的消耗性能，所以要是能提前预知好数据容量，还是直接在初始化的时候，把数组写死。
LinkedList
链表的扩容完全不用考虑那么多，毕竟只是把node的指向修改一下。
增删改查
array啊，就是排在一起，所以查找的话肯定是ArrayList比较快，而LinkedList就需要一个个的找了，但是鬼精的设计的Node既有pre，又有next，所以干脆get方法直接来了个二分查找。 get(index)方法返回的是nod(index).item 就是这个node
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;
}
}
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;
}
}
ArrayList的SubList
对SubList的所有操作都会变现到原来的parentList上，不信你看
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
fail-fast && fail-safe
这俩是数据安全的两种机制。
fail-safe 快速失败
当在迭代器Iterator遍历的过程中，对当前容器进行修改，内部modCount会和ExpectedModCount对比，由于不一致，导致数据修改失败。 这里有个点，list中只有在长度修改的时候，修改次数才会增加，修改数据不会。 一开始我想不通，为何迭代的时候不能修改长度？ arraylist的迭代器.
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
代码层面是因为在生成迭代器的时候就给变量赋值，所以后期修改数组长度的时候，会不一致，但是不一致能怎样呢？直到去了一趟便利店，才想明白啊，人这是为了数据安全，或者说数据的有效性。 我们在一个俩线程里面都持有了当前的list， a线程要拿出第0个位置的元素，b线程直接给删掉了，那到底改还是不改呢。所以这个就是为了数据安全。
https://blog.csdn.net/qq_31780525/article/details/77431970 这个讲的很不错。
关于遍历
RandomAccess是用来当标记的，意思是，随机访问任意下标元素都比较快。ArrayList实现了RandomAccess 遍历用for循环； LinkedList用Iterator会快一些，链表与数组的性质，你懂的。 但是，arraylist也不是傻的对不对，作者确实重写了listIterator方法，两种方式遍历相差无几，当然推荐还是for。
我做的测试：
public class Test {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList(100000);
for (int i = 0; i < 100000; i++) {
list.add(i);
}
LinkedList<Integer> linkedList = new LinkedList();
for (int i = 0; i < 100000; i++) {
linkedList.add(i);
}
detectedForTime(list,"list--for--");
detectedIteratorTime(list,"list--iterator--");
detectedForTime(linkedList,"linkedList--for--");
detectedIteratorTime(linkedList,"linkedList--iterator--");
}
static void detectedForTime(List list,String tag){
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
list.get(i);
}
System.out.println(tag + (System.currentTimeMillis() - start));
}
static void detectedIteratorTime(List list,String tag){
long start = System.currentTimeMillis();
Iterator iterator = list.iterator();
while (iterator.hasNext()){
iterator.next();
}
System.out.println(tag + (System.currentTimeMillis() - start));
}
}
result:
list--for--7
list--iterator--11
linkedList--for--6552
linkedList--iterator--6
