LinkedList通过下标查询效率为什么比ArrayList慢

下标查询效率为什么比ArrayList慢"/>

LinkedList通过下标查询效率为什么比ArrayList慢

最近面试过程中遇到了这个问题， 当时脱口而出因为ArrayList底层是个数组，可以通过下标直接获取到我们的索引值，查询的时间复杂度是O(1)。 linkedList底层是链表,时间复杂度是O(n)[注：这里的n为元素个数的一半， 时间复杂度中的n仅和操作的数据量有关， 这里LinkedList的查询仅对一半的数据查找]。 可能会有小伙伴疑惑，那为啥不是O(n/2), 这里n和n/2是等价的， 而且也没有O(n/2)的表示方法呀！

LinkedList的查询效率为什么比ArrayList低： ArrayList底层是数组，使用get()方法， 直接取的是数组对应下标中的值。 LinkedList底层是链表， 数据结构上一定不存在下标这么个概念。 get()方法，内部是对(0到index)和(index到总数)的遍历，最终找到我们要查询的下标中的值， 所以效率上要比ArrayList低。

ArrayList通过索引获取值：

// ArrayList的get()方法
public E get(int index) {// 判断索引值是否大于数据总量rangeCheck(index);// 获取下标元素的值return elementData(index);
}
// 判断索引值是否大于数据总量的方法
private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}// 从底层数组中获取元素
E elementData(int index) {// 重点***： 获取下标对应的具体值return (E) elementData[index];
}
// 存放元素的数组
transient Object[] elementData; 

LinkedList通过索引获取值：首先需要明确，LinkedList底层是一个链表， 肯定没有下标的概念， 只能是对总数遍历，然后取循环下标的值

// LinkedList的get方法，通过索引获取值
public E get(int index) {//检测指定下标index是否在正确的范围内checkElementIndex(index);// 遍历，找到指定的索引， 然后获取值return node(index).item;
}
// 索引值不正确，抛异常
private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 索引需要大于等于0 且小于元素的总数量
private boolean isElementIndex(int index) {return index >= 0 && index < size;
}
// 遍历元素数量， 获取到指定索引位置的值
Node<E> node(int index) {// 注意***：判断index在总数量的前半部分还是后半部分，这样仅需要遍历一半的数据量就能找到具体的值， 有种取半操作的含义if (index < (size >> 1)) {//如果在前半部分，就从0开始正序遍历， 直到找到元素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;}
}