원형 이중 연결 리스트 역순 출력, 뒤집기(reverse)

원형 이중 연결 리스트는 이전 노드와 다음 노드를 가리키는 포인터가 2개 존재하기 때문에 역순으로 만드는 작업은 복잡한 작업입니다.

원형 이중 연결 리스트 역순으로 출력하기

역순으로 출력하는 작업은 간단합니다. start 지점에서 prev로 리스트에 가장 뒤쪽에 있는 노드로 이동한 다음에 prev를 통해서 start까지 출력하면됩니다.

static void reversePrint(Node n) {
    if(start == null) return;

    do {
        System.out.println(n.prev.data);
        n = n.prev;		
    } while(start != n);
}

 

원형 이중 연결 리스트 뒤집기(모든 노드)

모든 노드의 next와 prev 포인터를 서로 교환해주면됩니다. 그리고 마지막에 start를 업데이트를 해주면 됩니다.

static void reverse2() {
    if (start == null || start.next == start) {
        return;
    }

    Node current = start;
    Node temp = null;
    do {
        temp = current.prev;
        current.prev = current.next;
        current.next = temp;

        current = current.prev;
    } while (current != start);

    start = temp.prev;
}

 

원형 이중 연결 리스트 뒤집기(모든 노드에서 반만큼 줄이기)

원형 이중 연결 리스트의 특성을 이해하고 리스트 첫번째와 마지막 노드를 교환하고 두번째와 마지막 -1번째 노드를 교환하는 방법으로 진행합니다.

static void reverse() {
    Node newHead = start.prev;

    Node curr = start;
    Node prev = curr.prev;

    while(true) {
        Node prevNext = prev.next;
        Node currPrev = curr.prev;
        prev.next = prev.prev;		
        curr.prev = curr.next;		
        prev.prev = prevNext;
        curr.next = currPrev;

        if(prev.next == curr || prev == curr) break;

        curr = curr.prev;
        prev = prev.next;
    }

    start = newHead;
}

종료 조건은 노드가 짝수일때 prev.next == curr의 조건으로 중앙 값이 바뀔때를 의미합니다.

노드가 홀수일때는 prev == curr로 중앙에 있는 노드를 가리킬때 탈출합니다.