C 언어로 이중 연결 리스트 구현하기

소개

이 프로젝트에서는 C 언어로 이중 연결 리스트 자료 구조를 구현하는 방법을 배우게 됩니다. 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드 모두에 대한 포인터를 포함하는 연결 리스트의 한 유형으로, 정방향 및 역방향 모두에서 효율적인 탐색을 가능하게 합니다.

👀 미리보기

$ gcc test_list.c list.c -o test
$ ./test
welcome
to
labex
online

🎯 과제

이 프로젝트에서 다음을 배우게 됩니다:

• 이중 연결 리스트를 초기화하는 방법
• 이중 연결 리스트를 탐색하고 각 노드에 대해 콜백 함수를 실행하는 방법
• 이중 연결 리스트에서 주어진 노드 뒤에 새 노드를 삽입하는 방법
• 이중 연결 리스트에서 주어진 노드 앞에 새 노드를 삽입하는 방법
• 이중 연결 리스트에서 노드를 삭제하는 방법

🏆 성과

이 프로젝트를 완료하면 다음을 수행할 수 있습니다:

• 이중 연결 리스트의 기본 구조와 연산을 이해합니다.
• 이중 연결 리스트 관리에 필요한 핵심 함수를 구현합니다.
• C 언어에서 포인터와 동적 메모리 할당을 사용하는 능력을 보여줍니다.
• 제공된 이중 연결 리스트 구현을 수정하고 개선하기 위해 지식을 적용합니다.

세그멘테이션 오류 수정

이 단계에서는 free_list 함수가 노드를 해제한 후 current 포인터를 업데이트하지 않아 세그멘테이션 오류가 발생합니다. 이 문제를 지금 수정해야 합니다.

1. list.c 파일에서 free_list() 함수를 찾습니다.
2. 업데이트된 free_list() 함수는 다음과 같습니다:

void free_list(struct List* list) {
    struct Node* current = list->head;
    struct Node* next = NULL;

    while (current) {
        next = current->next;
        free(current);
        current = next; // Updated
    }
    free(list);
}

주어진 노드 뒤에 노드 삽입

이 단계에서는 이중 연결 리스트에서 주어진 노드 뒤에 새 노드를 삽입하는 방법을 배우게 됩니다.

1. list.c 파일에서 insert_after() 함수를 찾습니다.
2. 이 함수는 struct List*, struct Node* (새 노드를 삽입할 노드), 그리고 새 노드의 data를 인수로 받습니다.
3. 이 함수는 새로운 struct Node를 생성하고 제공된 data로 해당 data 필드를 초기화해야 합니다.
4. 그런 다음 함수는 새 노드와 prev 노드의 next 및 prev 포인터를 업데이트하여 새 노드를 올바르게 삽입해야 합니다.
5. 마지막으로, 새 노드가 리스트의 끝에 삽입되는 경우 함수는 tail 포인터를 업데이트해야 합니다.

업데이트된 insert_after() 함수는 다음과 같습니다:

void insert_after(struct List* list, struct Node* prev, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (prev) { // Updated
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // Updated
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // Updated
        list->head = newnode;
    }
}

6. insert_after (list, NULL, data);를 찾아 다음 코드로 변경합니다:

insert_after (list, list->tail, data);

주어진 노드 앞에 노드 삽입

이 단계에서는 이중 연결 리스트에서 주어진 노드 앞에 새 노드를 삽입하는 방법을 배우게 됩니다.

1. list.c 파일에서 insert_before() 함수를 찾습니다.
2. 이 함수는 struct List*, struct Node* (새 노드를 삽입할 노드), 그리고 새 노드의 data를 인수로 받습니다.
3. 이 함수는 새로운 struct Node를 생성하고 제공된 data로 해당 data 필드를 초기화해야 합니다.
4. 그런 다음 함수는 새 노드와 next 노드의 next 및 prev 포인터를 업데이트하여 새 노드를 올바르게 삽입해야 합니다.
5. 마지막으로, 새 노드가 리스트의 시작 부분에 삽입되는 경우 함수는 head 포인터를 업데이트해야 합니다.

업데이트된 insert_before() 함수는 다음과 같습니다:

void insert_before(struct List* list, struct Node* next, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (next) { // Updated
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // Updated
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // Updated
        list->tail = newnode;
    }
}

6. insert_before (list, NULL, data);를 찾아 다음 코드로 변경합니다:

insert_before (list, list->head, data);

이중 연결 리스트에서 노드 삭제

이 단계에서는 이중 연결 리스트에서 노드를 삭제하는 방법을 배우게 됩니다.

1. list.c 파일에서 delete_from() 함수를 찾습니다.
2. 이 함수는 struct List*와 struct Node* (삭제할 노드) 를 인수로 받습니다.
3. 이 함수는 주어진 노드를 리스트에서 제거하기 위해 인접 노드의 next 및 prev 포인터를 업데이트해야 합니다.
4. 또한, 삭제된 노드가 리스트의 head 또는 tail인 경우 함수는 head 및 tail 포인터도 업데이트해야 합니다.
5. 마지막으로, 함수는 삭제된 노드가 차지하는 메모리를 해제해야 합니다.

업데이트된 delete_from() 함수는 다음과 같습니다:

void delete_from(struct List* list, struct Node* node) {
    if (node->prev) node->prev->next = node->next;
    else list->head = node->next; // Updated

    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev; // Updated

    free(node);
}

이제 list.c 파일의 이중 연결 리스트 구현이 올바르게 작동해야 합니다. 제공된 test_list.c 파일을 사용하여 이중 연결 리스트의 기능을 테스트할 수 있습니다. 테스트 결과는 다음과 같습니다:

$ gcc test_list.c list.c -o test
$ ./test
welcome
to
labex
online

요약

축하합니다! 이 프로젝트를 완료했습니다. LabEx 에서 더 많은 랩을 연습하여 기술을 향상시킬 수 있습니다.