Computer >> 컴퓨터 >  >> 프로그래밍 >> C 프로그래밍

C 언어로 단일 연결 리스트의 각 노드 값 뒤집기 프로그램

이 글에서는 연결 리스트가 주어졌을 때, 단일 연결 리스트(Singly Linked List)의 각 노드 값을 뒤집는 C 프로그램을 작성하는 방법을 알아봅니다. 여기서 말하는 '값을 뒤집는다'는 것은 노드의 순서를 바꾸는 것이 아니라, 각 노드에 저장된 정수의 자릿수 순서를 거꾸로 만드는 것을 의미합니다.

연결 리스트란 무엇인가?

연결 리스트(Linked List)는 데이터와 다음 노드를 가리키는 포인터를 함께 담고 있는 노드들이 사슬처럼 연결된 선형 자료구조입니다. 배열과 달리 메모리상에서 연속적으로 배치되지 않으며, 크기 변경과 삽입·삭제가 유연하다는 장점이 있습니다.

문제 이해하기

예시를 통해 문제를 살펴보겠습니다.

입력

34 12 89 56 72

출력

43 21 98 65 27

위 예시에서 첫 번째 노드의 값 34는 자릿수가 뒤집혀 43이 되고, 12는 21로, 89는 98로, 56은 65로, 72는 27로 변경됩니다. 즉, 리스트 전체를 순회하면서 각 노드의 값만 반전시키면 되는 것입니다.

문제 해결 접근 방법

이 문제는 다음 단계로 해결할 수 있습니다.

  1. 연결 리스트의 헤드(head) 노드부터 시작하여 마지막 노드까지 순회합니다.
  2. 현재 노드의 data 값을 자릿수 단위로 뒤집는 함수(reverseValue)를 호출한 뒤, 그 결과를 다시 data에 저장합니다.
  3. 다음 노드로 이동하며 모든 노드에 대해 위 과정을 반복합니다.

자릿수를 뒤집는 방법은 간단합니다. 주어진 수를 10으로 나눈 나머지(마지막 자릿수)를 추출하고, 결과 변수에 10을 곱한 후 해당 자릿수를 더하는 과정을 수가 0이 될 때까지 반복하면 됩니다.

C 프로그램: 단일 연결 리스트의 각 노드 값 뒤집기

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// 새 노드를 생성하는 함수
struct Node* insertNode(int key) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = key;
    temp->next = NULL;
    return temp;
}

// 정수의 자릿수를 뒤집는 함수
int reverseValue(int number) {
    int revElement = 0, rem;
    while (number != 0) {
        rem = number % 10;
        revElement = revElement * 10 + rem;
        number = number / 10;
    }
    return revElement;
}

// 연결 리스트의 모든 노드 값을 뒤집는 함수
void reverseLinkedListElements(struct Node* node) {
    if (node == NULL)
        return;
    while (node != NULL) {
        node->data = reverseValue(node->data);
        node = node->next;
    }
}

// 연결 리스트를 출력하는 함수
void printLinkedList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

int main() {
    struct Node* head = NULL;
    head = insertNode(34);
    head->next = insertNode(12);
    head->next->next = insertNode(89);
    head->next->next->next = insertNode(56);
    head->next->next->next->next = insertNode(72);

    printf("Original Linked List :\t");
    printLinkedList(head);

    reverseLinkedListElements(head);

    printf("\nAltered Linked List:\t");
    printLinkedList(head);

    return 0;
}

실행 결과

Original Linked List : 34 12 89 56 72
Altered Linked List: 43 21 98 65 27

코드 설명

  • insertNode(): malloc으로 새 노드를 동적 할당하여 생성하고, 데이터를 저장한 뒤 반환합니다.
  • reverseValue(): 나머지 연산(%)과 나눗셈(/)을 이용해 입력받은 정수의 자릿수를 하나씩 추출하여 역순으로 조립합니다.
  • reverseLinkedListElements(): 연결 리스트를 처음부터 끝까지 순회하며 각 노드의 data를 reverseValue()의 결과로 교체합니다.
  • printLinkedList(): 연결 리스트의 모든 값을 순서대로 화면에 출력합니다.

시간 및 공간 복잡도

시간 복잡도: O(n × d) — n은 노드의 개수, d는 각 노드 값의 평균 자릿수입니다. 각 노드마다 자릿수만큼의 연산이 수행되기 때문입니다.

공간 복잡도: O(1) — 추가적인 자료구조 없이 기존 노드의 값을 제자리(in-place)에서 수정하므로 상수 공간만 사용합니다.