ArrayList为什么比LinkedList查询速度快

标签：LinkedList idx get int ArrayList 查询 size

知乎：https://www.zhihu.com/question/61920401

举个简单的例子：假如有很多人，排成长队，这个时候要找5号的人就非常简单，问都不用问，直接定位。假如不排成长队，只是随机站在很大的广场里面，但是每个人只知道自己的前一个人和后一个人的位置，而且你只知道第一个人的位置，这个时候你要找第5个人的时候你就得从第一个人开始问后面的是谁，一直问下去才知道第5个人在哪里。   先看源码
ArrayList的get()方法：时间复杂度为O(1)

public AnyType get(int idx) {
        if(idx < 0 || idx >= size())
            throw new ArrayIndexOutOfBoundsException();
        return theItems[idx];
}

LinkedList的get()方法：时间复杂度为O(N)

private Node<AnyType> getNode(int idx, int lower, int upper) {
        Node<AnyType> p;

        if(idx < lower || idx > upper)
            throw new IndexOutOfBoundsException();

        if(idx < (size() >> 1)) {
            p = beginMarker.next;
            for(int i = 0; i < idx; i++)
                p = p.next;
        }else {
            p = endMarker;
            for(int i = size(); i >idx; i--)
                p = p.prev;
        }

        return p;
    }

ArrayList可以直接通过数组下标得到元素，而LinkedList则需要根据所给的下标从头部或尾部开始往下标的位置依次获得下一个元素或上一个元素。

标签：LinkedList,idx,get,int,ArrayList,查询,size
From： https://www.cnblogs.com/zuiniub/p/16893878.html