在 Java 中反轉 ArrayList
一、概述
ArrayList
是 Java 中常用的List
實現。
在本教程中,我們將探討如何反轉ArrayList
。
2. 問題介紹
像往常一樣,讓我們通過一個例子來理解這個問題。假設我們有一個Integer
List
:
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
反轉之後,我們期望得到結果:
List<Integer> EXPECTED = new ArrayList<>(Arrays.asList(7, 6, 5, 4, 3, 2, 1));
所以,這個要求看起來很簡單。但是,該問題可能有幾個變體:
- 將
List
反轉到位 - 反轉
List
並將結果作為新的List
對象返回
我們將在本教程中介紹這兩種情況。
Java 標準庫提供了一個輔助方法來完成這項工作。我們將看到如何使用這種方法快速解決問題。
此外,考慮到我們中的一些人可能正在學習 Java,我們將討論兩個有趣但有效的反轉List
的實現。
接下來,讓我們看看他們的行動。
3. 使用標準Collections.reverse
方法
Java 標準庫提供了[Collections.reverse](https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#reverse-java.util.List-)
方法來反轉給定List
中元素的順序。
這種方便的方法進行就地反轉,這將反轉它收到的原始列表中的順序。但是,首先,讓我們創建一個單元測試方法來理解它:
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
Collections.reverse(aList);
assertThat(aList).isEqualTo(EXPECTED);
當我們執行上面的測試時,它通過了。正如我們所見,我們將aList
對像傳遞給reverse
方法,然後aList
對像中元素的順序被反轉。
如果我們不想更改原始List
,並希望獲得一個新的List
對像以包含相反順序的元素,我們可以將一個新的List
對像傳遞給reverse
方法:
List<Integer> originalList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
List<Integer> aNewList = new ArrayList<>(originalList);
Collections.reverse(aNewList);
assertThat(aNewList).isNotEqualTo(originalList).isEqualTo(EXPECTED);
這樣,我們保持originalList
不變, aNewList
中元素的順序顛倒了。
正如我們從上面的兩個示例中看到的,標準的Collections.reverse
方法對於反轉List
非常方便。
但是,如果我們正在學習 Java,我們可能希望自己練習實現“反向”方法。
接下來,讓我們探索幾個不錯的實現:一個使用遞歸,另一個使用簡單循環。
4. 使用遞歸反轉List
首先,讓我們使用遞歸技術實現我們自己的 list-reverse 方法。首先,讓我們看一下實現:
public static <T> void reverseWithRecursion(List<T> list) {
if (list.size() > 1) {
T value = list.remove(0);
reverseWithRecursion(list);
list.add(value);
}
}
正如我們所看到的,上面的實現看起來非常緊湊。現在,讓我們了解它是如何工作的。
我們遞歸邏輯中的停止條件是list.size() <=1
。換句話說,如果list
對象為空或只包含一個元素,我們停止遞歸。
在每個遞歸調用中,我們執行“ T value = list.remove(0)
”,從列表中彈出第一個元素。它以這種方式工作:
recursion step 0: value = null, list = (1, 2, 3, ... 7)
|_ recursion step 1: value = 1, list = (2, 3, 4,...7)
|_ recursion step 2: value = 2, list = (3, 4, 5, 6, 7)
|_ recursion step 3: value = 3, list = (4, 5, 6, 7)
|_ ...
|_ recursion step 6: value = 6, list = (7)
如我們所見,當list
對象僅包含一個元素(7)時,我們停止遞歸,然後從底部開始執行list.add(value)
。也就是說,我們首先將 6 添加到列表的末尾,然後是 5,然後是 4,以此類推。最後,列表中元素的順序已經就地顛倒了。此外,該方法以線性時間運行。
接下來,讓我們創建一個測試來驗證我們的遞歸實現是否按預期工作:
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithRecursion(aList);
assertThat(aList).isEqualTo(EXPECTED);
如果我們運行測試,它就會通過。所以,我們的遞歸實現解決了這個問題。
5. 使用迭代反轉List
我們剛剛使用遞歸反轉了列表。或者,我們可以使用迭代來解決問題。
首先,讓我們看一下實現:
public static <T> void reverseWithLoop(List<T> list) {
for (int i = 0, j = list.size() - 1; i < j; i++) {
list.add(i, list.remove(j));
}
}
正如我們所看到的,迭代實現也非常簡潔。但是,我們只有一個for
循環,在循環體中,我們只有一個語句。
接下來,讓我們了解它是如何工作的。
我們在給定的列表上定義了兩個指針i
和j
。指針j
始終指向列表中的最後一個元素。但是點i
從 0 增加到**j-1** .
我們在每個迭代步驟中刪除最後一個元素,並使用list.add(i, list.remove(j))
將其填充到第i-th
位置。當i
到達j-1
時,循環結束,我們反轉了列表:
Iteration step 0: i = j = null, list = (1, 2, 3,...7)
Iteration step 1: i = 0; j = 6
|_ list.add(0, list.remove(6))
|_ list = (7, 1, 2, 3, 4, 5, 6)
Iteration step 2: i = 1; j = 6
|_ list.add(1, list.remove(6))
|_ list = (7, 6, 1, 2, 3, 4, 5)
...
Iteration step 5: i = 4; j = 6
|_ list.add(4, list.remove(6))
|_ list = (7, 6, 5, 4, 3, 1, 2)
Iteration step 6: i = 5; j = 6
|_ list.add(5, list.remove(6))
|_ list = (7, 6, 5, 4, 3, 2, 1)
該方法也以線性時間運行。
最後,讓我們測試一下我們的方法,看看它是否按預期工作:
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithLoop(aList);
assertThat(aList).isEqualTo(EXPECTED);
當我們運行上面的測試時,它通過了。
六,結論
在本文中,我們通過示例介紹瞭如何反轉ArrayList
。標準的Collections.reverse
方法可以很方便地解決這個問題。
但是,如果我們想創建自己的逆向實現,我們已經學習了兩種有效的就地逆向方法。
像往常一樣,本文的完整代碼可以在 GitHub 上找到。