MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Java ArrayList 与 LinkedList 的对比

2022-06-294.6k 阅读

一、基础概念

1.1 ArrayList 概述

ArrayList 是 Java 集合框架中 List 接口的一个可变大小数组的实现。它允许我们动态地添加和删除元素，并且可以像数组一样通过索引访问元素。从本质上来说，ArrayList 是基于数组的数据结构，这意味着它在内存中是连续存储的。

以下是创建一个 ArrayList 的基本示例：

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        System.out.println(arrayList);
    }
}

在上述代码中，我们首先创建了一个 ArrayList 对象，它可以存储 Integer 类型的元素。然后通过 add 方法向列表中添加元素，最后打印整个列表。

1.2 LinkedList 概述

LinkedList 同样实现了 List 接口，它是基于链表的数据结构。链表中的每个节点包含了数据以及指向前一个节点和后一个节点的引用（双向链表）。这使得 LinkedList 在插入和删除元素时不需要移动大量数据，因为只需要调整节点之间的引用关系。

以下是创建一个 LinkedList 的基本示例：

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println(linkedList);
    }
}

此代码与 ArrayList 的示例类似，只不过我们使用的是 LinkedList 来存储 Integer 类型的元素。

二、内存结构差异

2.1 ArrayList 的内存结构

ArrayList 内部使用数组来存储元素。数组在内存中是连续分配的一块区域，这就意味着当我们创建一个 ArrayList 时，系统会为其分配一段连续的内存空间来存储元素。例如，如果我们创建一个初始容量为 10 的 ArrayList，系统会在内存中分配一块可以容纳 10 个元素的连续空间。

当 ArrayList 的元素数量超过其当前容量时，它会进行扩容。扩容的过程涉及到创建一个新的更大的数组，然后将原数组中的所有元素复制到新数组中。这一操作在内存和时间上都有一定的开销。

2.2 LinkedList 的内存结构

LinkedList 的内存结构基于链表，链表中的每个节点都是独立的对象，在内存中并不一定是连续存储的。每个节点除了存储实际的数据之外，还包含两个引用，一个指向前一个节点（前驱节点），另一个指向后一个节点（后继节点）。

这种内存结构使得 LinkedList 在插入和删除元素时，只需要调整节点之间的引用关系，而不需要像 ArrayList 那样移动大量元素的内存位置。但是，由于每个节点都需要额外的空间来存储引用，LinkedList 相对于 ArrayList 来说会占用更多的内存空间。

三、性能对比

3.1 随机访问性能

3.1.1 ArrayList 的随机访问

由于 ArrayList 基于数组结构，它支持高效的随机访问。通过索引直接访问数组中的元素是非常快速的，时间复杂度为 O(1)。这是因为数组在内存中是连续存储的，根据索引可以直接计算出元素在内存中的位置，从而快速获取到该元素。

以下是一个演示 ArrayList 随机访问性能的示例：

import java.util.ArrayList;
import java.util.List;

public class ArrayListRandomAccess {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < 1000000; i++) {
            arrayList.add(i);
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            int value = arrayList.get(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList 随机访问时间: " + (endTime - startTime) + " 毫秒");
    }
}

在这个示例中，我们向 ArrayList 中添加了一百万个元素，然后通过 get 方法进行一百万次随机访问，并记录访问所花费的时间。

3.1.2 LinkedList 的随机访问

LinkedList 不支持高效的随机访问。要访问链表中的某个元素，必须从链表的头部（或尾部）开始，沿着链表逐个节点地遍历，直到找到目标节点。这使得随机访问的时间复杂度为 O(n)，其中 n 是链表中节点的数量。

以下是一个演示 LinkedList 随机访问性能的示例：

import java.util.LinkedList;
import java.util.List;

public class LinkedListRandomAccess {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 1000000; i++) {
            linkedList.add(i);
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            int value = linkedList.get(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("LinkedList 随机访问时间: " + (endTime - startTime) + " 毫秒");
    }
}

