在 Java 中反转列表 - 就地和异地

由柏拉图重新发布

关注： 0

在这个简短的教程中，您将学习如何在 Java 中反转原地和非原地列表。

反转就地和异地

对列表执行操作时——您可能需要考虑这些操作是就地完成的（对原始对象进行更改），还是它们是否就地完成（对副本进行更改，而原始对象则执行更改）对象不变）。

一些语言和库喜欢不同的默认行为。在 Java 中，大多数反转列表的操作都是到位.

如果这是您想要的行为 - 太好了！如果没有，您需要在反转副本之前创建列表的副本：

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

请注意： clone() 方法不创建一个深层副本。使用创建列表 new ArrayList(list) 不创建一个深层副本。不鼓励创建深层副本，并且以通用方式很难做到（并且在某些情况下没有意义，具体取决于列表中的数据类型）。这不会阻止您逆转 list 和不能有元素 listCopy 被逆转，虽然。

集合.reverse()

Collections.reverse() 方法是反转集合的标准方法，并充当“缺失” List.reverse() 方法。它就地反转列表：

List list = new ArrayList(Arrays.asList(1, 2, 3));
List listCopy = new ArrayList(list);

Collections.reverse(list);

System.out.println(list);     
System.out.println(listCopy);

Guava 的 Lists.reverse(list)

如果您已经在项目中使用 Google Guava，您还可以利用 Lists 类，它提供 reverse() 方法，它不会就地对原始列表进行排序，而是创建一个副本并反转该副本：

List list = new ArrayList(Arrays.asList(1, 2, 3));
List reversedList = Lists.reverse(list);

System.out.println(list);         
System.out.println(reversedList);

如果您还没有它，您可以使用 Maven 将 Google Guava 添加到您的项目中，方法是将其依赖项包含在您的 pom.xml 文件：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
</dependency>

或通过 Gradle：

implementation group: 'com.google.guava', name: 'guava'

请注意： 如果您还没有 Google Guava，或者不打算将它用于项目的其他部分 - 不要只为这个操作导入它，并坚持 Collections.reverse() 方法。 Guava 是一个很大的依赖项，仅在此操作中使用它是一个主要的矫枉过正。

List.add() 和 List.remove()

如果您希望执行除了反转列表之外的其他操作 - 您可以遍历原始列表，从末尾删除元素，通过任意方法传递它们，然后将它们添加回列表的开头：


public static int process(int input) {
    return input;
}

List list = new ArrayList(Arrays.asList(1, 2, 3));

for (int i = 0, j = list.size()-1; i <= j; i++) {
    int lastValue = process(list.remove(j));
    list.add(i, lastValue);
}

System.out.println(list);

基准

那么，哪个最快？这还取决于您是要就地执行操作还是就地执行操作。

就地逆转基准

让我们在这三种方法上对这两种方法进行基准测试，从 out-of-place 开始：

List list = new Random().ints(100, 1, 11)
                .boxed()
                .collect(Collectors.toList());

int runs = 1000;

long start1 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListCollections(list);
}
long end1 = System.currentTimeMillis();
System.out.println(String.format("Collections.reverse() took: %s miliseconds", end1-start1));

long start2 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListGuava(list);
}
long end2 = System.currentTimeMillis();
System.out.println(String.format("Guava's Lists.reverse() took: %s miliseconds", end2-start2));

long start3 = System.currentTimeMillis();
for (int i = 0; i < runs; i++) {
    reverseListManually(list);
}
long end3 = System.currentTimeMillis();
System.out.println(String.format("Manually took: %s miliseconds", end3-start3));

System.out.println("Original list: " + list);

结果是：

Collections.reverse() took: 3 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 13 miliseconds
Original list: [6, 7, 9, 7, 2, 5, 4, 1, 3, 2, 2, 6, ...

查看我们的 Git 学习实践指南，其中包含最佳实践、行业认可的标准以及随附的备忘单。停止谷歌搜索 Git 命令，实际上学习它！

当我们将元素数量从 100 增加到 1000 时会发生什么？

Collections.reverse() took: 9 miliseconds
Guava's Lists.reverse() took: 4 miliseconds
Manually took: 133 miliseconds
Original list: [10, 2, 2, 6, 2, 4, 7, 3, 9, 2, 7, 5, ...

Guava 保留了 4ms 标记！手动方法的时间复杂度最差，并且呈线性上升。 Collections.reverse() 扩大规模受到的影响较小，但 Guava 的实施受到的影响最小。不过，请记住，我们不会手动复制 Guava 方法的列表。当我们放弃“原始”和“反向”列表的想法时，基准会改变吗？

异地逆转基准

当我们从每个方法中删除手动副本并重新运行代码时，有 1000 个元素，并且每个元素都在列表的非反向副本上运行（从时间测量中排除）：

Collections.reverse() took: 7 miliseconds
Guava's Lists.reverse() took: 3 miliseconds
Manually took: 131 miliseconds
Original list: [6, 8, 10, 7, 3, 8, 7, 1, 1, 9, 5, ...

番石榴仍然设法始终胜过两者 Collections.reverse() 和手动方法。