Aula 18 - Estruturas de Dados Dinâmicas em C 🧱

📑 1. Fundamentos Teóricos & Análise Técnica

Diferente de linguagens de alto nível com coleções nativas redimensionáveis (como ArrayList em Java ou listas em Python), em linguagem C a construção de estruturas com dimensionamento dinâmico exige a criação manual de nós alocados na Heap interconectados através de ponteiros.

1. Lista Duplamente Encadeada (Doubly Linked List): Cada nó armazena seu dado e dois ponteiros: next (para o próximo elemento) e prev (para o elemento anterior). Permite travessia bidirecional e inserção/remoção em tempo constante \(O(1)\) quando o ponteiro para o nó já é conhecido.
2. Pilhas (LIFO - Last-In, First-Out): Operações estritas de push (empilhar) e pop (desempilhar) realizadas exclusivamente no topo.
3. Filas (FIFO - First-In, First-Out): Operações de enqueue (enfileirar no fim) e dequeue (desenfileirar no início).

A disciplina de memória é crítica: a destruição de uma lista exige percorrer nó por nó, preservando o ponteiro para o próximo elemento antes de liberar o nó atual com free().

📐 Arquitetura Conceitual & Diagrama de Fluxo

graph LR
    Head["Head (Início)"] --> N1["Nó 1 [prev: NULL | data: 10 | next]"]
    N1 <--> N2["Nó 2 [prev | data: 20 | next]"]
    N2 <--> N3["Nó 3 [prev | data: 30 | next: NULL]"]
    Tail["Tail (Fim)"] --> N3
    style Head fill:#e1f5fe,stroke:#01579b
    style N1 fill:#fff3e0,stroke:#e65100
    style N2 fill:#fff3e0,stroke:#e65100
    style N3 fill:#fff3e0,stroke:#e65100
    style Tail fill:#e8f5e9,stroke:#2e7d32

🔍 Pilares e Diretrizes Técnicas

Nesta unidade, aprofundamos os seguintes conceitos fundamentais: - Nós com Alocação Dinâmica: Uso de malloc(sizeof(Node)) para cada elemento inserido na coleção. - Manutenção de Invariantes de Ponteiros: Atualização atômica de next e prev para evitar nós órfãos. - Prevenção de Falhas de Segmentação (Segmentation Fault): Checagem mandatória de if (ptr == NULL) antes de desreferenciar ponteiros. - Varredura de Liberação Segura: Armazenamento temporário de temp = current->next antes de executar free(current).

🛠️ 2. Implementação Prática em C ANSI e Algoritmos de Estruturas de Dados

Abaixo está a implementação técnica de referência, estruturada com padrões de engenharia de software e foco em robustez:

// doubly_linked_list.c (Lista Duplamente Encadeada em C)
#include <stdio.h>
#include <stdlib.h>

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

typedef struct {
    DNode* head;
    DNode* tail;
} DList;

void dlist_push_back(DList* list, int val) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = val;
    newNode->next = NULL;
    newNode->prev = list->tail;

    if (list->tail) {
        list->tail->next = newNode;
    } else {
        list->head = newNode;
    }
    list->tail = newNode;
}

void dlist_free(DList* list) {
    DNode* curr = list->head;
    while (curr) {
        DNode* next = curr->next;
        free(curr);
        curr = next;
    }
    list->head = NULL;
    list->tail = NULL;
}

💡 Análise Passo a Passo do Código

1. Inserção em O(1): O ponteiro tail permite anexar elementos no fim da lista instantaneamente sem percorrer todos os nós.
2. Encadeamento Duplo: O nó anterior e o próximo conhecem-se mutuamente através de prev e next.
3. Liberação Completa: dlist_free evita vazamento de memória percorrendo e destruindo cada nó sequencialmente.

🎯 3. Próximos Passos & Sequência Didática