Linked List

Linked List를 C로 직접 구현할 수 있다.
코드는 다음과 같다.

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

typedef int item;
typedef struct __Node {
    item element;
    struct __Node *next_link;
} Node;

Node *create_node(item data, Node *next_link);
void insert_Node(Node **head, Node *p, Node *new_node);
void delete_Node(Node **head, Node *p, Node *remove_node);
void display_Node(Node *head);
Node *search_Node(Node *head, int key);

int main() {
    Node *list = NULL;
    Node *p;

    insert_Node(&list, NULL, create_node(1, NULL));
    insert_Node(&list, NULL, create_node(2, NULL));
    insert_Node(&list, NULL, create_node(3, NULL));
    display_Node(list);

    delete_Node(&list, NULL, list);
    display_Node(list);

    insert_Node(&list, list, create_node(5, NULL));
    insert_Node(&list, list, create_node(6, NULL));
    insert_Node(&list, list, create_node(7, NULL));
    display_Node(list);

    p = search_Node(list, 2);
    if (p != NULL) {
        printf("search completed: %d\n", p->element);
    } else {
        printf("search failed\n");
    }

    p = search_Node(list, 4);
    if (p != NULL) {
        printf("search completed: %d\n", p->element);
    } else {
        printf("search failed\n");
    }

    return 0;
}

Node *create_node(item data, Node *next_link) {
    Node *new_node;

    new_node = (Node *) malloc(sizeof(Node));
    if (new_node == NULL) {
        fprintf(stderr, "memory allocation error.\n");
        return NULL;
    }

    new_node->element = data;
    new_node->next_link = next_link;

    return new_node;
}

void insert_Node(Node **head, Node *p, Node *new_node) {
    if (*head == NULL) {
        new_node->next_link = NULL;
        *head = new_node;
    } else if (p == NULL) {
        /* insert head of list
        new_node->next_link = *head;
        *head = new_node;
        */
        /* insert tail of list */
        Node *temp = *head;

        while (1) {
            if ((*head)->next_link == NULL) {
                break;
            }

            *head = (*head)->next_link;
        }

        new_node->next_link = NULL;
        (*head)->next_link = new_node;

        *head = temp;
    } else {
        new_node->next_link = p->next_link;
        p->next_link = new_node;
    }
}

void delete_Node(Node **head, Node *p, Node *remove_node) {
    if (p == NULL) {
        *head = (*head)->next_link;
    } else {
        p->next_link = remove_node->next_link;
    }

    free(remove_node);
}

void display_Node(Node *head) {
    Node *p = head;

    while (p != NULL) {
        printf("%d -> ", p->element);
        p = p->next_link;
    }

    printf("\n");
}

Node *search_Node(Node *head, int key) {
    Node *p = head;

    while (p != NULL) {
        if (p->element == key) {
            return p;
        } else {
            p = p->next_link;
        }
    }

    return p;
}

코드의 선언부를 보면 typedef 를 이용하여 재정의된 item 형식이 있다.
예제에서는 int 형으로 선언되어 있어서 특별하게 재정의를 할 필요성은 없지만, 추후에 리스트 속에 들어갈 자료형이 어떤 것이 될 지 모르기에 재정의해서 사용하도록 했다.
구조체 Node 를 보게 되면 가장 단순한 선형 linked list를 표현하였다.
저장할 자료 하나와 다음 리스트에 해당하는 포인터를 선언해 준다.

– Main 함수

메인함수에서는 리스트를 구현하기 위해 사용된 생성, 삽입, 삭제, 탐색, 출력 함수를 하나씩 이용해본 것이다.

– crate_node 함수

Node *create_node(item data, Node *next_link) {
    Node *new_node;

    new_node = (Node *) malloc(sizeof(Node));
    if (new_node == NULL) {
        fprintf(stderr, "memory allocation error.\n");
        return NULL;
    }

    new_node->element = data;
    new_node->next_link = next_link;

    return new_node;
}

create_node 함수에서는 노드를 생성한다.

– insert_node 함수

void insert_Node(Node **head, Node *p, Node *new_node) {
    if (*head == NULL) {
        new_node->next_link = NULL;
        *head = new_node;
    } else if (p == NULL) {
        /* insert head of list
        new_node->next_link = *head;
        *head = new_node;
        */
        /* insert tail of list */
        Node *temp = *head;

        while (1) {
            if ((*head)->next_link == NULL) {
                break;
            }

            *head = (*head)->next_link;
        }

        new_node->next_link = NULL;
        (*head)->next_link = new_node;

        *head = temp;
    } else {
        new_node->next_link = p->next_link;
        p->next_link = new_node;
    }
}

