[자료구조] 단일연결리스트 reverse 메서드 구현 (java)

단일연결리스트의 reverse 메서드를 구현해봅시다. 단일연결리스트의 객체는 head 정보, 그리고 노드는 다음 노드 정보만 가지고 있는 가장 단순한 형태의 단일연결리스트입니다. 코드로 표현하면 다음과 같습니다.

public class SinglyLinkedList {

    Node head;

    static class Node {
        int data;
        Node next;
    }
 }

코드를 복잡하게 만들지 않기 위해서 toString()이나 add() 메서드는 이미 구현되어 있다고 가정하겠습니다.

public class UnitTest {

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);

        System.out.println(list);
    }
}

실행 결과

1 -> 2 -> 3 -> 4 

 

이제 여기에 reverse() 메서드를 구현해서 다음과 같은 결과가 나올 수 있도록 하는 것이 목표입니다.

public class UnitTest {

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);

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

        System.out.println(list);
    }
}

실행 결과

1 -> 2 -> 3 -> 4
4 -> 3 -> 2 -> 1 

 

접근법

1. head를 시작점으로 현재 노드를 가리키는 current와 current의 이전 노드를 가리키는 prev를 선언합니다.

2. current의 next 노드가 prev를 가리키도록 합니다.

3. current와 prev를 한 칸씩 뒤로 옮깁니다.

4. current가 null이 될때까지 2,3을 반복합니다.

5. prev가 가리키는 노드를 head로 선언하고 종료합니다.

말로 하면 이해가 잘 안되니 그림으로 살펴봅시다.

 

처음 리스트의 모습입니다.

 

prev를 null로 초기화하고, 현재 head가 가리키는 노드를 current가 가리키도록 합니다. 그리고 current가 가리키고 있는 노드가 prev를 다음 노드로 가리키도록 만듭니다.

 

current와 prev를 한 칸씩 뒤로 옮기면서 current가 null이 될때까지 같은 과정을 반복합니다.

 

current가 null을 가리키면 반복을 종료하고, 이때 prev가 가리키는 노드가 head가 되도록 만들어줍니다.

 

이를 코드로 구현하면 다음과 같습니다. 아이디어 자체는 어렵지 않지만, current를 뒤로 한 칸씩 옮길 수 있도록 next라는 변수에 current의 next 노드를 미리 저장해놓는 부분에서 조금 헷갈렸네요.

public void reverse() {
    Node prev = null;
    Node current = head;

    while (current != null) {
        Node next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    head = prev;
}