MUYI · 后端工程师的生产级知识体系

Appearance

Arraylist 与 LinkedList 区别? ​

  1. 是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是都不保证线程安全；

  2. 底层数据结构：ArrayList底层使用的是Object数组。LinkedList底层是双向链表（JDK1.7 之前为循环双向链表，之后改为非循环）。注意双向链表和双向循环链表的区别，下面有介绍。

  3. 插入和删除是否受元素位置的影响：

    • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e) 方法时，ArrayList 默认将指定的元素追加到此列表的末尾。这种情况时间复杂度就是O(1)。如果在指定位置 i 插入和删除元素（add(int index, E element)），时间复杂度就为 O(n-i)。因为执行上述操作时，集合中第 i 和第 i 个元素之后的(n-i)个元素都要向后位/向前移一位。
    • LinkedList 采用链表存储。所以对于add(E e)方法的插入、删除元素，时间复杂度不受元素位置的影响，近似 O（1）。如果是在指定位置i插入和删除元素（(add(int index, E element)） ，时间复杂度近似为O(n)。因为需要先移动到指定位置再插入。

  4. 是否支持快速随机访问:LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象。它对应于get（int index）方法。

  5. 内存空间占用:ArrayList的空间浪费主要在list列表的结尾预留一定的容量空间。LinkedList 的空间花费则体现在它的每一个元素都需要消耗 ArrayList 更多的空间。原因是每个元素要存放直接后续和直接前驱以及数据。

RandomAccess接口 ​

java
public interface RandomAccess {
    
}

查看源码我们发现，RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。它标识实现这个接口的类具有随机访问功能。

在 binarySearch（）方法中，它要判断传入的list 是否 RamdomAccess 的实例，如果是，调用indexedBinarySearch（）方法，如果不是，那么调用iteratorBinarySearch（）方法

java
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 实现了 RandomAccess 接口， 而 LinkedList 没有实现。原因：和底层数据结构有关。ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O（1），所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O（n）。所以链表不支持快速随机访问。

ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的。

下面再总结 list 的遍历方式选择： ​

  • 实现了 RandomAccess 接口的list，优先选择普通 for 循环 ，其次 foreach,
  • 未实现 RandomAccess接口的list，优先选择iterator遍历（foreach遍历底层也是通过iterator实现的）。大size的数据，禁止使用普通for循环

双向链表和双向循环链表 ​

双向链表： 包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。

双向链表

LinkedList 同时实现了 List 与 Deque 接口，可作队列、双端队列使用。引证：JDK 源码中的私有内部类 Node 就是上述结构的具体实现（item 存节点值，prev/next 分别指向前驱与后继）：

LinkedList内部结构

java
private static class Node<E> {
    E item;//节点值
    Node<E> next;//后继节点
    Node<E> prev;//前驱节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

双向循环链表： 最后一个节点的 next 指向head，而 head 的prev指向最后一个节点，构成一个环。

双向循环链表

2026-10 整改：并入《Java集合/LinkedList源码分析》。吸收其 Node 内部类段与 Deque 接口事实，线程安全部分库内另有覆盖。