[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;
        }
    }
  1. 增删快
    只需要修改插入位置或删除位置左右数据的引用目标即可。

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];
    }
  1. 增删慢(使用数组的弊端)
    • 每当插入或删除操作时 对应的需要向前或向后的移动元素
    • 当插入元素时 需要判定是否需要扩容操作
    • 扩容操作:创建一个新数组 增加 length 再将元素放入进去
      较为繁琐