C언어에서 문자열을 연결 리스트로 다루는 방법

C언어에서 문자열은 고정 크기의 배열로 다뤄지는 경우가 많지만, 크기 변경이나 동적 할당이 필요한 상황에서는 비효율적일 수 있습니다. 이를 해결하기 위한 대안으로 연결 리스트를 활용한 문자열 처리가 있습니다. 연결 리스트를 사용하면 메모리를 동적으로 할당할 수 있어 문자열의 길이가 유동적이거나 대규모 데이터를 처리해야 하는 경우에 유리합니다. 본 기사에서는 연결 리스트를 통해 문자열을 다루는 기본 개념부터 고급 응용 방법까지 자세히 다룹니다. 이를 통해 메모리 효율성과 코드 유지 보수성을 향상시킬 수 있는 방법을 이해할 수 있을 것입니다.

문자열과 연결 리스트의 개념

C언어에서 문자열은 문자 배열로 표현되며, 이는 고정된 크기로 정의됩니다. 문자열은 char 타입 배열에 저장되며, 문자열 끝에는 null 문자(\0)가 포함됩니다. 그러나 고정된 크기는 동적 문자열 처리에 한계를 가져옵니다.

문자열의 기본 개념

문자열은 문자(char)의 연속으로 이루어진 데이터 구조입니다. C언어에서는 문자열을 처리할 때 배열을 사용하며, 크기 변경이나 동적 할당은 개발자가 직접 관리해야 합니다.

연결 리스트의 기본 개념

연결 리스트는 동적 데이터 구조로, 각 노드가 데이터와 다음 노드에 대한 포인터를 포함합니다. 연결 리스트는 다음과 같은 특징을 가집니다.

유연성: 크기가 동적으로 변할 수 있습니다.
효율성: 노드의 삽입 및 삭제가 배열보다 효율적입니다.

문자열과 연결 리스트의 상호작용

연결 리스트를 사용하여 문자열을 저장하면 다음과 같은 방식으로 동작합니다.

각 노드가 하나의 문자를 저장하며, 다음 노드로의 포인터를 포함합니다.
동적 크기 조정이 가능하므로 메모리 사용이 효율적입니다.

이 개념을 기반으로 다음 단계에서는 연결 리스트로 문자열을 저장하는 이유와 그 장점을 자세히 살펴봅니다.

연결 리스트로 문자열을 저장하는 이유

연결 리스트를 사용하여 문자열을 저장하면, 배열 기반 접근 방식에서 발생할 수 있는 한계를 극복할 수 있습니다. 이는 특히 문자열의 크기가 가변적이거나 동적 데이터 조작이 필요한 경우에 유용합니다.

메모리 효율성

배열은 고정 크기를 사전에 정의해야 하므로, 크기를 초과하거나 부족할 경우 메모리 낭비 또는 데이터 손실이 발생할 수 있습니다.
연결 리스트는 필요한 만큼만 메모리를 할당하므로 메모리 사용이 더 효율적입니다.

동적 문자열 처리

문자열에 문자를 삽입하거나 삭제해야 하는 경우, 배열에서는 데이터 이동과 추가 메모리 할당이 필요합니다.
연결 리스트는 특정 노드의 연결만 변경하면 되므로, 삽입 및 삭제가 간단하고 효율적입니다.

가변 크기 문자열

프로그램 실행 중 문자열의 크기를 동적으로 변경할 수 있는 기능이 연결 리스트에서는 자연스럽게 구현됩니다.
이 기능은 사용자 입력, 파일 읽기 등에서 유용하게 활용됩니다.

구조적 장점

연결 리스트를 사용하면 문자열을 여러 조각으로 나눠 병렬 처리하거나, 특정 패턴의 문자열을 효율적으로 검색할 수 있습니다.
연결 리스트의 유연성은 특정 문자열 연산(예: 서브스트링 생성, 부분 문자열 제거)에 대한 효율성을 높입니다.

이러한 이유로 연결 리스트는 크기가 동적으로 변하거나 빈번한 삽입과 삭제가 필요한 문자열 처리에 적합한 선택입니다. 다음 단계에서는 단일 연결 리스트를 활용해 문자열을 구현하는 방법을 살펴보겠습니다.

