[C/정렬] 양방향(이중) 연결리스트(Double Linked List)

//doubleLinkedList.c
// 참고 유튜브 영상: "Gunny's Algorithm Together"의 "더블 링크드 리스트 다함께 C언어로 코딩 해봐요 - by Gunny (Korean Ver.)"

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

typedef struct _Node{
    int data;
    struct _Node *next;
    struct _Node *prev;
} Node;

// 노드 만들기, 값은 초기화
Node *createNode(int data) {
    Node *newNode = (Node *) malloc(sizeof(Node));

    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    
    return newNode;
}

//노드의 메모리를 해제함.
void deleteNode(Node *node) {
    free(node);
}

//head부터 시작해서 index번째의 Node의 주소를 반환함
Node *getNodeAt(Node *head, int index) {
    Node *curr = head;
    int count = 0;

    while(curr != NULL) {
        if(count == index) {
        return curr;
        }
        count++;
        curr = curr->next;
    }
    return NULL;
}

//Node의 갯수를 알려주는 함수.
int countNode(Node *head) {
    Node *curr = head;
    int count = 0;

    while (curr != NULL) {
        count++;
        curr = curr->next;
    }
    return count;
}

void appendNode(Node **head, Node *newNode) {
    // 노드가 하나도 없는 경우
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *curr = *head;
        while(curr->next != NULL) {
            curr = curr->next;
        }
        //curr 이 마지막 노드임, 그 뒤에 노드를 추가
        curr->next = newNode;
        newNode->prev = curr;
        //newNode->next = NULL;
    }
}

void insertAfter(Node *curr, Node *newNode) {
    //createNode 함수로 만든 노드를 curr 뒤에 끼워넣음.
    //curr 이 head일 경우
    if (curr->prev == NULL && curr->next == NULL) {
        curr->next = newNode;
        newNode->prev = curr;
    } else if (curr->next == NULL) {  //tail 일 경우
        curr->next = newNode;
        newNode->prev = curr;
    } else {  //body 일 경우, 사이에 끼워넣는다.
        newNode->next = curr->next;
        newNode->prev = curr;
        curr->next->prev = newNode;
        curr->next = newNode;
    }
}

void removeNode(Node **head, Node* remove) {
    //헤드를 제거하라고 한다면
    if (*head == remove) {
        *head = remove->next;
    }
    remove->next->prev = NULL;

    // remove 할 것 뒤에 노드가 있을 때...

    if (remove->next != NULL) {
        remove->next->prev = remove->prev;
    }
    //remove 앞에 노드가 있을 때...
    if (remove->prev != NULL) {
        remove->prev->next = remove->next;
    }
    deleteNode(remove);
}

void printNode(Node *head, int count) {
    Node *curr = head;
    
    for (int i = 0; curr != NULL && i < count; i++) { // 0 < 5
        curr = getNodeAt(head, i);
        printf("list[%d] = %d\n", i, curr->data);
    }
}

int main () {
    int i = 0;
    int count = 0;

    // 트리의 첫번째 노드를 가리키는 포인터 변수. head는 변경될 수 있으므로 그 head를 가리킨다.
    // head와 동일한 메모리 값이지만 함수 내에서 list 메모리값을 바꾸어 head 위치를 변경하기도 한다.
    Node *list = NULL;
    //임시 노드
    Node *newNode = NULL;
    // 현재 노드
    Node *curr = NULL;
    //i를 데이터값으로, 양방향 주소를 NULL로 하는 Node 형 포인터 5개 만들어 list 주소에 하나씩 추가한다.
    for(i=1; i<6; i++) {
        newNode = createNode(i);
        printf("%d번째 노드:0x%x, data:%d, prev:0x%x, next:0x%x\n", \
                            i-1, newNode, newNode->data, newNode->prev, newNode->next);
        printf("list:0x%x\n", list);
        appendNode(&list, newNode);
        printf("newNode->prev:0x%x\n", newNode->prev);
        printf("newNode->next:0x%x\n", newNode->next);
    }

    count = countNode(list);  // 노드의 전체 갯수 구하기 = 5
    printf("node의 개수: %d\n", count);
    for (i = 0; i<count; i++) {  //5회 반복
        curr = getNodeAt(list, i); // 0, 1, 2, 3, 4번째 있는 노드 주소를 얻기
        printf("list[%d] = %d\n", i, curr->data); // 그 노드의 데이터 출력
    }
    printf("--------------5 Nodes Created------------\n");

    newNode = createNode(99);
    curr = getNodeAt(list, 0); // 첫번째 노드의 포인터
    insertAfter(curr, newNode); // 그 노드 뒤에 새 노드를 삽입하기

    newNode = createNode(1033);
    curr = getNodeAt(list, 4);
    insertAfter(curr, newNode);

    count = countNode(list);
    printNode(list, count);
    // for (i = 0; i< count; i++) {
    //     curr = getNodeAt(list, i);
    //     printf("list[%d] = %d\n", i, curr->data);
    // }
    
    printf("----------- After 2 nodes inserted-----------\n");

    newNode = getNodeAt(list, 1);
    removeNode(&list, newNode);

    count = countNode(list);
    printNode(list, count);
    printf("---After Nodes with index 1 removed-----\n");


    newNode = getNodeAt(list, 0);
    removeNode(&list, newNode);
   
    count = countNode(list);
    printNode(list, count);
    printf("---After Nodes with index 0 removed-----\n");

    return 0;
}

------------실행 결과-----------
0번째 노드:0x4052a0, data:1, prev:0x0, next:0x0
list:0x0
newNode->prev:0x0
newNode->next:0x0
1번째 노드:0x4056d0, data:2, prev:0x0, next:0x0
list:0x4052a0
newNode->prev:0x4052a0
newNode->next:0x0
2번째 노드:0x4056f0, data:3, prev:0x0, next:0x0
list:0x4052a0
newNode->prev:0x4056d0
newNode->next:0x0
3번째 노드:0x405710, data:4, prev:0x0, next:0x0
list:0x4052a0
newNode->prev:0x4056f0
newNode->next:0x0
4번째 노드:0x405730, data:5, prev:0x0, next:0x0
list:0x4052a0
newNode->prev:0x405710
newNode->next:0x0
node의 개수: 5
list[0] = 1
list[1] = 2
list[2] = 3
list[3] = 4
list[4] = 5
--------------5 Nodes Created------------
list[0] = 1
list[1] = 99
list[2] = 2
list[3] = 3
list[4] = 4
list[5] = 1033
list[6] = 5
----------- After 2 nodes inserted-----------
list[0] = 1
list[1] = 2
list[2] = 3
list[3] = 4
list[4] = 1033
list[5] = 5
---After Nodes with index 1 removed-----
list[0] = 2
list[1] = 3
list[2] = 4
list[3] = 1033
list[4] = 5
---After Nodes with index 0 removed-----