C언어로 다중 레벨 연결 리스트 구현하기

다중 레벨 연결 리스트는 계층적인 데이터를 표현하는 데 적합한 데이터 구조입니다. 예를 들어, 디렉토리 구조나 다단계의 중첩된 데이터에서 효과적으로 사용됩니다. 본 기사에서는 C언어를 사용하여 다중 레벨 연결 리스트를 설계, 구현, 그리고 응용하는 방법을 자세히 설명합니다. 이를 통해 메모리 관리와 알고리즘 설계에 대한 이해를 심화할 수 있습니다.

다중 레벨 연결 리스트란?

다중 레벨 연결 리스트는 기본 연결 리스트의 확장된 형태로, 각 노드가 하나 이상의 레벨로 연결될 수 있는 구조를 가집니다. 일반적인 단일 연결 리스트에서는 노드가 다음 노드로만 연결되지만, 다중 레벨 연결 리스트에서는 추가적으로 하위 레벨의 노드를 가리키는 링크가 포함됩니다.

특징

계층적 데이터 표현: 트리와 유사하게 상위-하위 관계를 자연스럽게 표현합니다.
복잡한 데이터 구조: 단일 리스트로 표현하기 어려운 다차원 데이터를 처리할 수 있습니다.
유연성: 동적으로 노드를 추가하거나 삭제할 수 있으며, 탐색 방식도 유연합니다.

사용 예시

파일 디렉토리 시스템: 폴더 안에 또 다른 폴더와 파일이 중첩되어 있는 구조 표현.
조직도: 상위 관리자와 하위 직원의 계층적 관계 표현.
멀티레벨 캐싱: 캐시 데이터에서 여러 우선순위를 다루는 구조.

이러한 특성 덕분에 다중 레벨 연결 리스트는 효율적으로 계층 데이터를 처리할 수 있는 강력한 도구로 활용됩니다.

다중 레벨 연결 리스트의 구조 설계

다중 레벨 연결 리스트를 구현하려면 노드 구조를 설계하고, 각 노드가 상위와 하위 데이터를 연결할 수 있도록 링크를 포함해야 합니다.

노드 구조

노드는 기본적으로 데이터 필드와 함께 두 개 이상의 포인터를 포함합니다.

데이터 필드: 노드가 저장하는 데이터(예: 정수, 문자열 등).
다음 포인터: 동일한 레벨의 다음 노드를 가리킵니다.
하위 레벨 포인터: 하위 레벨의 첫 번째 노드를 가리킵니다.

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

// 노드 구조체 정의
typedef struct Node {
    int data;                // 데이터 필드
    struct Node* next;       // 다음 노드 포인터
    struct Node* child;      // 하위 레벨 포인터
} Node;

구조 설계의 핵심

동적 메모리 할당: 노드는 동적으로 생성되며, 필요에 따라 메모리를 할당받아 관리됩니다.
계층적 관계 표현: child 포인터를 통해 하위 레벨 노드에 접근할 수 있어 계층적 데이터 구조를 표현합니다.

다중 레벨 연결 리스트의 설계 예시

예를 들어, 다음과 같은 리스트 구조를 구현할 수 있습니다.

Level 1: 1 → 2 → 3  
                 ↓  
Level 2:      4 → 5

위 구조는 3번 노드가 하위 레벨로 연결되어 있고, 하위 레벨에 4번과 5번 노드가 존재합니다.

확장 가능성

설계된 구조는 다음과 같은 확장이 가능합니다.

더 깊은 하위 레벨 추가.
각 레벨에서의 순서 보장.
추가적인 링크를 포함하여 양방향 연결 리스트로 확장.

이 구조를 통해 다중 레벨 연결 리스트의 기본적인 틀을 완성하고, 이후 구현 단계를 진행할 수 있습니다.

다중 레벨 연결 리스트 생성하기

다중 레벨 연결 리스트를 생성하려면 새 노드를 동적으로 할당하고 데이터를 초기화한 후, 필요한 위치에 노드를 연결해야 합니다. 아래는 주요 과정입니다.

노드 생성 함수

