Java 面试题：说一下 ArrayList 和 LinkedList 的区别？

本文已收录到 GitHub AndroidFamily，有 Android 进阶知识系统，欢迎 Star。技术和职场问题，请关注大众号 [彭旭锐] 私信我发问。

前言

大家好，我是小彭。

在上一篇文章里，咱们聊到了根据动态数组 ArrayList 线性表，今日咱们来评论一个根据链表的线性表 —— LinkedList。

---

学习路线图：

---

1. LinkedList 的特色

1.1 说一下 ArrayList 和 LinkedList 的差异？

• 1、数据结构： 在数据结构上，ArrayList 和 LinkedList 都是 “线性表”，都承继于 Java 的 List 接口。另外 LinkedList 还完结了 Java 的 Deque 接口，是根据链表的栈或行列，与之对应的是 ArrayDeque 根据数组的栈或行列；
• 2、线程安全： ArrayList 和 LinkedList 都不考虑线程同步，不保证线程安全；
• 3、底层完结： 在底层完结上，ArrayList 是根据动态数组的，而 LinkedList 是根据双向链表的。事实上，它们许多特性的差异都是因为底层完结不同引起的。比如说：
  • 在遍历速度上： 数组是一块接连内存空间，根据局部性原理可以更好地命中 CPU 缓存行，而链表是离散的内存空间对缓存行不友好；
  • 在访问速度上： 数组是一块接连内存空间，支撑 O(1) 时刻复杂度随机访问，而链表需求 O(n) 时刻复杂度查找元素；
  • 在添加和删去操作上： 假如是在数组的结尾操作只需求 O(1) 时刻复杂度，但在数组中心操作需求搬运元素，所以需求 O(n)时刻复杂度，而链表的删去操作自身只是修正引用指向，只需求 O(1) 时刻复杂度（假如考虑查询被删去节点的时刻，复杂度剖析上依然是 O(n)，在工程剖析上仍是比数组快）；
  • 额定内存耗费上： ArrayList 在数组的尾部添加了闲置方位，而 LinkedList 在节点上添加了前驱和后继指针。

1.2 LinkedList 的多面人生

在数据结构上，LinkedList 不只完结了与 ArrayList 相同的 List 接口，还完结了 Deque 接口（承继于 Queue 接口）。

Deque 接口表示一个双端行列（Double Ended Queue），答应在行列的首尾两头操作，所以既能完结行列行为，也能完结栈行为。

Queue 接口：

回绝战略	抛反常	返回特别值
入队（队尾）	add(e)	offer(e)
出队（队头）	remove()	poll()
调查（队头）	element()	peek()

Queue 的 API 可以分为 2 类，差异在于办法的回绝战略上：

• 抛反常：

  • 向空行列取数据，会抛出 NoSuchElementException 反常；
  • 向容量满的行列加数据，会抛出 IllegalStateException 反常。

• 返回特别值：

  • 向空行列取数据，会返回 null；
  • 向容量满的行列加数据，会返回 false。

Deque 接口：

Java 没有供给规范的栈接口（很好奇为什么不供给），而是放在 Deque 接口中：

回绝战略	抛反常	等价于
入栈	push(e)	addFirst(e)
出栈	pop()	removeFirst()
调查（栈顶）	peek()	peekFirst()

除了规范的行列和栈行为，Deque 接口还供给了 12 个在两头操作的办法：

回绝战略	抛反常	返回值
添加	addFirst(e)/ addLast(e)	offerFirst(e)/ offerLast(e)
删去	removeFirst()/ removeLast()	pollFirst()/ pollLast()
调查	getFirst()/ getLast()	peekFirst()/ peekLast()

---

2. LinkedList 源码剖析

这一节，咱们来剖析 LinkedList 中首要流程的源码。

2.1 LinkedList 的特点

• LinkedList 底层是一个 Node 双向链表，Node 节点中会持有数据 E 以及 prev 与next 两个指针；
• LinkedList 用 first 和 last 指针指向链表的头尾指针。

LinkedList 的特点很好了解的，不出意外的话又有小朋友出来举手发问了：

• ‍♀️疑问 1：为什么字段都不声明 private 关键字？

这个问题直接答复吧。我的了解是：因为内部类在编译后会生成独立的 Class 文件，假如外部类的字段是 private 类型，那么编译器就需求经过办法调用，而 non-private 字段就可以直接访问字段。

• ‍♀️疑问 2：为什么字段都声明 transient 关键字？

这个问题咱们在剖析源码的进程中答复。

疑问比 ArrayList 少许多，LinkedList 真香（仍是别快乐得太早吧）。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // 疑问 1：为什么字段都不声明 private 关键字？
    // 疑问 2：为什么字段都声明 transient 关键字？
    // 元素个数
    transient int size = 0;
    // 头指针
    transient Node<E> first;
    // 尾指针
    transient Node<E> last;
    // 链表节点
    private static class Node<E> {
        // 节点数据
        // （类型擦除后：Object item;）
        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;
        }
    }
}

