如何将List<String>转换为ArrayList<String>

Question

该 API 调用 返回一个潜在的大型的 List<String>，其中元素没有排序。我需要对其进行排序、搜索和访问随机元素。目前该 List 的实现是 ArrayList（我已经检查过源代码），但是未来 API 开发人员可能会在不改变接口的情况下选择切换到 LinkedList 实现。

对可能很大的 LinkedList 进行排序、搜索和访问将非常缓慢且无法接受。因此，我需要将 List 转换为 ArrayList，以确保程序的实际效率。然而，由于该 List 很可能已经是 ArrayList，因此没有必要无谓地创建一个新的 ArrayList 副本。

鉴于这些限制，我提出了以下将 List 转换为 ArrayList 的方法：

private static <T> ArrayList<T> asArrayList(List<T> list) {
  if (list instanceof ArrayList) {
    return (ArrayList<T>) (list);
  } else {
    return new ArrayList<T>(list);
  }
}

我的问题是：这是处理具有未知实现的列表的最有效方法吗？是否有更好的方法将List转换为ArrayList？是否有比将List转换为ArrayList更好的选项？

- dln385

---

你有想过它可能有多大吗（大小）？除非它非常大并且会导致性能问题，否则我会使用复制构造函数。 - assylias

可能在5,000到50,000之间，而且这个方法会被调用成万次。 - dln385

在我的台式电脑上，使用复制构造函数对包含 100,000 个项目的列表进行操作只需要不到 0.5 毫秒（在 JIT 启动后）。现在转换速度快了约 1,000 倍;-) - assylias

Answer 1

你目前的代码已经非常简洁高效，看起来已经达到了最优化的效果。

虽然如此，这似乎是一种过早的优化行为。只有当你使用的 API 作者更改为 LinkedList 时才需要担心这个问题。如果现在就开始担心，你可能会花很多时间和精力计划未来的情况，而这些时间可能更好地用于解决其他问题。你可能只在更新自己应用程序版本之间更改 API 版本 - 如果真的需要处理这个问题，则可以在那时解决。

- Mac

Answer 2

正如您所看到的，代码简单且高效，只有在必要时才创建副本。

因此，答案是没有更好的选择，除非采用完全不同类型的解决方案，例如对列表进行排序。

（请记住，很少需要这种优化水平，因此这不是一个非常频繁的问题。）

更新：只是一个想法，通常情况下，编写良好的API不会返回不适合包含的数据量的数据类型。这并不是说您应该盲目信任它们，但这并不是一个完全不合理的假设。

- biziclop

Answer 3

排序、搜索、访问一个可能很大的LinkedList会极其缓慢，对于我的程序来说是无法接受的。

实际上，情况并不像那么糟糕。如果我没记错的话，Collections.sort方法将列表复制到一个临时数组中，对数组进行排序，清空原始列表并将数组复制回去。对于足够大的列表，O(NlogN)的排序阶段将支配O(N)的复制阶段。

- Stephen C

Answer 4

支持高效随机访问的Java集合实现RandomAccess标记接口。对于这样的列表，您可以直接在列表上运行Collections.sort。对于没有随机访问的列表，您应该使用其toArray方法之一将列表转储到数组中，对该数组进行排序，然后将其包装成随机访问List。

T[] array = (T[])list.toArray(); // just suppress the warning if the compiler worries about unsafe cast
Arrays.sort(array);
List<T> sortedList = Arrays.asList(array);

我认为Arrays.asList实际上创建了一个ArrayList，所以如果你喜欢的话，可以尝试将其结果强制转换。

Collections.sort对于所有List实现都是高效的，只要它们提供了高效的ListIterator。该方法将列表转储到数组中，对其进行排序，然后使用ListIterator在O(n)时间内将值复制回列表中。

- Wormbo

---

Arrays.asList()并不会创建一个ArrayList（好吧，它有点像，因为它返回一个Arrays.ArrayList内部类类型。:))，但是它创建的是由实际数组支持的列表。 - biziclop

啊，好的。这就是为什么给你的类命名很重要的原因。在同一个包中有两个同名的类，一个是公共顶级类，另一个是内部类，这会让人感到困惑。 :) - Wormbo

问我是怎么发现的 :) - biziclop