Реализация двусвязного списка на C

Введение

В этом проекте вы научитесь реализовывать структуру данных двусвязный список на C. Двусвязный список - это тип связного списка, где каждый узел содержит указатели как на предшествующий, так и на следующий узел, что позволяет эффективно перемещаться в обоих направлениях - вперед и назад.

👀 Предварительный просмотр

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

🎯 Задачи

В этом проекте вы научитесь:

• инициализировать двусвязный список;
• обходить двусвязный список и выполнять для каждого узла функцию обратного вызова;
• вставлять новый узел после заданного узла в двусвязном списке;
• вставлять новый узел перед заданным узлом в двусвязном списке;
• удалять узел из двусвязного списка.

🏆 Достижения

После завершения этого проекта вы сможете:

• понять основную структуру и операции с двусвязным списком;
• реализовать ядровые функции для управления двусвязным списком;
• продемонстрировать способность работать с указателями и динамическим выделением памяти в C;
• применить свои знания для исправления и улучшения предоставленной реализации двусвязного списка.

Skills Graph

Исправление сегментации

В этом шаге функция free_list не обновляет указатель current после освобождения узла, что приведет к сегментации. Эта ошибка должна быть исправлена сейчас.

1. Найдите функцию free_list() в файле list.c.
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; // Обновлено
    }
    free(list);
}

Вставить узел после заданного узла

В этом шаге вы научитесь вставлять новый узел после заданного узла в двусвязном списке.

1. Найдите функцию insert_after() в файле list.c.
2. Эта функция принимает struct List*, struct Node* (узел, после которого нужно вставить новый узел) и data для нового узла.
3. Функция должна создать новый struct Node и инициализировать его поле data с помощью предоставленного data.
4. Затем функция должна обновить указатели 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) { // Обновлено
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // Обновлено
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // Обновлено
        list->head = newnode;
    }
}

6. Найдите insert_after (list, NULL, data); и замените на следующий код:

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

Вставить узел перед заданным узлом

В этом шаге вы научитесь вставлять новый узел перед заданным узлом в двусвязном списке.

1. Найдите функцию insert_before() в файле list.c.
2. Эта функция принимает struct List*, struct Node* (узел, перед которым нужно вставить новый узел) и data для нового узла.
3. Функция должна создать новый struct Node и инициализировать его поле data с помощью предоставленного data.
4. Затем функция должна обновить указатели 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) { // Обновлено
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // Обновлено
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // Обновлено
        list->tail = newnode;
    }
}

6. Найдите insert_before (list, NULL, data); и замените на следующий код:

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

Удалить узел из двусвязного списка

В этом шаге вы научитесь удалять узел из двусвязного списка.

1. Найдите функцию delete_from() в файле list.c.
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; // Обновлено

    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev; // Обновлено

    free(node);
}

Теперь реализация двусвязного списка в файле list.c должна работать правильно. Вы можете использовать предоставленный файл test_list.c для проверки функциональности двусвязного списка. Результаты теста следующие:

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

Резюме

Поздравляем! Вы завершили этот проект. Вы можете практиковаться в более многих лабораторных работах в LabEx, чтобы улучшить свои навыки.