当前位置：首页 > news >正文

深入解析 ArrayList 与 LinkedList：Java 集合框架中的两大常用 List

news 2024/9/21 14:35:04

在 Java 的集合框架中，ArrayList 和 LinkedList 是两种常用的 List 实现类，它们都实现了 List 接口，提供了有序的元素存储方式，支持按索引访问和元素插入、删除等操作。然而，它们的底层实现不同，导致了性能上的差异。在实际开发中，如何选择合适的 List 实现类，直接关系到程序的性能和效率。

本文将详细探讨 ArrayList 和 LinkedList 的底层实现、优缺点以及适用场景，帮助你在实际开发中作出更合理的选择。

1. `ArrayList` 和 `LinkedList` 的基本概念

1.1 `ArrayList`

ArrayList 是基于动态数组实现的列表，它使用一个可动态调整大小的数组来存储元素。数组是连续内存空间，因此支持通过索引快速访问元素。由于数组的大小是固定的，ArrayList 在添加新元素时，可能需要扩容（即创建一个更大的数组并将元素复制到新数组中）。

1.2 `LinkedList`

LinkedList 是基于双向链表实现的列表，每个节点包含一个数据元素以及指向前一个节点和后一个节点的指针。链表的节点存储在不连续的内存地址中，插入和删除操作非常高效，但由于无法通过索引直接访问某个元素，因此随机访问性能较差。

2. 底层实现

2.1 `ArrayList` 的实现原理

ArrayList 的核心是一个动态数组，数组的默认初始容量为10。随着元素的添加，ArrayList 会根据需要自动扩容，每次扩容时，新数组的容量是原数组的 1.5 倍。

关键特点：

通过索引访问元素非常快速（时间复杂度为 O(1)）。
在末尾添加元素通常非常高效，但如果数组已满，扩容会影响性能（扩容时需要将所有元素复制到新数组中）。
插入和删除操作在非末尾位置时，需要移动大量元素，因此性能较差（时间复杂度为 O(n)）。

2.2 `LinkedList` 的实现原理

LinkedList 由双向链表实现，每个节点包含一个指向下一个节点和上一个节点的引用，元素并不存储在连续的内存地址中。

关键特点：

插入和删除元素时无需移动其他元素，性能较好（时间复杂度为 O(1)）。
通过索引访问某个元素需要遍历链表，性能较差（时间复杂度为 O(n)）。
占用更多内存，因为每个节点都需要额外的指针来指向前后节点。

3. 主要操作性能对比

操作	`ArrayList` 性能	`LinkedList` 性能
随机访问（按索引获取元素）	快，时间复杂度为 `O(1)`	慢，时间复杂度为 `O(n)`，需要遍历
在末尾添加元素	快，时间复杂度为 `O(1)`，但如果扩容则为 `O(n)`	快，时间复杂度为 `O(1)`
在中间插入/删除元素	慢，时间复杂度为 `O(n)`，因为需要移动元素	快，时间复杂度为 `O(1)`，只需更新指针
内存使用	内存开销较小，只存储元素	内存开销较大，存储元素外还要存储前后指针

4. 适用场景

4.1 何时使用 `ArrayList`

ArrayList 适用于以下场景：

频繁访问元素：如果应用程序的主要需求是通过索引快速获取元素，ArrayList 是最佳选择，因为它的随机访问性能优于 LinkedList。
少量插入和删除：如果插入和删除操作主要集中在列表的末尾，而不是中间位置，ArrayList 的性能会更好，因为它在末尾添加元素非常高效。

示例：`ArrayList` 用法

import java.util.ArrayList;public class ArrayListExample {public static void main(String[] args) {ArrayList<String> arrayList = new ArrayList<>();arrayList.add("Apple");arrayList.add("Banana");arrayList.add("Cherry");System.out.println("ArrayList elements:");for (String fruit : arrayList) {System.out.println(fruit);}// 通过索引访问元素System.out.println("Second element: " + arrayList.get(1));}
}

4.2 何时使用 `LinkedList`

LinkedList 适用于以下场景：

频繁插入和删除元素：如果你的应用程序需要在列表中频繁插入和删除元素，特别是在列表的中间或开头位置，LinkedList 是一个更好的选择，因为它的插入和删除操作性能优于 ArrayList。
需要频繁在两端操作：LinkedList 提供了额外的功能，如可以高效地在列表的开头和末尾插入、删除元素，适合队列或栈的实现。

示例：`LinkedList` 用法

import java.util.LinkedList;public class LinkedListExample {public static void main(String[] args) {LinkedList<String> linkedList = new LinkedList<>();linkedList.add("Apple");linkedList.add("Banana");linkedList.add("Cherry");System.out.println("LinkedList elements:");for (String fruit : linkedList) {System.out.println(fruit);}// 在开头和结尾插入元素linkedList.addFirst("Grapes");linkedList.addLast("Mango");System.out.println("After adding first and last elements:");for (String fruit : linkedList) {System.out.println(fruit);}}
}

5. 扩展：`Deque` 接口与 `LinkedList`

LinkedList 不仅仅是 List 的实现，它还实现了 Deque（双端队列）接口。Deque 提供了双向队列的功能，允许在两端插入和删除元素。因此，LinkedList 可以同时用作栈（Stack）和队列（Queue）。

使用 `LinkedList` 作为队列

LinkedList<String> queue = new LinkedList<>();
queue.add("First");
queue.add("Second");
queue.add("Third");System.out.println("Queue: " + queue);// 移除队列头部元素
queue.remove();
System.out.println("After removing: " + queue);

使用 `LinkedList` 作为栈

LinkedList<String> stack = new LinkedList<>();
stack.push("First");
stack.push("Second");
stack.push("Third");System.out.println("Stack: " + stack);// 弹出栈顶元素
stack.pop();
System.out.println("After popping: " + stack);

6. 选择 `ArrayList` 还是 `LinkedList`？

在实际开发中，选择 ArrayList 还是 LinkedList 取决于你对性能和使用场景的需求：

如果需要快速随机访问，选择 ArrayList。这是因为 ArrayList 通过索引访问的性能为 O(1)，而 LinkedList 需要遍历链表，性能为 O(n)。
如果需要频繁在列表的中间插入或删除元素，选择 LinkedList。在 ArrayList 中，插入或删除元素时需要移动元素，性能较低。
如果插入和删除操作集中在列表的两端，尤其是头部，可以选择 LinkedList，因为它对两端操作的性能是 O(1)，而 ArrayList 在头部插入或删除元素的性能为 O(n)。