2.2 LinkedList 的结构办法

LinkedList 有 2 个结构办法：

• 1、无参结构办法： no-op；
• 2、带调集的结构： 在链表结尾添加整个调集，内部调用了 addAll 办法将整个调集添加到数组的结尾。

// 无参结构办法
public LinkedList() {
}
// 带调集的结构办法
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
// 在链表尾部添加调集
public boolean addAll(Collection<? extends E> c) {
    // 索引为 size，等于在链表尾部添加
    return addAll(size, c);
}

2.3 LinkedList 的添加办法

LinkedList 供给了十分多的 addXXX 办法，内部都是调用一系列 linkFirst、linkLast 或 linkBefore 完结的。假如在链表中心添加节点时，会用到 node(index) 办法查询指定方位的节点。

其实，咱们会发现所有添加的逻辑都可以用 6 个进程概括：

• 进程 1： 找到刺进方位的后继节点（在头部刺进便是 first，在尾部刺进便是 null）；
• 进程 2： 结构新节点；
• 进程 3： 将新节点的 prev 指针指向前驱节点（在头部刺进便是 null，在尾部刺进便是 last）；
• 进程 4： 将新节点的 next 指针指向后继节点（在头部刺进便是 first，在尾部刺进便是 null）；
• 进程 5： 将前驱节点的 next 指针指向新节点（在头部刺进没有这个进程）；
• 进程 6： 将后继节点的 prev 指针指向新节点（在尾部刺进没有这个进程）。

剖析一下添加办法的时刻复杂度，区分在链表两头或中心添加元素的状况共：

• 假如是在链表首尾两头添加： 只需求 O(1) 时刻复杂度；
• 假如在链表中心添加： 因为需求定位到添加方位的前驱和后继节点，所以需求 O(n) 时刻复杂度。假如事先现已获得了添加方位的节点，就只需求 O(1) 时刻复杂度。

添加办法

public void addFirst(E e) {
    linkFirst(e);
}
public void addLast(E e) {
    linkLast(e);
}
public boolean add(E e) {
    linkLast(e);
    return true;
}
public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        // 在尾部添加
        linkLast(element);
    else
        // 在指定方位添加
        linkBefore(element, node(index));
}
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
// 在链表头部添加
private void linkFirst(E e) {
    // 1. 找到刺进方位的后继节点（first）
    final Node<E> f = first;
    // 2. 结构新节点
    // 3. 将新节点的 prev 指针指向前驱节点（null）
    // 4. 将新节点的 next 指针指向后继节点（f）
    // 5. 将前驱节点的 next 指针指向新节点（前驱节点是 null，所以没有这个进程）
    final Node<E> newNode = new Node<>(null, e, f);
    // 修正 first 指针
    first = newNode;
    if (f == null)
        // f 为 null 说明首个添加的元素，需求修正 last 指针
        last = newNode;
    else
        // 6. 将后继节点的 prev 指针指向新节点
        f.prev = newNode;
    size++;
    modCount++;
}
// 在链表尾部添加
void linkLast(E e) {
    final Node<E> l = last;
    // 1. 找到刺进方位的后继节点（null）
    // 2. 结构新节点
    // 3. 将新节点的 prev 指针指向前驱节点（l）
    // 4. 将新节点的 next 指针指向后继节点（null）
    final Node<E> newNode = new Node<>(l, e, null);
    // 修正 last 指针
    last = newNode;
    if (l == null)
        // l 为 null 说明首个添加的元素，需求修正 first 指针
        first = newNode;
    else
        // 5. 将前驱节点的 next 指针指向新节点
        l.next = newNode;
    // 6. 将后继节点的 prev 指针指向新节点（后继节点是 null，所以没有这个进程）
    size++;
    modCount++;
}
// 在指定节点前添加
// 1. 找到刺进方位的后继节点
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    // 2. 结构新节点
    // 3. 将新节点的 prev 指针指向前驱节点（pred）
    // 4. 将新节点的 next 指针指向后继节点（succ）
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        // 5. 将前驱节点的 next 指针指向新节点
        pred.next = newNode;
    size++;
    modCount++;
}
// 在指定方位添加整个调集元素
// index 为 0：在链表头部添加
// index 为 size：在链表尾部添加
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    // 事实上，c.toArray() 的实践类型不一定是 Object[]，有可能是 String[] 等
    // 不过，咱们是经过 Node中的item 接受的，所以不用担心 ArrayList 中的 ArrayStoreException 问题
    Object[] a = c.toArray();
    // 添加的数组为空，跳过
    int numNew = a.length;
    if (numNew == 0)
        return false;
    // 1. 找到刺进方位的后继节点
    // pred：刺进方位的前驱节点
    // succ：刺进方位的后继节点
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 找到 index 方位原本的节点，刺进后变成后继节点
        succ = node(index);
        pred = succ.prev;
    }
    // 刺进调集元素
    for (Object o : a) {
        E e = (E) o;
        // 2. 结构新节点
        // 3. 将新节点的 prev 指针指向前驱节点
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            // pred 为 null 说明是在头部刺进，需求修正 first 指针
            first = newNode;
        else
            // 5. 将前驱节点的 next 指针指向新节点
            pred.next = newNode;
        // 修正前驱指针
        pred = newNode;
    }
    if (succ == null) {
        // succ 为 null 说明是在尾部刺进，需求修正 last 指针
        last = pred;
    } else {
        // 4. 将新节点的 next 指针指向后继节点
        pred.next = succ;
        // 6. 将后继节点的 prev 指针指向新节点
        succ.prev = pred;
    }
    // 数量添加 numNew
    size += numNew;
    modCount++;
    return true;
}
// 将 LinkedList 转化为 Object 数组
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}