새로운 노드를 생성하고 초기화하는 함수를 작성합니다.

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 동적 메모리 할당
    if (newNode == NULL) {
        printf("메모리 할당 실패\n");
        return NULL;
    }
    newNode->data = data;    // 데이터 초기화
    newNode->next = NULL;    // 다음 포인터 초기화
    newNode->child = NULL;   // 하위 레벨 포인터 초기화
    return newNode;
}

노드 연결 함수

노드를 수평 및 하위 레벨로 연결합니다.

void addNext(Node* parent, Node* child) {
    if (parent != NULL) {
        parent->next = child;
    }
}

void addChild(Node* parent, Node* child) {
    if (parent != NULL) {
        parent->child = child;
    }
}

다중 레벨 리스트 생성 과정

다음은 다중 레벨 연결 리스트를 생성하는 예제 코드입니다.

int main() {
    // Level 1 노드 생성
    Node* node1 = createNode(1);
    Node* node2 = createNode(2);
    Node* node3 = createNode(3);

    // Level 2 노드 생성
    Node* node4 = createNode(4);
    Node* node5 = createNode(5);

    // 노드 연결
    addNext(node1, node2);
    addNext(node2, node3);

    // Level 1과 Level 2 연결
    addChild(node3, node4);
    addNext(node4, node5);

    // 결과 확인
    printf("Level 1: %d → %d → %d\n", node1->data, node2->data, node3->data);
    printf("Level 2: %d → %d\n", node4->data, node5->data);

    return 0;
}

출력 예시

위 코드를 실행하면 다음과 같은 출력이 나타납니다.

Level 1: 1 → 2 → 3  
Level 2: 4 → 5

핵심 포인트

노드를 생성하고 적절히 초기화해야 합니다.
next와 child 포인터를 통해 계층적인 관계를 정확히 설정합니다.
동적 메모리 할당을 통해 메모리 관리의 유연성을 확보합니다.

이 과정을 통해 다중 레벨 연결 리스트의 기본 구조를 생성할 수 있습니다.

다중 레벨 연결 리스트 탐색 방법

다중 레벨 연결 리스트에서 데이터를 탐색하는 것은 계층 구조를 고려해야 하므로 단순 연결 리스트보다 조금 더 복잡합니다. 각 노드의 next와 child 포인터를 활용하여 모든 노드를 순회합니다.

탐색 알고리즘

다중 레벨 연결 리스트를 탐색하는 기본 알고리즘은 다음과 같습니다:

현재 노드에서 데이터를 출력.
하위 레벨(child)로 내려가서 재귀적으로 탐색.
상위 레벨로 돌아와 다음 노드(next)를 탐색.

탐색 함수 구현

재귀적으로 리스트를 탐색하는 함수는 다음과 같습니다.

void traverseList(Node* head) {
    if (head == NULL) {
        return; // 노드가 없으면 종료
    }

    // 현재 노드 데이터 출력
    printf("%d ", head->data);

    // 하위 레벨 탐색
    if (head->child != NULL) {
        printf("(child -> ");
        traverseList(head->child);
        printf(")");
    }

    // 다음 노드 탐색
    traverseList(head->next);
}

탐색 예제

이전에 생성한 리스트에서 탐색을 수행해 봅니다.

int main() {
    // 다중 레벨 연결 리스트 생성 (앞서 생성한 코드 사용)
    Node* node1 = createNode(1);
    Node* node2 = createNode(2);
    Node* node3 = createNode(3);
    Node* node4 = createNode(4);
    Node* node5 = createNode(5);

    addNext(node1, node2);
    addNext(node2, node3);
    addChild(node3, node4);
    addNext(node4, node5);

    // 리스트 탐색
    printf("다중 레벨 연결 리스트 탐색 결과:\n");
    traverseList(node1);
    printf("\n");

    return 0;
}

출력 예시

코드를 실행하면 다음과 같은 결과를 얻습니다.

다중 레벨 연결 리스트 탐색 결과:  
1 2 3 (child -> 4 5 )

탐색 방법의 주요 고려 사항

재귀 사용: 하위 레벨을 탐색할 때 재귀를 사용하여 계층 구조를 처리합니다.
순서 보장: next와 child 포인터를 순서대로 탐색하여 데이터의 계층적 순서를 보장합니다.
출력 포맷: 계층 구조를 시각적으로 표현할 수 있도록 출력 형식을 조정합니다.

확장 가능성