同样，我们向 LinkedList 中添加了一百万个元素，并进行一百万次随机访问，通过对比时间可以明显看出 LinkedList 在随机访问性能上远远低于 ArrayList。

3.2 插入和删除性能

3.2.1 ArrayList 的插入和删除

在 ArrayList 中插入和删除元素的性能取决于插入或删除的位置。如果在列表的末尾进行插入或删除操作，时间复杂度为 O(1)，因为不需要移动其他元素。然而，如果在列表的中间或开头进行插入或删除操作，就需要移动大量元素，时间复杂度为 O(n)。

以下是在 ArrayList 中间插入元素的示例：

import java.util.ArrayList;
import java.util.List;

public class ArrayListInsertion {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < 1000000; i++) {
            arrayList.add(i);
        }

        long startTime = System.currentTimeMillis();
        arrayList.add(500000, 999999);
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList 在中间插入时间: " + (endTime - startTime) + " 毫秒");
    }
}

在上述代码中，我们在已经包含一百万个元素的 ArrayList 的中间位置（索引为 500000）插入一个新元素，并记录插入操作所花费的时间。

3.2.2 LinkedList 的插入和删除

LinkedList 在插入和删除元素方面表现出色，无论在链表的任何位置进行插入或删除操作，时间复杂度都为 O(1)。这是因为它只需要调整节点之间的引用关系，而不需要移动大量数据。

以下是在 LinkedList 中间插入元素的示例：

import java.util.LinkedList;
import java.util.List;

public class LinkedListInsertion {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 1000000; i++) {
            linkedList.add(i);
        }

        long startTime = System.currentTimeMillis();
        linkedList.add(500000, 999999);
        long endTime = System.currentTimeMillis();
        System.out.println("LinkedList 在中间插入时间: " + (endTime - startTime) + " 毫秒");
    }
}

通过对比可以发现，LinkedList 在中间插入元素的时间远远小于 ArrayList，这体现了链表结构在插入和删除操作上的优势。

3.3 遍历性能

3.3.1 ArrayList 的遍历

ArrayList 可以使用多种方式进行遍历，如普通的 for 循环、增强型 for 循环和迭代器。使用普通 for 循环进行遍历是最快的，因为它直接通过索引访问元素，时间复杂度为 O(n)。增强型 for 循环本质上也是通过迭代器实现的，不过它更加简洁。

以下是使用普通 for 循环遍历 ArrayList 的示例：

import java.util.ArrayList;
import java.util.List;

public class ArrayListTraversal {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < 1000000; i++) {
            arrayList.add(i);
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < arrayList.size(); i++) {
            int value = arrayList.get(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList 使用普通 for 循环遍历时间: " + (endTime - startTime) + " 毫秒");
    }
}

3.3.2 LinkedList 的遍历

LinkedList 遍历方式同样包括普通 for 循环、增强型 for 循环和迭代器。由于 LinkedList 不支持高效的随机访问，使用普通 for 循环遍历的效率较低，时间复杂度为 O(n^2)，因为每次通过索引访问元素都需要从链表头开始遍历。而使用迭代器遍历则更为高效，时间复杂度为 O(n)。

以下是使用迭代器遍历 LinkedList 的示例：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class LinkedListTraversal {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 1000000; i++) {
            linkedList.add(i);
        }

        long startTime = System.currentTimeMillis();
        Iterator<Integer> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            int value = iterator.next();
        }
        long endTime = System.currentTimeMillis();
        System.out.println("LinkedList 使用迭代器遍历时间: " + (endTime - startTime) + " 毫秒");
    }
}

通过对比可以发现，在遍历操作上，根据不同的遍历方式，ArrayList 和 LinkedList 各有优劣。

四、应用场景

4.1 ArrayList 的应用场景

  • 频繁随机访问：如果应用程序需要频繁地根据索引访问列表中的元素，例如在一个存储学生成绩的列表中，经常需要根据学生的序号获取其成绩，那么 ArrayList 是一个很好的选择。因为它的随机访问性能高效，能够快速地定位到所需元素。
  • 数据量相对稳定：当数据量相对稳定，不会频繁进行插入和删除操作时，ArrayList 也是合适的。由于其基于数组的结构，在内存使用上相对紧凑，不会像 LinkedList 那样因为节点引用而占用过多额外空间。

