为什么 ArrayList 查询快增删慢，LinkedList 增删快，查询慢

[LinkedList]

1. 查询慢（双向链表的弊端）
   双向链表的查询逻辑是他会根据 index 的大小判断是从前开始遍历还是从后开始遍历，如果 index 更靠前就从前遍历，更靠后就从后遍历，也就是在查询过程中，会一次次的移动指针直到获取到 index 的值。

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
	
	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;
        }
    }

2. 增删快
   只需要修改插入位置或删除位置左右数据的引用目标即可。

ArrayList

1. 查询快
   可以看出 ArrayList 底层是用的数组存储。
   而数组的查询实际上是对引用地址的访问，不需要遍历。
   列如 new int arr[5];
   arr 数组的地址假设为 0x1000
   arr[0] ~ arr[5] 地址可看作为 0x1000 + i * 4
   首地址 + 下标 + 引用数据类型的字节大小。

transient Object[] elementData;
 
	public E get(int index) {
        rangeCheck(index);
 
        return elementData(index);
    }
	
	E elementData(int index) {
        return (E) elementData[index];
    }

2. 增删慢（使用数组的弊端）
   • 每当插入或删除操作时 对应的需要向前或向后的移动元素
   • 当插入元素时 需要判定是否需要扩容操作
   • 扩容操作：创建一个新数组 增加 length 再将元素放入进去
     较为繁琐