깊이 우선 탐색(DFS): 현재 구현은 깊이 우선 탐색 방식입니다.
너비 우선 탐색(BFS): 큐를 활용하여 너비 우선 방식으로도 탐색할 수 있습니다.
조건부 탐색: 특정 조건에 따라 탐색을 중단하거나 특정 데이터만 탐색하도록 수정할 수 있습니다.

이 탐색 방식을 통해 다중 레벨 연결 리스트의 모든 데이터를 효과적으로 탐색할 수 있습니다.

다중 레벨 연결 리스트 삭제

다중 레벨 연결 리스트에서 삭제 작업은 동적 메모리를 안전하게 해제하고 계층 구조를 고려해야 하는 과정입니다. 각 노드를 방문하며, 하위 레벨 노드를 재귀적으로 삭제한 뒤 현재 노드를 삭제해야 합니다.

삭제 알고리즘

현재 노드의 하위 레벨(child)로 재귀적으로 이동하여 모든 하위 노드 삭제.
현재 노드의 다음 노드(next)로 이동하여 삭제.
현재 노드 메모리 해제.

삭제 함수 구현

다음은 재귀적으로 리스트를 삭제하는 함수입니다.

void deleteList(Node* head) {
    if (head == NULL) {
        return; // 노드가 없으면 종료
    }

    // 하위 레벨 노드 삭제
    if (head->child != NULL) {
        deleteList(head->child);
    }

    // 다음 노드 삭제
    if (head->next != NULL) {
        deleteList(head->next);
    }

    // 현재 노드 메모리 해제
    printf("Deleting node with data: %d\n", head->data);
    free(head);
}

삭제 예제

이전에 생성한 다중 레벨 연결 리스트를 삭제합니다.

int main() {
    // 다중 레벨 연결 리스트 생성 (앞서 생성한 코드 사용)
    Node* node1 = createNode(1);
    Node* node2 = createNode(2);
    Node* node3 = createNode(3);
    Node* node4 = createNode(4);
    Node* node5 = createNode(5);

    addNext(node1, node2);
    addNext(node2, node3);
    addChild(node3, node4);
    addNext(node4, node5);

    // 리스트 삭제
    printf("다중 레벨 연결 리스트 삭제 작업 시작:\n");
    deleteList(node1);

    return 0;
}

출력 예시

코드를 실행하면 각 노드가 삭제되는 과정이 출력됩니다.

다중 레벨 연결 리스트 삭제 작업 시작:  
Deleting node with data: 4  
Deleting node with data: 5  
Deleting node with data: 3  
Deleting node with data: 2  
Deleting node with data: 1

삭제 작업에서의 고려 사항

재귀 사용: 하위 레벨 삭제를 위해 재귀 호출이 필요합니다.
메모리 누수 방지: free()를 호출하여 모든 동적 메모리를 안전하게 해제합니다.
순서 중요성: 하위 레벨부터 상위 레벨로 삭제하여 연결이 끊어지지 않도록 합니다.

확장 가능성

부분 삭제: 특정 레벨 또는 특정 노드만 삭제하도록 함수를 수정할 수 있습니다.
비재귀적 삭제: 재귀 호출 대신 스택을 사용하여 삭제 과정을 구현할 수 있습니다.
디버깅 지원: 삭제 과정에서 디버깅 정보를 출력하여 문제를 진단할 수 있습니다.

이 과정을 통해 다중 레벨 연결 리스트를 안전하게 삭제하고 메모리를 효율적으로 관리할 수 있습니다.

다중 레벨 연결 리스트 활용 예시

다중 레벨 연결 리스트는 계층적 데이터 관리가 필요한 다양한 실제 사례에 유용하게 적용됩니다. 여기에서는 파일 디렉토리 구조 구현과 멀티레벨 메뉴 시스템 두 가지를 중심으로 다룹니다.

예시 1: 파일 디렉토리 구조

파일 디렉토리 시스템은 계층적 데이터 구조를 가장 잘 보여주는 사례입니다. 각 디렉토리를 노드로 간주하고, 하위 폴더와 파일은 child 포인터로 연결됩니다.

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

// 파일 또는 폴더 노드 구조체
typedef struct Node {
    char name[50];           // 파일/폴더 이름
    struct Node* next;       // 같은 레벨의 다음 노드
    struct Node* child;      // 하위 레벨 첫 노드
} Node;