단일 연결 리스트를 사용한 문자열 구현

단일 연결 리스트는 각 노드가 하나의 문자와 다음 노드에 대한 포인터를 포함하는 구조입니다. 이 방식은 간단하면서도 동적 문자열 처리를 지원하는 기본적인 방법입니다.

단일 연결 리스트의 구조

단일 연결 리스트로 문자열을 표현하기 위해 다음과 같은 구조체를 정의합니다:

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

typedef struct Node {
    char data;
    struct Node* next;
} Node;

각 노드는 문자(data)와 다음 노드의 주소(next)를 저장합니다.

단일 연결 리스트로 문자열 생성

문자열을 생성하려면 각 문자를 새로운 노드로 할당하고, 노드 간 연결을 설정합니다.
예제 코드:

Node* createNode(char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Node* createString(const char* str) {
    Node* head = NULL;
    Node* tail = NULL;

    for (int i = 0; str[i] != '\0'; i++) {
        Node* newNode = createNode(str[i]);
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    return head;
}

문자열 출력

연결 리스트로 저장된 문자열을 출력하려면, 노드를 순회하며 각 문자를 출력합니다:

void printString(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%c", current->data);
        current = current->next;
    }
    printf("\n");
}

사용 예시

int main() {
    const char* input = "Hello, Linked List!";
    Node* stringList = createString(input);

    printf("Stored string: ");
    printString(stringList);

    // 메모리 해제는 추가 구현 필요
    return 0;
}

결론

단일 연결 리스트를 사용하면 문자열의 동적 생성과 유연한 조작이 가능합니다. 이러한 구조는 삽입 및 삭제와 같은 동적 연산을 효율적으로 처리할 수 있는 기반을 제공합니다. 다음 단계에서는 이중 연결 리스트를 활용해 문자열을 구현하는 고급 방법을 살펴보겠습니다.

이중 연결 리스트로 문자열 구현

이중 연결 리스트는 각 노드가 앞의 노드와 뒤의 노드에 대한 포인터를 모두 포함하는 구조입니다. 이 방식은 단일 연결 리스트보다 효율적인 양방향 탐색과 복잡한 문자열 조작이 가능합니다.

이중 연결 리스트의 구조

이중 연결 리스트의 노드는 다음과 같은 구조체로 정의됩니다:

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

typedef struct Node {
    char data;
    struct Node* prev;
    struct Node* next;
} Node;

각 노드는 문자(data), 이전 노드에 대한 포인터(prev), 다음 노드에 대한 포인터(next)를 포함합니다.

이중 연결 리스트로 문자열 생성

문자열을 생성하려면 각 문자를 노드로 생성하고, 양방향으로 연결합니다.
예제 코드:

Node* createNode(char data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

Node* createString(const char* str) {
    Node* head = NULL;
    Node* tail = NULL;

    for (int i = 0; str[i] != '\0'; i++) {
        Node* newNode = createNode(str[i]);
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    return head;
}

문자열 출력

이중 연결 리스트를 출력하려면, 각 노드를 순회하며 데이터를 출력합니다.
예제 코드:

void printString(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%c", current->data);
        current = current->next;
    }
    printf("\n");
}

문자열 역순 출력

이중 연결 리스트의 장점은 노드의 역방향 탐색이 가능하다는 점입니다:

void printReverseString(Node* tail) {
    Node* current = tail;
    while (current != NULL) {
        printf("%c", current->data);
        current = current->prev;
    }
    printf("\n");
}

사용 예시

int main() {
    const char* input = "Bidirectional List!";
    Node* stringList = createString(input);

    printf("Stored string: ");
    printString(stringList);

    printf("Reversed string: ");
    // tail을 찾으려면 head부터 순회하거나 별도로 반환받아야 함
    Node* tail = stringList;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    printReverseString(tail);

    // 메모리 해제는 추가 구현 필요
    return 0;
}

결론

이중 연결 리스트는 양방향 탐색이 가능하므로 문자열의 역순 출력이나 복잡한 조작에 적합합니다. 특히 삽입, 삭제, 역방향 처리와 같은 고급 연산이 빈번히 필요한 경우 효과적입니다. 다음 단계에서는 연결 리스트 기반 문자열의 주요 조작 방법을 다룹니다.

연결 리스트 기반 문자열 조작

연결 리스트를 사용하여 문자열을 저장하면 삽입, 삭제, 탐색과 같은 조작이 배열보다 더 효율적으로 수행될 수 있습니다. 이 섹션에서는 연결 리스트를 기반으로 문자열을 조작하는 주요 방법을 살펴봅니다.

문자 삽입

연결 리스트에서 문자 삽입은 특정 위치에 새 노드를 추가하는 것으로 구현됩니다.

void insertChar(Node** head, Node* position, char data) {
    Node* newNode = createNode(data);

    if (position == NULL) { // 리스트가 비어 있거나 맨 앞에 삽입
        newNode->next = *head;
        if (*head != NULL) {
            (*head)->prev = newNode;
        }
        *head = newNode;
    } else { // 중간 또는 끝에 삽입
        newNode->next = position->next;
        newNode->prev = position;
        if (position->next != NULL) {
            position->next->prev = newNode;
        }
        position->next = newNode;
    }
}

문자 삭제

특정 노드를 삭제하려면 노드 간 연결을 재구성한 뒤 메모리를 해제합니다.

void deleteChar(Node** head, Node* target) {
    if (target == NULL) return;

    if (*head == target) { // 첫 번째 노드를 삭제
        *head = target->next;
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
    } else { // 중간 또는 끝 노드를 삭제
        if (target->prev != NULL) {
            target->prev->next = target->next;
        }
        if (target->next != NULL) {
            target->next->prev = target->prev;
        }
    }
    free(target);
}

문자열 탐색

특정 문자를 검색하려면 리스트를 순회하며 조건을 확인합니다.

Node* findChar(Node* head, char target) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == target) {
            return current;
        }
        current = current->next;
    }
    return NULL; // 찾지 못한 경우
}

