1. 개요
ArrayList 는 Java에서자주 사용되는 List 구현입니다.
이 예제에서는 ArrayList 를 뒤집는 방법을 살펴보겠습니다 .
2. 문제 소개
늘 그렇듯이 예제를 통해 문제를 이해해 봅시다. 정수 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 메서드를 제공하여 지정된 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를 배우고 있다면 아마도 우리는 스스로 "reverse" 방법을 구현하는 연습을 하고 싶을 것입니다.
다음으로 몇 가지 멋진 구현을 살펴보겠습니다. 하나는 재귀를 사용하고 다른 하나는 간단한 루프를 사용합니다.
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) "를 실행하여 List에서 첫 번째 요소를 팝합니다. 다음과 같은 방식으로 작동합니다.
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) 실행을 시작합니다. 즉, 먼저 List 끝에 6을 추가한 다음 5, 4 등을 추가합니다. 결국 List의 요소 순서가 제자리에서 반전되었습니다. 또한 이 방법은 선형 시간으로 실행됩니다 .
다음으로 재귀 구현이 예상대로 작동하는지 확인하는 테스트를 만들어 보겠습니다.
List<Integer> aList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
ReverseArrayList.reverseWithRecursion(aList);
assertThat(aList).isEqualTo(EXPECTED);
테스트를 실행하면 통과합니다. 따라서 우리의 재귀 구현은 문제를 해결합니다.
5. 반복을 사용하여 List 뒤집기
재귀를 사용하여 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 루프 는 하나만 있고 루프 본문에는 하나의 단일 문만 있습니다.
다음으로 어떻게 작동하는지 이해합시다.
우리는 주어진 List에 두 개의 포인터 i 와 j 를 정의했습니다. 포인터 j는 항상 List의 마지막 요소를 가리킵니다. 그러나 포인트 i는 0에서 j-1 로 증가합니다 .
각 반복 단계에서 마지막 요소를 제거하고 list.add(i, list.remove(j)) 를 사용하여 i번째 위치 에 채웁니다 . i 가 j-1 에 도달 하면 루프가 종료되고 List을 뒤집었습니다.
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);
위의 테스트를 실행하면 통과합니다.
6. 결론
이 기사에서는 예제를 통해 ArrayList를 뒤집는 방법을 다루었습니다 . 표준 Collections.reverse 메서드는 이 문제를 해결하는 데 매우 편리합니다.
그러나 자체 역방향 구현을 만들고 싶다면 두 가지 효율적인 내부 역방향 접근 방식을 배웠습니다.
늘 그렇듯이 이 기사의 전체 코드는 GitHub 에서 찾을 수 있습니다 .