4.2 LinkedList 的应用场景

  • 频繁插入和删除：在一些需要频繁在列表中间插入或删除元素的场景中，如实现一个任务队列，任务可能随时被插入到队列中间或从队列中间移除，LinkedList 的性能优势就非常明显。它能够快速地完成插入和删除操作，而不会像 ArrayList 那样因为大量元素移动而导致性能下降。
  • 内存空间有限：虽然 LinkedList 由于节点引用会占用更多内存空间，但在某些情况下，如果内存空间有限且不希望因为数组扩容而导致内存碎片等问题，LinkedList 可以作为一种选择。因为它不需要连续的内存空间来存储所有元素，只要有足够的离散内存空间来创建节点即可。

五、其他特性对比

5.1 内存占用

正如前面提到的，ArrayList 在内存占用方面相对紧凑，因为它基于数组结构，元素连续存储。而 LinkedList 每个节点除了存储数据还需要存储两个引用，这使得它在存储相同数量元素时，会比 ArrayList 占用更多的内存空间。

5.2 序列化性能

在序列化方面，ArrayList 相对简单。由于其基于数组，序列化过程可以直接将数组内容进行序列化。而 LinkedList 由于其链表结构，序列化时需要逐个处理每个节点，并且要处理节点之间的引用关系，这使得 LinkedList 的序列化过程相对复杂一些，性能也会稍低。

5.3 实现复杂度

从实现复杂度来看，ArrayList 的实现相对简单，主要围绕数组的操作，如扩容、元素的插入和删除等。而 LinkedList 的实现涉及到节点类的定义以及节点之间引用关系的维护，相对来说更为复杂。这也导致在代码维护和理解上，LinkedList 可能需要更多的精力。

六、代码示例综合对比

以下是一个综合示例，展示了 ArrayList 和 LinkedList 在不同操作上的性能差异：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListPerformanceComparison {
    public static void main(String[] args) {
        int size = 1000000;

        // ArrayList 操作
        List<Integer> arrayList = new ArrayList<>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("ArrayList 添加元素时间: " + (endTime - startTime) + " 毫秒");

        startTime = System.currentTimeMillis();
        arrayList.add(size / 2, 999999);
        endTime = System.currentTimeMillis();
        System.out.println("ArrayList 在中间插入元素时间: " + (endTime - startTime) + " 毫秒");

        startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            int value = arrayList.get(i);
        }
        endTime = System.currentTimeMillis();
        System.out.println("ArrayList 随机访问时间: " + (endTime - startTime) + " 毫秒");

        // LinkedList 操作
        List<Integer> linkedList = new LinkedList<>();
        startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            linkedList.add(i);
        }
        endTime = System.currentTimeMillis();
        System.out.println("LinkedList 添加元素时间: " + (endTime - startTime) + " 毫秒");

        startTime = System.currentTimeMillis();
        linkedList.add(size / 2, 999999);
        endTime = System.currentTimeMillis();
        System.out.println("LinkedList 在中间插入元素时间: " + (endTime - startTime) + " 毫秒");

        startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            int value = linkedList.get(i);
        }
        endTime = System.currentTimeMillis();
        System.out.println("LinkedList 随机访问时间: " + (endTime - startTime) + " 毫秒");
    }
}

通过运行上述代码，可以直观地看到 ArrayList 和 LinkedList 在添加元素、中间插入元素以及随机访问操作上的性能差异。

在实际应用中，根据具体的需求和场景，合理选择 ArrayList 或 LinkedList 对于优化程序性能至关重要。了解它们之间的差异，能够帮助开发者编写出更加高效、健壮的代码。无论是在数据处理、算法实现还是系统架构设计中，正确地使用这两种数据结构都能为项目带来显著的效益。