// 노드 생성 함수
Node* createNode(char* name) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("메모리 할당 실패\n");
        return NULL;
    }
    strcpy(newNode->name, name);
    newNode->next = NULL;
    newNode->child = NULL;
    return newNode;
}

// 디렉토리 탐색 함수
void traverseDirectory(Node* head, int depth) {
    if (head == NULL) {
        return;
    }

    // 깊이에 따른 들여쓰기
    for (int i = 0; i < depth; i++) {
        printf("  ");
    }

    printf("%s\n", head->name);

    // 하위 레벨 탐색
    if (head->child != NULL) {
        traverseDirectory(head->child, depth + 1);
    }

    // 다음 노드 탐색
    traverseDirectory(head->next, depth);
}

int main() {
    // 디렉토리 구조 생성
    Node* root = createNode("root");
    Node* folder1 = createNode("folder1");
    Node* folder2 = createNode("folder2");
    Node* file1 = createNode("file1.txt");
    Node* file2 = createNode("file2.txt");

    root->child = folder1;
    folder1->next = folder2;
    folder1->child = file1;
    file1->next = file2;

    printf("디렉토리 구조:\n");
    traverseDirectory(root, 0);

    return 0;
}

출력 예시

디렉토리 구조:
root
  folder1
    file1.txt
    file2.txt
  folder2

예시 2: 멀티레벨 메뉴 시스템

다중 레벨 연결 리스트는 웹 애플리케이션이나 소프트웨어에서 메뉴 시스템 구현에 활용될 수 있습니다. 각 메뉴 항목은 노드로 간주되며, 하위 메뉴는 child 포인터를 통해 연결됩니다.

Node* createMenu(char* name) {
    return createNode(name); // 위의 파일 디렉토리 구조의 노드 생성 재사용
}

void displayMenu(Node* menu, int level) {
    traverseDirectory(menu, level); // 동일한 디렉토리 탐색 함수 사용
}

int main() {
    // 멀티레벨 메뉴 생성
    Node* mainMenu = createMenu("Main Menu");
    Node* submenu1 = createMenu("Submenu 1");
    Node* submenu2 = createMenu("Submenu 2");
    Node* option1 = createMenu("Option 1");
    Node* option2 = createMenu("Option 2");

    mainMenu->child = submenu1;
    submenu1->next = submenu2;
    submenu1->child = option1;
    option1->next = option2;

    printf("멀티레벨 메뉴:\n");
    displayMenu(mainMenu, 0);

    return 0;
}

출력 예시

멀티레벨 메뉴:
Main Menu
  Submenu 1
    Option 1
    Option 2
  Submenu 2

활용 포인트

유연한 계층 관리: 다중 레벨 연결 리스트는 데이터를 계층적으로 저장하고 탐색하기에 적합합니다.
확장 가능성: 새로운 디렉토리나 메뉴 항목을 동적으로 추가할 수 있습니다.
시각적 구조 표현: 들여쓰기와 탐색 알고리즘을 활용하여 계층 구조를 직관적으로 출력합니다.

응용 가능성

데이터베이스 내 트리 구조 관리
그래픽 인터페이스에서 동적 메뉴 구성
계층적 접근 권한 관리 시스템

이와 같은 활용 사례를 통해 다중 레벨 연결 리스트의 실용성을 경험할 수 있습니다.

요약

다중 레벨 연결 리스트는 계층적 데이터 표현과 관리를 가능하게 하는 강력한 데이터 구조입니다. 본 기사에서는 C언어로 다중 레벨 연결 리스트를 설계하고 구현하는 방법을 다루었습니다. 구조 설계, 노드 생성, 탐색 및 삭제 방법을 비롯해 파일 디렉토리 구조와 멀티레벨 메뉴 시스템과 같은 실제 응용 예시를 제시했습니다.

다중 레벨 연결 리스트는 계층 데이터 처리가 필요한 다양한 응용 분야에서 유용하며, 이를 통해 메모리 관리와 알고리즘 설계에 대한 깊은 이해를 얻을 수 있습니다. 학습을 심화하려면 다중 레벨 리스트의 변형 및 다양한 탐색 방식에 대한 실습을 추천합니다.