在链表中心添加节点时，会用到 node(index) 办法查询指定方位的节点。可以看到保持 first 和 last 头尾节点的作用又发挥出来了：

• 假如索引方位小于 size/2，则从头节点开端找；
• 假如索引方位大于 size/2，则从尾节点开端找。

虽然，咱们从复杂度剖析的视点看，从哪个方向查询是没有差异的，时刻复杂度都是 O(n)。但从工程剖析的视点看仍是有差异的，从更接近目标节点的方位开端查询，实践履行的时刻会更短。

查询指定方位节点

// 寻找指定方位的节点，时刻复杂度：O(n)
Node<E> node(int index) {
    if (index < (size >> 1)) {
        // 假如索引方位小于 size/2，则从头节点开端找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 假如索引方位大于 size/2，则从尾节点开端找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

LinkedList 的删去办法其实便是添加办法的逆运算，咱们就不重复剖析了。

// 删去头部元素
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
// 删去尾部元素
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
// 删去指定元素
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

---

2.4 LinkedList 的迭代器

Java 的 foreach 是语法糖，本质上也是选用 iterator 的办法。因为 LinkedList 自身便是双向的，所以 LinkedList 只供给了 1 个迭代器：

• ListIterator listIterator()： 双向迭代器

与其他容器类一样，LinkedList 的迭代器中都有 fail-fast 机制。假如在迭代的进程中发现 expectedModCount 变化，说明数据被修正，此刻就会提早抛出 ConcurrentModificationException 反常（当然也不一定是被其他线程修正）。

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}
// 非静态内部类
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    // 创建迭代器时会记录外部类的 modCount
    private int expectedModCount = modCount;
    ListItr(int index) {
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
    public E next() {
        // 更新 expectedModCount
        checkForComodification();
        ...
    }
    ...
}

2.5 LinkedList 的序列化进程

• ‍♀️疑问 2：为什么字段都声明 transient 关键字？

LinkedList 重写了 JDK 序列化的逻辑，不序列化链表节点，而只是序列化链表节点中的有用数据，这样序列化产物的大小就有所下降。在反序列时，只需求按照对象顺序顺次添加到链表的结尾，就能康复链表的顺序。

// 序列化和反序列化只考虑有用数据
// 序列化进程
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();
    // 写入链表长度
    s.writeInt(size);
    // 写入节点上的有用数据
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}
// 反序列化进程
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();
    // 读取链表长度
    int size = s.readInt();
    // 读取有用元素并用 linkLast 添加到链表尾部
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}

2.6 LinkedList 怎么完结线程安全？

有 5 种办法：

• 办法 1 – 运用 Collections.synchronizedList 包装类： 原理也是在所有办法上添加 synchronized 关键字；
• 办法 2 – 运用 ConcurrentLinkedQueue 容器类： 根据 CAS 无锁完结的线程安全行列；
• 办法 3 – 运用 LinkedBlockingQueue 容器： 根据加锁的堵塞行列，适合于带堵塞操作的生产者顾客模型；
• 办法 4 – 运用 LinkedBlockingDeque 容器： 根据加锁的堵塞双端行列，适合于带堵塞操作的生产者顾客模型；
• 办法 5 – 运用 ConcurrentLinkedDeque 容器类： 根据 CAS 无锁完结的线程安全双端行列。

---

3. 总结

• 1、LinkedList 是根据链表的线性表，一起具有 List、Queue 和 Stack 的行为；

• 2、在查询指定方位的节点时，假如索引方位小于 size/2，则从头节点开端找，否则从尾节点开端找；

• 3、LinkedList 重写了序列化进程，只处理链表节点中有用的元素；

• 4、LinkedList 和 ArrayList 都不考虑线程同步，不保证线程安全。

在上一篇文章里，咱们提到了 List 的数组完结 ArrayList，而 LinkedList 不只是 List 的链表完结，一起仍是 Queue 和 Stack 的链表完结。那么，在 Java 中的 Queue 和 Stack 的数组完结是什么呢，这个咱们在下篇文章评论，请关注。

---

本文为稀土技术社区首发签约文章，14天内制止转载，14天后未获授权制止转载，侵权必究！