ArrayList 和 LinkedList 的区别（面试常考）

最近秋招面试时经常碰到这道题，虽然自己也答出来了，但总感觉不是那么完善，特此总结一下。

ArrayList 和 LinkedList 都实现了 List 接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
        
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    

我们可以看到 LinkedList 还实现了 Deque 这个队列接口，可以作为双向队列的实现。

ArrayList 的底层是动态数组，可以实现动态扩容，每次扩容成原来的 1.5 倍，相对于原来的基本数组，它封装了数组插入、删除、扩容这些数组操作的细节。
另外，它支持随机访问，但是删除或者插入元素效率很低，例如在数组中间插入一个元素，必须把这个元素以后的元素全部向后搬移一个位置。

LinkedList 访问一个元素时一般是通过 for 循环获取到这个元素所在位置，然后返回这个元素，时间复杂度为 O(n)。删除或者插入一个给定指针指向的结点时间复杂度为 O(1）。

我们下面写个程序来模拟两种数据结构的随机查找过程。

/**
 * ArrayList 底层是动态数组，利用数组下标随机访问元素很高效。
 */
public class ArrayList {
    public static void main(String[] args) {
        List<Integer> arrayList = new java.util.ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        for(int i = 0; i< 100000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        long arraylisttime = getTime(arrayList);
        System.out.println(arraylisttime + " ms");
        long linkedListTime = getTime(linkedList);
        System.out.println(linkedListTime + " ms");
      
    }

    private static long getTime(List<Integer> list) {
        long curTime =  System.currentTimeMillis();
        for(int i = 0; i< list.size(); i++) {
            // ArrayList 通过下标访问元素。
            list.get(i);
        }
        long wasteTime = System.currentTimeMillis();
        return wasteTime - curTime;
    }
}

/** 结果：
* 8 ms
* 7892 ms
*/

可以看出数组随机访问的性能确实非常高，特别是在数据量大的时候。

原理就是数组在内存中占用连续的存储空间并且存储相同的元素。所以根据下标访问某一个元素时可以直接计算得到元素所在位置，大大加快了访问速度。