C++에서 단일 연결 리스트를 순환 연결 리스트로 변환하는 방법

이 튜토리얼에서는 단일 연결 리스트(Singly Linked List)를 순환 연결 리스트(Circular Linked List)로 변환하는 프로그램을 C++로 구현하는 방법을 알아보겠습니다.

단일 연결 리스트가 주어졌을 때, 마지막 노드가 다시 첫 번째 노드를 가리키도록 만들어 순환 연결 리스트로 바꾸는 것이 우리의 목표입니다.

변환 원리

단일 연결 리스트의 마지막 노드는 next 포인터가 NULL을 가리킵니다. 따라서 변환 과정은 매우 간단합니다.

리스트의 처음(head) 노드 주소를 저장해 둡니다.
next가 NULL이 될 때까지 노드를 순회하며 마지막 노드를 찾습니다.
마지막 노드의 next가 저장해 둔 시작 노드를 가리키도록 설정합니다.

이렇게 하면 리스트의 끝이 다시 시작점과 연결되어 원형 구조가 완성됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 연결 리스트의 노드 구조체
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 단일 연결 리스트를
// 순환 연결 리스트로 변환하는 함수
Node* circular(Node* head){
    Node* start = head;          // 시작 노드 저장
    while (head->next != NULL)
        head = head->next;       // 마지막 노드까지 이동
    // 마지막 노드의 next가 시작 노드를 가리키도록 설정
    head->next = start;
    return start;
}

// 새 노드를 리스트 앞에 추가하는 함수
void push(Node** head, int data){
    // 새 노드 생성
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;        // 데이터 저장
    newNode->next = (*head);     // 기존 head를 next로 연결
    (*head) = newNode;           // head 갱신
}

// 순환 연결 리스트의 요소를 출력하는 함수
void print_list(Node* node){
    Node* start = node;
    while (node->next != start) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("%d ", node->data);
}

int main(){
    Node* head = NULL;
    push(&head, 15);
    push(&head, 14);
    push(&head, 13);
    push(&head, 22);
    push(&head, 17);

    circular(head);              // 순환 연결 리스트로 변환

    printf("Display list: \n");
    print_list(head);
    return 0;
}

실행 결과

Display list:
17 22 13 14 15

코드 설명

circular() 함수는 핵심 로직을 담당합니다. 먼저 시작 노드를 start 변수에 저장한 뒤, while 반복문으로 리스트의 마지막 노드까지 이동합니다. 그리고 마지막 노드의 next 포인터가 start를 가리키도록 대입하면 순환 연결 리스트가 완성됩니다.

print_list() 함수는 무한 루프에 빠지지 않도록 주의해야 합니다. 일반 연결 리스트처럼 NULL을 조건으로 사용할 수 없기 때문에, 다시 시작 노드로 돌아오는 시점(node->next == start)을 종료 조건으로 사용합니다. 마지막 노드의 데이터는 반복문 밖에서 한 번 더 출력하여 누락되지 않게 처리했습니다.

시간 복잡도는 리스트를 한 번 순회하므로 O(n)이며, 추가 공간 없이 포인터만 변경하므로 공간 복잡도는 O(1)입니다.