insert_node 함수에서는 총 3가지 경우로 나누어서 새로운 노드를 삽입하게 된다.
1. 새로운 노드를 리스트의 맨 앞에 추가하는 경우
head가 null인 경우는 비어있는 공백 리스트란 뜻이다.
리스트의 처음에 새로운 노드를 삽입하고 헤드 포인터를 새로운 노드로 지정하여 준다.
이러면 main함수에서 설정했던 Node 포인터인 list가 선두 노드를 가르키게 된다.

2. 새로운 노드를 리스트의 맨 뒤에 추가하는 경우
코드내에 주석에서도 처리하였듯이, 지금 구현되어 있는 코드는 동적 배열처럼 리스트의 뒷부분에 계속해서 새로운 노드를 추가하는 코드이다.
이렇게 구현하기 위해서 임시로 선두 노드의 주소를 저장하고 있을 temp 포인터를 설정한다.
그리고, 리스트의 끝부분으로 이동한다.
완벽하게 끝까지 가버릴 경우 포인터가 null 값을 가지게 되므로, 끝 바로 앞 노드까지, 즉 next_node 가 NULL을 가르키고 있는 바로 앞부분까지 이동한다.
새로 추가될 노드를 직전 노드의 next_node 포인터로 연결시켜 주고, 다시 헤드 포인터를 리스트의 선두 노드로 복귀시켜 주면 된다.
코드내에 주석으로 처리된 부분은 뒤로 추가하지 않고, 리스트의 선두 부분으로 추가할 때 사용되는 코드이다.
이렇게 구현을 하면, stack 처럼 새롭게 추가되는 노드가 계속 리스트의 선두 노드를 형성하게 된다.

3. 새로운 노드를 리스트의 중간에 추가하는 경우
이렇게 코드를 작성할 때는 순서에 매우 유의하여야 한다.
먼저 삽입되기 직전의 next_node 포인터가 가르키는 노드를 새로 추가될 노드에 포인터에 대응시켜 준다.
그리고 삽입되기 직전의 next_node 포인터를 새로운 노드를 가르키도록 한다.
로직 순서가 바뀌게 되면 원하는 결과값이 나오지 않으니, 꼭 순서에 유의하여야 한다.

– delete_node 함수

void delete_Node(Node **head, Node *p, Node *remove_node) {
    if (p == NULL) {
        *head = (*head)->next_link;
    } else {
        p->next_link = remove_node->next_link;
    }

    free(remove_node);
}

삭제 함수에서는 2가지 경우로 나누어서 삭제를 진행한다.
1. 리스트의 선두 노드를 삭제하는 경우
이 경우에는 헤드 포인터를 리스트의 두번째 노드로 지정하여 주고 선두노드를 제거한다.
포인터의 재설정이 없으면, 리스트의 주소값을 잃어버릴 수 있으니 유의하여야 한다.

2. 리스트 중간의 노드를 삭제하는 경우
이 경우에는 삭제할 노드를 가르키는 포인터, 즉 직전 노드의 next_node 포인터를 삭제할 노드가 가지고 있던 next_node 포인터로 대응시켜 주고 삭제를 진행해야 한다.
이 과정이 없을 경우에는 삭제할 노드 이후의 노드들에 대해서 주소값을 잃어버리게 된다.

– display_node 함수

void display_Node(Node *head) {
    Node *p = head;

    while (p != NULL) {
        printf("%d -> ", p->element);
        p = p->next_link;
    }

    printf("\n");
}

리스트의 선두 노드에서부터 끝 노드까지 순차적으로 탐색하며 해당 item 값을 출력해주는 함수이다.
이 경우에 유의할 점으로는, 탐색을 하기 위한 별도의 포인터를 지역변수로 선언을 하고, 그 포인터로 리스트를 탐색해야 한다.
만약, head 포인터로 탐색을 진행하게 될 경우에, 한 번의 탐색은 가능하나 리스트의 선두 노드의 주소를 잃어버리게 되므로, 복구가 불가능해지게 된다.

– search_node 함수

Node *search_Node(Node *head, int key) {
    Node *p = head;

    while (p != NULL) {
        if (p->element == key) {
            return p;
        } else {
            p = p->next_link;
        }
    }

    return p;
}

리스트 내에서 원하는 키 값을 찾고자 할 때 사용할 수 있는 방법이다.
참고로 위 구현에서는 선형 탐색을 하게 되므로, 최악의 경우에는 display_node함수와 완벽하게 같아지게 된다.
display_node 함수에서처럼 리스트를 순회할 때에는 반드시 별도의 포인터를 지역변수로 선언해서 사용해야 한다.
예시 코드에서는 리턴 타입을 Node* 형으로 지정하였기 때문에, key값을 찾을 경우 그냥 그 노드 자체를 리턴해버리도록 하였다.

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있다.

댓글 남기기