응용: 문자열 대체

기존 문자를 새 문자로 교체하려면 탐색 후 데이터 필드를 변경합니다.

void replaceChar(Node* head, char oldChar, char newChar) {
    Node* target = findChar(head, oldChar);
    if (target != NULL) {
        target->data = newChar;
    }
}

사용 예시

int main() {
    const char* input = "Hello!";
    Node* stringList = createString(input);

    printf("Original string: ");
    printString(stringList);

    printf("Inserting 'X' after 'H':\n");
    Node* position = findChar(stringList, 'H');
    insertChar(&stringList, position, 'X');
    printString(stringList);

    printf("Deleting 'X':\n");
    Node* target = findChar(stringList, 'X');
    deleteChar(&stringList, target);
    printString(stringList);

    printf("Replacing 'o' with 'O':\n");
    replaceChar(stringList, 'o', 'O');
    printString(stringList);

    return 0;
}

결론

연결 리스트는 삽입과 삭제가 빈번히 필요한 문자열 조작에 적합합니다. 이를 활용하면 동적 데이터 처리와 유연한 메모리 사용이 가능하며, 코드 유지보수성 또한 향상됩니다. 다음 단계에서는 연결 리스트 기반 문자열의 정렬 방법을 살펴보겠습니다.

연결 리스트 기반 문자열 정렬

연결 리스트로 저장된 문자열을 정렬하려면 노드를 순회하며 데이터를 재구성하거나, 노드 자체를 재배치하는 방법을 사용합니다. 연결 리스트는 배열보다 삽입과 삭제가 효율적이기 때문에 정렬 과정에서도 메모리 이동 없이 링크만 수정하면 됩니다.

버블 정렬을 이용한 문자열 정렬

버블 정렬은 간단한 알고리즘으로, 연결 리스트에서도 구현이 비교적 쉽습니다.

void bubbleSort(Node* head) {
    int swapped;
    Node* current;
    Node* last = NULL;

    if (head == NULL) return;

    do {
        swapped = 0;
        current = head;

        while (current->next != last) {
            if (current->data > current->next->data) {
                // 데이터 교환
                char temp = current->data;
                current->data = current->next->data;
                current->next->data = temp;
                swapped = 1;
            }
            current = current->next;
        }
        last = current; // 마지막 노드는 이미 정렬됨
    } while (swapped);
}

노드 재배치를 통한 정렬

