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

ゝ一纸荒年。 2022-01-30 02:43 591阅读 0赞

最近面试过程中遇到了这个问题， 当时脱口而出因为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;
        }
    }