ArrayList的底层结构是顺序结构，LinkedList的底层结构是链式结构。

两者都支持迭代器访问和下标访问两种方式，一般来说，更推荐使用下标去访问ArrayList，用迭代器去访问LinkedList。下面做了一个实验去分别对比两种list使用两种访问方式的速度。

• 都使用下标访问，list的大小为100000。

        List<String> linked = new LinkedList<>();
        List<String> array = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            linked.add(String.valueOf(i));
            array.add(String.valueOf(i));
        }
        long startA = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            array.get(i);
        }
        long endA = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            linked.get(i);
        }
        long endL = System.currentTimeMillis();
        System.out.println("Array: " + (endA - startA));
        System.out.println("Linked: " + (endL - endA));

image.png

可以看出，两者差距明显。因为顺序结构对下标的访问时间复杂度是O(1), 链式结构的时间复杂度是O(n)。

• 都使用迭代器访问， list的大小为100000。

        List<String> linked = new LinkedList<>();
        List<String> array = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            linked.add(String.valueOf(i));
            array.add(String.valueOf(i));
        }
        long startA = System.currentTimeMillis();
        Iterator<String> iterator = array.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        long endA = System.currentTimeMillis();
        iterator = linked.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        long endL = System.currentTimeMillis();
        System.out.println("Array: " + (endA - startA));
        System.out.println("Linked: " + (endL - endA));

image.png

可以看出，两者访问速度相当。因为使用迭代器的这种方式，两种链表访问的时间复杂度都是O(1)。