A lista encadeada simples é uma estrutura de dados fundamental que permite o armazenamento dinâmico de informações. Diferente dos arrays, os elementos não precisam estar em posições contíguas na memória. Abaixo, exploramos a implementação técnica de operações essenciais, desde a manipulação básica até a inserção e remoção em posições arbitrárias.

Estrutura Básica e Exibição

Primeiramente, definimos a estrutura do nó e uma função para percorrer e imprimir os dados contidos na lista.

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

typedef int DataType;

typedef struct Node {
    DataType data;
    struct Node* next;
} Node;

void printLinkedList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

Inserção e Remoção nas Extremidades

Para modificar a cabeça da lista dentro de uma função, passamos o endereço do ponteiro (ponteiro duplo). Isso permite que a alteração persista fora do escopo da função.

// Inserção no final (Tail)
void pushBack(Node** headRef, DataType val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = NULL;

    if (*headRef == NULL) {
        *headRef = newNode;
    } else {
        Node* temp = *headRef;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// Inserção no início (Head)
void pushFront(Node** headRef, DataType val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = *headRef;
    *headRef = newNode;
}

// Remoção no início
void popFront(Node** headRef) {
    assert(*headRef);
    Node* oldHead = *headRef;
    *headRef = (*headRef)->next;
    free(oldHead);
}

// Remoção no final
void popBack(Node** headRef) {
    assert(*headRef);
    if ((*headRef)->next == NULL) {
        free(*headRef);
        *headRef = NULL;
    } else {
        Node* prev = NULL;
        Node* tail = *headRef;
        while (tail->next != NULL) {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

Busca e Manipulação por Posição

Operações em locais específicos exigem a localização prévia de um nó ou o gerenciamento de ponteiros adjacentes.

// Localizar um nó pelo valor
Node* findNode(Node* head, DataType target) {
    Node* curr = head;
    while (curr) {
        if (curr->data == target) return curr;
        curr = curr->next;
    }
    return NULL;
}

// Criar um novo nó isolado
Node* createNewNode(DataType val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) return NULL;
    newNode->data = val;
    newNode->next = NULL;
    return newNode;
}

// Inserir ANTES de um nó específico
void insertBefore(Node** headRef, Node* pos, DataType val) {
    assert(pos);
    if (pos == *headRef) {
        pushFront(headRef, val);
    } else {
        Node* prev = *headRef;
        while (prev->next != pos) {
            prev = prev->next;
        }
        Node* newNode = createNewNode(val);
        newNode->next = pos;
        prev->next = newNode;
    }
}

// Inserir DEPOIS de um nó específico
void insertAfter(Node* pos, DataType val) {
    assert(pos);
    Node* newNode = createNewNode(val);
    newNode->next = pos->next;
    pos->next = newNode;
}

// Remover um nó específico
void eraseNode(Node** headRef, Node* pos) {
    assert(pos && *headRef);
    if (pos == *headRef) {
        popFront(headRef);
    } else {
        Node* prev = *headRef;
        while (prev->next != pos) {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
    }
}

// Remover o nó subsequente
void eraseNextNode(Node* pos) {
    assert(pos && pos->next);
    Node* target = pos->next;
    pos->next = target->next;
    free(target);
}

Exemplo de Execução Completa

Abaixo, um fluxo de teste demonstrando a integração de todas as funções implementadas.

int main() {
    Node* myList = NULL;

    // Construindo a lista: 10, 20, 30
    pushBack(&myList, 10);
    pushBack(&myList, 20);
    pushBack(&myList, 30);
    
    // Adicionando 5 na frente: 5, 10, 20, 30
    pushFront(&myList, 5);
    
    // Buscando o nó com valor 20 e inserindo 25 após ele
    Node* node20 = findNode(myList, 20);
    if (node20) {
        insertAfter(node20, 25);
    }
    
    // Lista resultante: 5 -> 10 -> 20 -> 25 -> 30
    printLinkedList(myList);
    
    // Removendo o primeiro e o último
    popFront(&myList);
    popBack(&myList);
    
    // Lista final: 10 -> 20 -> 25
    printLinkedList(myList);

    // Limpeza de memória (opcional para este exemplo simples)
    while (myList) {
        popFront(&myList);
    }

    return 0;
}

O gerenciamento manual de memória via malloc e free é crucial. Ao manipular listas ligadas, o cuidado com ponteiros nulos e a ordem das atribuições evita vazamentos de memória e erros de segmentação.