Edição didática em português. O código e suas saídas preservam o original.

Lista duplamente encadeada em C

Mantenha ligações para frente e para trás ao inserir e remover nós.

Um nó duplamente encadeado contém next e prev. Essas duas ligações permitem percorrer a lista nos dois sentidos, ao custo de um ponteiro adicional por nó e mais atualizações em cada alteração.

Ao inserir um nó entre dois vizinhos, conecte os dois lados e corrija as ligações inversas. Ao remover, conecte os vizinhos antes de liberar o nó. As extremidades exigem cuidado: o primeiro não tem anterior e o último não tem próximo.

Confira a consistência percorrendo para frente e para trás. Teste remover o único nó, a cabeça e a cauda; libere todas as alocações ao terminar.

Código 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;
}

Abrir no compilador

Saída esperada

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

Perguntas frequentes

Por que o código e a saída continuam em inglês?

Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.