연결 리스트의 노드를 실제로 재배치하려면 노드 삽입과 삭제를 사용해 새로운 리스트를 형성합니다. 이는 추가 메모리 사용을 줄이고 더 정교한 제어를 제공합니다.

Node* sortedInsert(Node* sorted, Node* newNode) {
    if (sorted == NULL || sorted->data >= newNode->data) {
        newNode->next = sorted;
        if (sorted != NULL) {
            sorted->prev = newNode;
        }
        return newNode;
    }

    Node* current = sorted;
    while (current->next != NULL && current->next->data < newNode->data) {
        current = current->next;
    }

    newNode->next = current->next;
    if (current->next != NULL) {
        current->next->prev = newNode;
    }
    current->next = newNode;
    newNode->prev = current;

    return sorted;
}

Node* insertionSort(Node* head) {
    Node* sorted = NULL;
    Node* current = head;

    while (current != NULL) {
        Node* next = current->next;
        current->prev = current->next = NULL; // 노드를 분리
        sorted = sortedInsert(sorted, current);
        current = next;
    }

    return sorted;
}

사용 예시

int main() {
    const char* input = "linkedlist";
    Node* stringList = createString(input);

    printf("Original string: ");
    printString(stringList);

    printf("Sorting with Bubble Sort:\n");
    bubbleSort(stringList);
    printString(stringList);

    printf("Sorting with Insertion Sort:\n");
    stringList = createString(input); // 원본 복원
    stringList = insertionSort(stringList);
    printString(stringList);

    return 0;
}

정렬의 장점

버블 정렬: 구현이 간단하지만, 시간 복잡도가 O(n²)로 느리며 작은 데이터셋에 적합합니다.
삽입 정렬: 노드 이동이 적어 효율적이며, O(n²)의 시간 복잡도를 가지지만, 노드 재배치가 필요합니다.

결론

연결 리스트에서 문자열 정렬은 사용 사례와 데이터 크기에 따라 다양한 알고리즘을 선택할 수 있습니다. 적절한 정렬 방법을 선택함으로써 데이터 처리 속도와 효율성을 높일 수 있습니다. 다음 단계에서는 연결 리스트를 활용한 문자열 데이터 처리 응용 예시를 살펴보겠습니다.

응용 예시: 연결 리스트를 활용한 문자열 데이터 처리

연결 리스트를 사용하면 대량의 문자열 데이터를 효율적으로 처리할 수 있습니다. 이 섹션에서는 실제 사례를 통해 연결 리스트 기반 문자열 처리의 가능성과 장점을 살펴봅니다.

응용 1: 중복 문자 제거

입력된 문자열에서 중복 문자를 제거하고 고유한 문자만 남깁니다.

void removeDuplicates(Node* head) {
    Node* current = head;

    while (current != NULL) {
        Node* runner = current->next;
        while (runner != NULL) {
            if (runner->data == current->data) {
                Node* duplicate = runner;
                runner = runner->next;
                deleteChar(&head, duplicate);
            } else {
                runner = runner->next;
            }
        }
        current = current->next;
    }
}

사용 예시:

const char* input = "programming";
Node* stringList = createString(input);
printf("Original string: ");
printString(stringList);

printf("After removing duplicates: ");
removeDuplicates(stringList);
printString(stringList);

응용 2: 문자열 회문 확인

입력된 문자열이 회문(앞뒤가 같은 문자열)인지 확인합니다.

int isPalindrome(Node* head) {
    Node* tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }

    while (head != NULL && tail != NULL && head != tail && head->prev != tail) {
        if (head->data != tail->data) {
            return 0; // 회문이 아님
        }
        head = head->next;
        tail = tail->prev;
    }
    return 1; // 회문임
}

사용 예시:

const char* input = "radar";
Node* stringList = createString(input);
printf("Is palindrome: %s\n", isPalindrome(stringList) ? "Yes" : "No");

응용 3: 문자열 병합

두 개의 연결 리스트로 저장된 문자열을 병합하여 새로운 문자열을 생성합니다.

Node* mergeStrings(Node* str1, Node* str2) {
    if (str1 == NULL) return str2;
    if (str2 == NULL) return str1;

    Node* tail = str1;
    while (tail->next != NULL) {
        tail = tail->next;
    }

    tail->next = str2;
    str2->prev = tail;

    return str1;
}

