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

ArrayList 和 LinkedList 之间的主要区别。在什么情况下你会选择使用 ArrayList 而不是 LinkedList，反之亦然？

article 2024/11/16 13:48:31

ArrayList 与 LinkedList 的主要区别

在 Java 中，ArrayList 和 LinkedList 是两种常用的集合类，它们都是 List 接口的实现。尽管它们都可以存储一系列元素，但它们在内部实现上有着显著的不同，这也决定了它们在性能上的差异。

ArrayList

ArrayList 是基于动态数组实现的，它在内存中分配一块连续的空间来存储元素。这意味着 ArrayList 支持随机访问，即可以通过索引快速地获取元素。但是，这也意味着在列表中间位置插入或删除元素的成本较高，因为这通常需要移动大量的元素。

代码示例

1List<String> arrayList = new ArrayList<>();
2arrayList.add("Element1");
3arrayList.add("Element2");
4arrayList.set(0, "NewElement1"); // 快速访问，O(1)
5System.out.println(arrayList.get(1)); // 快速访问，O(1)
6arrayList.remove(0); // 删除第一个元素，O(n)，因为后续元素需要前移
7arrayList.add(1, "InsertedElement"); // 在索引1处插入元素，O(n)，因为后续元素需要后移

LinkedList

LinkedList 是基于双向链表实现的。每个元素实际上是一个节点，每个节点包含指向其前一个节点和后一个节点的引用。因此，LinkedList 在插入和删除元素时具有较好的性能，因为它只需要更新相邻节点的引用即可。但是，由于链表的特性，随机访问元素的成本较高，因为可能需要从头开始遍历整个链表直到找到指定位置的元素。

代码示例

1List<String> linkedList = new LinkedList<>();
2linkedList.add("Element1");
3linkedList.add("Element2");
4// 不能像 ArrayList 一样使用 set 方法，而是使用 addFirst 或 addLast
5linkedList.addFirst("NewElement1"); // 插入头部，O(1)
6System.out.println(linkedList.getFirst()); // 访问头部元素，O(1)
7linkedList.removeFirst(); // 删除头部元素，O(1)
8linkedList.add(1, "InsertedElement"); // 在索引1处插入元素，O(n)，因为需要找到索引1的位置

选择 ArrayList 与 LinkedList 的场景

使用 ArrayList 的情况

当你需要频繁地根据索引访问元素时，例如当你需要遍历列表或需要通过索引进行查找时。
当你知道列表的大小不会经常改变或者列表的大小有限时，因为 ArrayList 在扩容时会复制现有的数组到新的更大的数组中，这是一个耗时的操作。
当列表中的大部分操作是在列表的尾部添加元素时，因为在这种情况下不需要移动任何元素。

使用 LinkedList 的情况

当你需要频繁地在列表中间位置插入或删除元素时，例如在一个需要不断添加或移除元素的队列中。
当列表的大小经常变化且不知道具体的大小时，因为 LinkedList 在插入或删除元素时不需要调整其他元素的位置。
当列表中的大部分操作是基于元素本身，而非基于索引时。

合理化的使用建议

性能优化
- 在选择集合类型时，首先考虑的是性能需求。如果需要快速的随机访问，选择 ArrayList；如果需要高效的插入和删除操作，选择 LinkedList。
- 对于 ArrayList，尽量预估列表的最大容量，并在创建时指定初始容量，以减少自动扩容带来的开销。
代码清晰性
- 选择适合业务场景的数据结构不仅能够提高程序的性能，还能使代码更清晰易懂。例如，如果实现一个队列，使用 LinkedList 可能会比使用 ArrayList 更直观。
并发安全
- 如果集合会被多个线程同时访问，那么要考虑使用线程安全的集合类，如 Vector 或 CopyOnWriteArrayList，或者手动管理同步，比如使用 Collections.synchronizedList(new LinkedList<>())。