C 언어 - linked list를 노드로 구현해 봤다.

자료구조 중에서 가장 기초가 되는 형태가 Linked List이다. List들이 서로 이어져 있는 모양인데, 이를 노드라는 기본형들의 연결로 만들어 본다. 노드란 놈은 이렇게 생겼다.

원하는 데이터를 담고 있는 부분과, 다음 연결된 노드를 가리키는 포인터로 구성이 되어 있다. c코드로 나타내 보자면 아래와 같이 생겼다. 

struct Node {
    int data;              /* 데이터 */
    struct Node* nextNode; /* 다음 노드를 가리키는 부분 */
};

 우리가 실행시켜 볼 main문은 다음과 같이 생겼다.

int main() {
    struct Node* Node1 = CreateNode(100);
    struct Node* Node2 = InsertNode(Node1, 200);
    struct Node* Node3 = InsertNode(Node2, 300);
    /* Node 2 뒤에 Node4 넣기 */
    struct Node* Node4 = InsertNode(Node2, 400);
 
    PrintNodeFrom(Node1);
    return 0;
}

 CreateNode라는 함수는 초기에 노드를 생성하는 함수이다. 이 함수에서 만들어 진 노드를 시작으로 리스트가 시작된다.  InsertNode는 이미 만들어진 리스트가 있을 때, 특정한 위치에 노드를 삽입하고 싶을 경우 사용하는 함수이다. 그래서 입력값으로 사용할 데이터와 노드를 삽입시킬 기준이 되는 노드가 필요하다. PrintNodeFrom은 입력 노드로 부터 줄줄이 이러진 노드들의 데이터 값을 보여주는 함수이고, DestroyNode는 필요가 없어진 노드를 제거하는 함수이다. 

struct Node* CreateNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 
    newNode->data = data;
    newNode->nextNode = NULL;
 
    return newNode;
}

먼저 CreateNode부터 보자. 이 함수는 malloc을 사용해서 새로운 노드를 정의하고, 이 노드 자체를 반환하는 함수이다. 처음 생긴 노드는 다음 노드를 가리키는 포인터에 아무 값도 가지지 않게 된다. 

이번에는 InsertNode이다. 이는 설명이 조금 필요한 부분이 있다. 

Current 노드 바로뒤에 새롭게 삽입을 하고 싶은데, Current는 이미 다른 노드와 연결이 되어 있다. 그리고 새롭게 삽입하는 노드도 기존 노드와 연결을 시켜주어야 한다.

 

기존 Current 노드가 가리키던 연결을 끊고 새롭게 만들어진 노드를 가리키도록 한다. 그리고 새로운 노드가 원래 Current가 가리키던 노드를 가리키게 된다!! 코드는 아래와 같다.

struct Node* InsertNode(struct Node* current, int data) {
    /* current 노드가 가리키고 있던 다음 노드가 after 이다 */
    struct Node* after = current->nextNode;
 
    /* 새로운 노드를 생성한다 */
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 
    /* 새 노드에 값을 넣어준다. */
    newNode->data = data;
    newNode->nextNode = after;
 
    /* current 는 이제 newNode 를 가리키게 된다 */
    current->nextNode = newNode;
 
    return newNode;
}

 이번에는 DestroyNode~

  우선 삭제하고자 하는 노드를 찾고, 삽입과 마찬가지로 노드들의 연결을 다시 정리해주어야 한다. 위 사진과 같이 삭제될 노드가 가리키고 있던 노드를 그 이전 노드가 가리키기만 하면 된다. 그리고 삭제될 노드는 할당된 메모리를 해제해 주어야 한다.(free)

void DestroyNode(struct Node* destroy,    struct Node* head) { /* 다음 노드를 가리킬 포인터*/
    struct Node* next = head;           /* head 를 파괴하려 한다면 */
    if (destroy == head) {
        free(destroy);
        return;
    }              /* 만일 next 가 NULL 이면 종료 */
    while (next) { /* 만일 next 다음 노드가 destroy 라면 next 가 destory 앞 노드*/
        if (next->nextNode == destroy) { /* 따라서 next 의 다음 노드는 destory 가
                                            아니라 destroy 의 다음 노드가 된다. */
            next->nextNode = destroy->nextNode;
        } /* next 는 다음 노드를 가리킨다. */
        next = next->nextNode;
    }
    free(destroy);
}

 마지막으로 입력 노드로부터의 줄줄이 연결된 노드들의 데이터를 보여주는 PrintNodeFrom이다.

