Учебная версия на русском. Код и его вывод сохранены в исходном виде.

Двусвязный список на C

Поддерживайте прямые и обратные ссылки при вставке и удалении узлов.

Узел содержит next и prev. Это позволяет обходить список в обе стороны, но требует дополнительного указателя и согласованного обновления связей при каждой операции.

При вставке между соседями соедините обе стороны и исправьте обратные ссылки. При удалении сначала соедините соседей, затем освободите узел. У первого узла нет предыдущего, у последнего — следующего.

Проверяйте согласованность обходом вперёд и назад. Испытайте удаление головы, хвоста и единственного узла. В конце освободите все выделенные объекты.

Код C

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

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

DNode* insertHead(DNode *head, int val) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = val;
    newNode->prev = NULL;
    newNode->next = head;
    if (head != NULL) head->prev = newNode;
    return newNode;
}

void printForward(DNode *head) {
    DNode *curr = head;
    while (curr != NULL) {
        printf("%d <-> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

void freeDList(DNode *head) {
    DNode *curr = head;
    while (curr != NULL) {
        DNode *temp = curr;
        curr = curr->next;
        free(temp);
    }
}

int main() {
    DNode *head = NULL;
    head = insertHead(head, 300);
    head = insertHead(head, 200);
    head = insertHead(head, 100);

    printf("Doubly Linked List: ");
    printForward(head);

    freeDList(head);
    return 0;
}

Открыть в компиляторе

Ожидаемый вывод

Doubly Linked List: 100 <-> 200 <-> 300 <-> NULL

Частые вопросы

Почему код и вывод остаются на английском?

Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.