[C] 자료구조(Data Structure) 이중 연결 리스트(Double Linked List)

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

이중 연결 리스트(Double Linked List)를 구현하기 위한 전처리 구문이다. <stdlib.h>는 동적 할당을 위해 포함하였다.

 

typedef int element;

typedef struct ListNode {
    element data;
    struct ListNode* front_link;
    struct ListNode* back_link;
} ListNode;

이중 연결 리스트는 헤드(head)라는 가장 앞선 노드를 기준으로 각 노드에는 해당 노드의 요소와 이전 그리고 다음 노드의 주소가 포함되어 있다.

 

`ListNode* make_node(element value) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = value;
    node->front_link = NULL;
    node->back_link = NULL;
    return node;
}

이중 연결 리스트에 사용할 새로운 노드를 만드는 사용자 정의 함수이다.

 

ListNode* insert_first(ListNode* head, element value) {
    ListNode* new_node = make_node(value);

    if (head != NULL) {
        new_node->back_link = head;
        head->front_link = new_node;
    }
    
    head = new_node;
    return head;
}

이중 연결 리스트의 헤드에 새로운 노드를 삽입하는 사용자 정의 함수이다. 헤드 노드에 새로운 노드(new_node)가 삽입된다.

 

ListNode* insert(ListNode* head, ListNode* pre_node, element value) {
    ListNode* new_node = make_node(value);
    new_node->back_link = pre_node;
    new_node->front_link = pre_node->front_link;
    (pre_node->front_link)->back_link = new_node;
    pre_node->front_link = new_node;
    return head;
}

이중 연결 리스트의 특정 부분에 새로운 노드를 삽입하는 사용자 정의 함수이다. 이전 노드(pre_node)의 다음 위치에 새로운 노드(new_node)가 삽입된다.

 

ListNode* delete_first(ListNode* head) {
    if (head == NULL) return NULL;

    ListNode* del_node;
    del_node = head;
    head = del_node->back_link;
    free(del_node);
    return head;
}

이중 연결 리스트의 헤드 노드를 제거하는 사용자 정의 함수이다. 헤드 노드를 제거한다.

 

ListNode* delete(ListNode* head, ListNode* del_node) {
    if (head == NULL) return NULL;

    (del_node->back_link)->front_link = del_node->front_link;
    (del_node->front_link)->back_link = del_node->back_link;
    free(del_node);
    return head;
}

이중 연결 리스트의 특정 부분에 있는 노드를 제거하는 사용자 정의 함수이다. 제거 노드(del_node)를 제거한다.

 

void print(ListNode* head) {
    for (ListNode* node = head; node != NULL; node = node->back_link)
        printf("%d->", node->data);
    printf("NULL\n");
}

이중 연결 리스트의 모든 요소를 출력하는 사용자 정의 함수이다.

---

// example
int main() {
    ListNode* head = NULL;

    for (int i = 0; i < 3; i++) {
        head = insert_first(head, i);
        print(head);
    }
    printf("\n");

    head = insert(head, head->back_link, 7);
    print(head);
    printf("\n");

    head = delete(head, head->back_link);
    print(head);
    printf("\n");

    for (int i = 0; i < 3; i++) {
        head = delete_first(head);
        print(head);
    }

    return 0;
}

// terminal
0->NULL
1->0->NULL
2->1->0->NULL

2->1->7->0->NULL

2->1->0->NULL

1->0->NULL
0->NULL
NULL

이중 연결 리스트를 이용한 예제 main문이다. 이중 연결 리스트 관련 함수는 모두 head의 주소를 반환하기 때문에 관련 함수를 사용할 때 ListNode* 자료형의 head 변수에 그 반환값을 넣어준다.

---

전체 코드

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

typedef int element;

typedef struct ListNode {
    element data;
    struct ListNode* front_link;
    struct ListNode* back_link;
} ListNode;

ListNode* make_node(element value) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = value;
    node->front_link = NULL;
    node->back_link = NULL;
    return node;
}

ListNode* insert_first(ListNode* head, element value) {
    ListNode* new_node = make_node(value);

    if (head != NULL) {
        new_node->back_link = head;
        head->front_link = new_node;
    }
    
    head = new_node;
    return head;
}

ListNode* insert(ListNode* head, ListNode* pre_node, element value) {
    ListNode* new_node = make_node(value);
    new_node->back_link = pre_node;
    new_node->front_link = pre_node->front_link;
    (pre_node->front_link)->back_link = new_node;
    pre_node->front_link = new_node;
    return head;
}

ListNode* delete_first(ListNode* head) {
    if (head == NULL) return NULL;

    ListNode* del_node;
    del_node = head;
    head = del_node->back_link;
    free(del_node);
    return head;
}

ListNode* delete(ListNode* head, ListNode* del_node) {
    if (head == NULL) return NULL;

    (del_node->back_link)->front_link = del_node->front_link;
    (del_node->front_link)->back_link = del_node->back_link;
    free(del_node);
    return head;
}

void print(ListNode* head) {
    for (ListNode* node = head; node != NULL; node = node->back_link)
        printf("%d->", node->data);
    printf("NULL\n");
}

int main() {
    ListNode* head = NULL;

    for (int i = 0; i < 3; i++) {
        head = insert_first(head, i);
        print(head);
    }
    printf("\n");

    head = insert(head, head->back_link, 7);
    print(head);
    printf("\n");

    head = delete(head, head->back_link);
    print(head);
    printf("\n");

    for (int i = 0; i < 3; i++) {
        head = delete_first(head);
        print(head);
    }

    return 0;
}