ArrayList和LinkedList的区别和应用

ArrayList基于动态数组，适合频繁随机访问和遍历；LinkedList基于双向链表，适合频繁在任意位置插入删除。选择依据操作模式：读多用ArrayList，增删多用LinkedList。

ArrayList和LinkedList，它们都是Java集合框架中

List

解决方案

理解ArrayList和LinkedList的根本区别，要从它们的内部实现说起。

ArrayList，顾名思义，是基于动态数组实现的。这意味着它在内存中是一块连续的空间，每个元素都有一个明确的索引。当你通过

get(index)

System.arraycopy

LinkedList 则完全不同，它基于双向链表实现。列表中的每个元素（节点）都包含数据本身，以及指向前一个元素和后一个元素的引用（指针）。这种非连续的存储方式，使得它在内存中可能分散在各个地方。因此，如果你想通过索引

get(index)

何时选择ArrayList？场景分析与性能考量

我个人在项目实践中，如果不是有明确的理由，通常会倾向于先使用ArrayList。原因很简单，在大多数业务场景下，数据的读取和遍历操作远多于中间位置的增删。

ArrayList的优势场景主要体现在：

• 频繁的随机访问和遍历： 如果你的应用需要通过索引快速获取元素，或者需要高效地遍历整个列表，ArrayList的O(1)随机访问和良好的缓存局部性（因为元素在内存中是连续的）会带来卓越的性能。比如，你需要根据用户的输入，快速查找某个特定位置的数据，或者你需要对列表中的所有元素进行迭代处理。

  List userNames = new ArrayList<>();
  userNames.add("Alice");
  userNames.add("Bob");
  // ... 添加更多用户
  
  // 快速通过索引获取元素
  String user = userNames.get(5); // O(1)
  
  // 高效遍历
  for (String name : userNames) {
      System.out.println(name); // 缓存友好，遍历速度快
  }

• 数据量相对稳定或只在末尾添加： 如果你的列表数据在创建后很少变动，或者大部分添加操作都发生在列表的末尾，ArrayList的表现会非常好。在末尾添加元素通常是摊还O(1)的，因为只有在容量不足时才需要扩容。

• 内存使用效率（相对而言）： 虽然扩容可能带来复制开销，但ArrayList每个元素只存储数据本身，而LinkedList每个节点还需要额外的两个指针（前驱和后继），这使得在存储相同数量的元素时，ArrayList的内存占用可能会更小（尤其是在元素对象本身不大的情况下）。

需要注意的是，即使ArrayList在中间插入或删除是O(n)，对于小规模列表，这种性能差异可能并不明显。但在处理大量数据时，选择不当可能会导致严重的性能问题。

魔乐社区

天翼云和华为联合打造的AI开发者社区，支持AI模型评测训练、全流程开发应用

下载

LinkedList的独特优势：频繁增删改操作的最佳拍档

当你的应用场景需要频繁地在列表的任意位置进行插入、删除操作时，LinkedList的链式结构就显得尤为强大。

LinkedList的优势场景主要包括：

• 实现队列（Queue）和双端队列（Deque）： LinkedList是

  Queue

  和

  Deque

  接口的经典实现。由于它可以在两端高效地添加和删除元素（

  addFirst()

  ,

  addLast()

  ,

  removeFirst()

  ,

  removeLast()

  都是O(1)），非常适合用作先进先出（FIFO）的队列或先进后出（LIFO）的栈。

  import java.util.LinkedList;
  import java.util.Queue;
  
  Queue messageQueue = new LinkedList<>();
  messageQueue.offer("Message 1"); // 添加到队尾 O(1)
  messageQueue.offer("Message 2");
  String nextMessage = messageQueue.poll(); // 从队头取出 O(1)

• 频繁在列表中间插入或删除元素： 设想一个场景，你有一个日志列表，需要根据某些条件在任意位置插入新的日志条目，或者删除旧的日志。如果使用ArrayList，每次操作都可能导致大量元素移动。而LinkedList一旦找到目标位置，只需修改几个指针即可，操作是O(1)的。当然，找到目标位置本身可能需要O(n)的遍历，所以如果需要先通过索引查找，然后删除，整体仍然是O(n)。但如果操作是基于迭代器（例如在遍历时删除当前元素），那么删除操作就是O(1)。

  import java.util.Iterator;
  import java.util.LinkedList;
  
  LinkedList taskList = new LinkedList<>();
  taskList.add("Task A");
  taskList.add("Task B");
  taskList.add("Task C");
  
  // 使用迭代器在遍历时删除元素，效率高
  Iterator it = taskList.iterator();
  while (it.hasNext()) {
      String task = it.next();
      if ("Task B".equals(task)) {
          it.remove(); // O(1)
          break;
      }
  }
  // taskList 现在是 [Task A, Task C]

• 数据量不确定且操作集中在两端： 如果你对列表的大小没有预设，且大部分操作都发生在列表的头部或尾部，LinkedList能够避免ArrayList在扩容时可能带来的性能波动。

性能陷阱与常见误区：如何避免不当选择？

在选择ArrayList或LinkedList时，有一些常见的误区和性能陷阱需要避免。

1. 误区：LinkedList总是比ArrayList慢。 这不完全正确。虽然LinkedList的随机访问性能确实比ArrayList差，但它在中间增删操作上有着显著优势。如果你在一个LinkedList上进行大量的

get(index)

2. 陷阱：在LinkedList上进行索引访问后修改。 这是一个常见的误用模式。例如：

LinkedList myLinkedList = new LinkedList<>();
// ... 填充数据
for (int i = 0; i < myLinkedList.size(); i++) {
    // 每次get(i)都需要从头遍历，导致O(n^2)的性能
    String element = myLinkedList.get(i); 
    // ... 对element进行操作
}

这种代码在LinkedList上会产生O(n^2)的性能，因为每次

get(i)

for (String element : myLinkedList) {
    // 每次get(i)都需要从头遍历，导致O(n^2)的性能
    // ... 对element进行操作
}

使用迭代器遍历，LinkedList的遍历效率与ArrayList相近，都是O(n)，因为迭代器会记住当前位置。

3. 误区：ArrayList扩容很慢，应该避免。 ArrayList的扩容确实是一个O(n)的操作，涉及到新数组的创建和元素复制。但这个操作是分摊到每次添加操作上的。也就是说，如果你添加了m个元素，总的开销是O(m)，平均每次添加仍然是O(1)。因此，除非你确实遇到了频繁扩容导致的性能瓶颈（例如，你预估了列表大小，但没有在构造时指定初始容量，导致频繁小规模扩容），否则不必过度担心。我个人在实际开发中，如果预知列表会很大，会习惯性地在构造ArrayList时传入一个初始容量，比如

new ArrayList<>(1000)

4. 陷阱：不考虑并发性。 ArrayList和LinkedList都不是线程安全的。如果在多线程环境中使用，你需要手动进行同步，例如使用

Collections.synchronizedList()

java.util.concurrent

CopyOnWriteArrayList

总结一下我的看法： 大多数情况下，ArrayList是更安全、更通用的选择，因为它在最常见的操作（随机访问和遍历）上表现优异，并且其扩容机制通常不会成为主要瓶颈。只有当你明确知道你的应用需要频繁在列表的中间进行插入或删除操作，或者需要实现队列/栈等特定数据结构时，才应该考虑使用LinkedList。在不确定的时候，先用ArrayList，然后通过性能测试和分析来验证你的选择，这通常是更稳妥的开发流程。