void PrintNodeFrom(struct Node* from) {
    /* from 이 NULL 일 때 까지,
       즉 끝 부분에 도달할 때 까지 출력 */
    while (from) {
        printf("노드의 데이터 : %d \n", from->data);
        from = from->nextNode;
    }
}

 아주 간단한 경우였다. 그런데 이 구조에서는 특정한 위치를 찾기 위해서 처음부터 살펴봐야 하는 불편함이 있다. 앞으로 밖에 가리키고 있지 않기 때문이다. 그러면 뒤로도 가리키게 하면 어떨까???

 이런 식으로 말이다. 노드의 구조 자체를 바꿔야 할 것이다.

struct Node {
    int data; /* 데이터 */
    struct Node* nextNode;
    struct Node* prevNode;
};

 이전 노드를 가리키는 포인터를 하나 추가하기만 하면 된다. 

struct Node* CreateNode(int data){
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->nextNode = NULL;
    newNode->prevNode = NULL;
    newNode->data = data;
    return newNode;
}

 CreatNode도 prevNode 포인터가 아무 값도 가지지 않게 만들어 주기만 하면 된다. 

InsertNode

DestroyNode

 InsertNode랑 DestroyNode가 조금 복잡하다. 위 그림과 같은 과정으로 코드를 작성했다. 화살표의 개수가 곧 설정해 주어야 하는 값들의 개수이므로 이에 유의하면서 작성해야 한다.

struct Node* InsertNode(struct Node *current, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* after = current->nextNode;
    newNode->data = data;
    newNode->nextNode = after;
    newNode->prevNode = current;
    /* current 는 이제 newNode 를 가리키게 된다 */  
    current->nextNode = newNode;
    if(after) after->prevNode = newNode;
 
    return newNode;
}
void DestroyNode(struct Node *destroy, struct Node* head) {
    if (destroy == head) {
        (head->nextNode)->prevNode = NULL;
        free(head);
        return;
    }
    while (head) {
        if (head->nextNode == destroy) {
            head->nextNode = destroy->nextNode;
            (destroy->nextNode)->prevNode = head;
            free(destroy);
        }
        head = head->nextNode;
    }
    printf("destination not found\n");
    return;
}

 이와 더불어서 총 노드의 개수를 알아야 하는 일이 발생할 수 있으므로 이에 대한 함수도 작성하였다.

int CountNode(struct Node* head) {
    int count = 0;
    while (head) {
        count++;
        head = head->nextNode;
    }
    return count;
}

 사실 이는 다음 과정을 위해서 미리 작성한 것인데, 다음에 할 과정이 무엇인가 하면~

 이렇게 꼬리를 무는 Cyclic Node들을 만드는 것이다!!! prevNode와 nextNode는 절대 NULL일 리가 없다! 그리고, 이전처럼 검색이나 Print를 한다면 끝이 없이 이어질 것이므로 총 노드의 개수를 알고, 이를 이용해 한 Cycle동안만 시행하도록 만들어 주어야 한다. 

struct Node* CreateNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->nextNode = newNode;
    newNode->prevNode = newNode;
    newNode->data = data;
    return newNode;
}

 일단 Create를 하는 과정은 다음과 같이 하고, 

int CountNode(struct Node* head) {
    struct Node* after = head->nextNode;
    int count = 1;
    while (after) {
        if (after == head) break;
        count++;
        after = after->nextNode;
    }
    return count;
}

 

  앞서 만들었던 위 CountNode 함수를 적극 활용해야 할 것이다. 

void PrintNodeFrom(struct Node *from, int total_node) {
    while (from) {
        printf("노드의 데이터 : %d \n", from->data);
        from = from->nextNode;
        total_node--;
        if (total_node <= 0) break;
    }
    printf("모든 노드가 끝남 \n");
}

 

  이런 식으로 말이다. total_node가 0이 되면 한 사이클을 돌았다는 뜻이므로 break를 걸어 주었다.

struct Node* InsertNode(struct Node *current, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    struct Node* after = current->nextNode;
    newNode->data = data;
    newNode->nextNode = after;
    newNode->prevNode = current;
    /* current 는 이제 newNode 를 가리키게 된다 */
    current->nextNode = newNode;
    if (after) after->prevNode = newNode;
 
    return newNode;
}
void DestroyNode(struct Node *destroy, struct Node* head) {
    struct Node* after = head;
    if (destroy == head) {
        (head->nextNode)->prevNode = head->prevNode;
        (head->prevNode)->nextNode = head->nextNode;
        free(head);
        return;
    }
    while (after) {
        if (after->nextNode == destroy) {
            after->nextNode = destroy->nextNode;
            (destroy->nextNode)->prevNode = after;
            free(destroy);
            return;
        }
        after = after->nextNode;
    }
    printf("destination not found\n");
    return;
}
int SearchNode(struct Node* head, struct Node *search) {
    struct Node* after = head;
    while (after) {
        if (after->nextNode == search) {
            return (after->nextNode)->data;
        }
        after = after->nextNode;
    }
    return -1;
}

 나머지 과정들은 사실 크게 다르지 않다.