사용 예시:

const char* str1 = "Hello, ";
const char* str2 = "World!";
Node* list1 = createString(str1);
Node* list2 = createString(str2);

Node* mergedList = mergeStrings(list1, list2);
printf("Merged string: ");
printString(mergedList);

결론

연결 리스트를 활용한 문자열 데이터 처리는 동적 메모리 관리와 효율적인 데이터 조작이 필요할 때 특히 유용합니다. 중복 제거, 회문 확인, 문자열 병합과 같은 응용은 연결 리스트의 유연성과 효율성을 잘 보여주는 사례입니다. 다음 단계에서는 연결 리스트와 배열의 성능을 비교하여 각각의 적합한 사용 사례를 논의하겠습니다.

성능 비교: 연결 리스트 vs 배열

연결 리스트와 배열은 문자열 데이터를 처리하는 데 각각 장점과 단점이 있습니다. 성능 차이를 이해하면 특정 작업에 적합한 자료 구조를 선택할 수 있습니다.

삽입 및 삭제

연결 리스트:
삽입 및 삭제는 특정 노드만 변경하면 되므로 O(1) 시간 복잡도를 가지며 매우 효율적입니다. 특히, 리스트의 중간 또는 시작 부분에 변경이 필요한 경우 유리합니다.
배열:
배열에서는 삽입 및 삭제 시 데이터 이동이 필요하므로 최악의 경우 O(n)의 시간 복잡도가 발생합니다. 배열 끝에 삽입하는 경우에는 O(1)로 수행됩니다.

랜덤 접근

연결 리스트:
랜덤 접근이 불가능하며 특정 인덱스에 도달하려면 순차 탐색이 필요하므로 O(n) 시간이 소요됩니다.
배열:
배열은 인덱스를 사용해 O(1) 시간에 랜덤 접근이 가능합니다.

메모리 사용

연결 리스트:
각 노드가 추가적인 포인터를 저장해야 하므로 메모리 오버헤드가 발생합니다. 데이터 크기에 비해 메모리 효율성이 떨어질 수 있습니다.
배열:
배열은 데이터만 저장하므로 메모리 사용이 더 효율적입니다. 하지만 크기를 미리 정의해야 하며, 빈 공간이 낭비될 가능성이 있습니다.

정렬 및 검색

연결 리스트:
노드의 연결을 재구성해야 하므로 정렬이 O(n²) 시간 복잡도를 가지며 배열보다 느립니다. 검색 역시 O(n) 시간이 소요됩니다.
배열:
배열은 정렬 알고리즘을 쉽게 적용할 수 있으며, 이진 검색 같은 고급 검색 기법을 활용하면 O(log n) 시간 복잡도를 달성할 수 있습니다.

사용 사례 비교

작업 유형	연결 리스트	배열
빈번한 삽입/삭제	적합	부적합
랜덤 접근	부적합	적합
데이터 크기 동적 변경	적합	부적합
메모리 효율	부적합	적합
대규모 정렬/검색	부적합	적합

결론

연결 리스트와 배열은 각각의 장단점이 뚜렷하며, 작업의 특성과 요구 사항에 따라 선택해야 합니다. 연결 리스트는 삽입과 삭제가 빈번한 동적 데이터 처리에 적합하며, 배열은 랜덤 접근이 필요한 고정 크기 데이터 처리에 적합합니다. 다음 단계에서는 이 기사의 내용을 요약하며 마무리하겠습니다.

요약

본 기사에서는 C언어에서 연결 리스트를 사용하여 문자열을 효율적으로 처리하는 방법을 소개했습니다. 연결 리스트의 구조와 구현 방식을 이해하면 문자열 삽입, 삭제, 탐색, 정렬 등 다양한 연산을 유연하게 수행할 수 있습니다. 또한 배열과의 성능 비교를 통해 연결 리스트가 특히 동적 데이터 처리에 적합하다는 점을 확인했습니다. 이러한 지식을 바탕으로 메모리 효율성과 코드 유지 보수성을 개선할 수 있는 C언어 프로그래밍을 실현할 수 있습니다.