Estruturas de Dados Dinâmicas¶

Geral¶

struct.c
typedef struct Node{
    int n;
    struct Node *prox;
    // struct Node *ant;
} Node;

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

int main(){
    // iniciar estrutura
    Node *head = NULL;
    // Node *tail = NULL;

    // operações
    return 0;
}

Operações¶

Inserir¶

Passos Gerais¶

Passagem por referência - deve modificar valores
Criar novo nó - Node *new = (Node *)malloc(sizeof(Node))
Verificar alocação de memória - if (new != NULL)
Preencher nó
Achar ponto de inserção
Se for o caso, ver se a estrutura está vazia
Inserir o nó
Atualizar ponteiros vizinhos

Variações¶

Pilha¶

inserir_pilha.c
void push(Node **head, int n){
    // 1 - criar novo nó
    Node *new = (Node *) malloc(sizeof(Node));
    // 2 - verificar alocação de memória
    if (new != NULL){
        // 3 - preencher nó
        new->data = n;
        new->next = *head; // pilha só insere no topo
        *head = new; // atualizar ponteiro do topo da pilha
    }
}

Fila¶

inserir_fila.c
void enqueue(Node **head, Node **tail, int n) {
    Node *novo = (Node *)malloc(sizeof(Node));

    if (novo != NULL) {
        novo->data = n;
        novo->next = NULL;
        // se a fila estiver vazia
        if (*head == NULL) {
            *head = novo;
            *tail = novo;
        } else {
            (*tail)->next = novo;
            *tail = novo;
        }
    } 
}

Lista encadeada¶

inserir_lista_inicio.c
void inserir_inicio(Node **head, int n){
    Node *new = (Node *)malloc(sizeof(Node));
    if (new != NULL) {
        new->data = n;
        new->next = *head;
        *head = new;
    }
}

inserir_lista_apos_valor.c
// inserir um nó após um nó de valor específico
void inserir_meio_apos_valor(Node **head, int valor_ref, int novo_valor){
    Node *temp = head;
    while (temp != NULL && temp->n != valor_ref){
        // percorrer a lista até achar o valor
        temp = temp->next;
    }
    // se o valor for encontrado, inserir após ele
    if (temp != NULL) {
        Node *new = (Node *)malloc(sizeof(Node));
        if (new != NULL){
            new->n = novo_valor;
            new->next = temp->next;
            temp->next = new;
        }
    } else {
        printf("Valor %d não encontrado\n", valor_ref);
    }
}

inserir_lista_posicao.c
// inserir um nó em índice específico
void inserir_na_posicao(Node **head, int pos, int novo_valor){
    Node *new = (Node *)malloc(sizeof(Node));
    if (new == NULL) {
        printf("Erro na alocação de memória\n");
        return;
    }
    new->n = novo_valor;

    if (indice == 0){
        new->next = *head;
        *head = new;
        return;
    }
    Node *temp = *head;
    for (int i = 0; i < indice-1 && temp != NULL; i++){
        temp = temp->next;
    }
    if (temp == NULL){
        printf("Índice fora do alcance da lista\n");
        free(new);
    } else {
        new->next = temp->next;
        temp->next = new;
    }
}

inserir_lista_antes_valor.c
// inserir um nó antes de um nó de valor específico
void inserir_meio_antes_valor(Node **head, int valor_ref, int novo_valor) {
    Node *new = (Node *)malloc(sizeof(Node));
    if (new == NULL) {
        printf("Erro na alocação de memória\n");
        return;
    }
    new->n = novo_valor;

    if (*head == NULL) {
        printf("A lista está vazia\n");
        free(new);
        return;
    }

    // Verificar se o nó a ser inserido é a nova head
    if ((*head)->n == valor_ref) {
        new->next = *head;
        *head = new;
        return;
    }

    Node *temp = *head; // sempre para percorrer
    while (temp->next != NULL && temp->next->n != valor_ref) {
        temp = temp->next; // Percorrer até o nó anterior ao valor_ref
    }

    if (temp->next == NULL) {
        printf("Valor %d não encontrado\n", valor_ref);
        free(new);
    } else {
        new->next = temp->next; // Inserir
        temp->next = new;
    }
}

inserir_lista_fim.c
void inserir_fim(Node **head, int n){
    Node *new = (Node *)malloc(sizeof(Node));
    if (new != NULL){
        new->n = n;
        new->next = NULL;
    }
    // para ajustar o ponteiro prev, verificar se lista está vazia
    if (*head == NULL){
        *head = new;
    } else {
        // Percorrer lista
        Node *temp = *head;
        while (temp->next != NULL){
            temp = temp->next;
        }
        // último nó aponta para o novo
        temp->next = new;
    }
}

inserir_lista_ordenado.c
// inserir nó de forma ordenada
void inserir_ordenado(Node **head, int novo_valor) {
    Node *new = (Node *)malloc(sizeof(Node));
    if (new == NULL) {
        printf("Erro na alocação de memória\n");
        return;
    }
    new->n = novo_valor;

    if (*head == NULL || (*head)->n >= novo_valor) {
        // Inserir no início se a lista estiver vazia ou o novo valor for menor
        new->next = *head;
        *head = new;
        return;
    }

    Node *temp = *head;
    while (temp->next != NULL && temp->next->n < novo_valor) {
        temp = temp->next; // Percorrer até o nó apropriado
    }

    // Inserir o novo nó
    new->next = temp->next;
    temp->next = new; 
}

L2E¶

Lista circular¶

L2C¶

Remover¶

Passos Gerais¶

Passagem por referência - deve modificar valores
Ponteiro auxiliar - referência para o lugar de remoção
Verificar se a estrutura está vazia
Salvar referência - aux = *head
Atualizar os ponteiros vizinhos
Liberar memória do nó removido

Variações¶

Pilha¶

remover_pilha_void.c
void pop_void(Node **head){
    // 1 - ponteiro aux para o topo (liberar memória)
    Node *aux;
    // 2 - verificar se a pilha está vazia
    if((*head) != NULL){
        // 3 - salvar referência para o topo
        aux = *head;
        // 4 - atualizar ponteiro do topo
        *head = (*head)->next;
        // 5 - liberar memória do nó
        free(aux);
    }
}

remover_pilha_int.c
int pop_int(Node **head){
    // 1 - ponteiro aux para o topo (liberar memória)
    Node *aux;
    int n;
    // 2 - verificar se a pilha está vazia
    if((*head) != NULL){
        n = (*head)->data;
        // 3 - salvar referência para o topo
        aux = *head;
        // 4 - atualizar ponteiro do topo
        *head = (*head)->next;
        // 5 - liberar memória do nó
        free(aux);
    }
    return n;
}

Fila¶

remover_fila_void.c
int dequeue_void(Node **head, Node **tail) {
    Node *aux;
    if ((*head) != NULL) {
        aux = *head;
        *head = (*head)->next;
        free(aux);

        if ((*head) == NULL) 
        *tail = NULL;
    }
}

remover_fila_int.c
int dequeue_int(Node **head, Node **tail) {
    Node *aux;
    int n;
    if ((*head) != NULL) {
        n = (*head)->data;

        aux = *head;
        *head = (*head)->next;
        free(aux);

        if ((*head) == NULL) 
        *tail = NULL;
    }
    return n;
}

Lista encadeada¶

remover_lista_inicio_void.c
// remover primeiro nó
void remover_inicio_void(Node **head){
    if (*head == NULL){
        return;
    }
    Node *temp = *head;
    *head = (*head)->next;
    free(temp);
}

remover_lista_inicio_int.c
// remover primeiro nó
void remover_inicio_int(Node **head){
    if (*head == NULL){
        return;
    }
    Node *temp;
    int valor = 0;
    if (*head != NULL){
        valor = (*head)->n;
        temp = *head;
        *head = (*head)->next;
        free(temp);
    }
    return valor;
}

remover_lista_valor.c
// remover nó dado valor específico
void remover_por_valor(Node **head, int valor){
    if (*head != NULL)
        return;
    Node *temp = *head;
    Node *anterior = NULL;

    // Se o nó a ser removido for o primeiro
    if (temp != NULL && temp->n == valor){
        *head = temp->next;
        free(temp);
        return;
    }
    // Percorrer a lista procurando o valor
    while (temp != NULL && temp->n != valor){
        anterior = temp;
        temp = temp->next;
    }
    // Se o valor não for encontrado
    if (temp == NULL){
        return;
    }
    // Ajustar ponteiros
    anterior->prox = temp->prox;
    free(temp);
}

remover_lista_index.c
// remover nó dada posição específica
void remover_por_index(Node **head, int pos){
    if (*head == NULL)
        return;
    Node *temp = *head;
    Node *anterior = NULL;
    // Se o nó a ser removido for o primeiro
    if (pos == 0){
        *head = *temp->prox;
        free(*temp);
        return;
    }
    // Percorrer a lista até a posição desejada
    for (int i = 0; i < pos; i++){
        anterior = temp;
        temp = temp->prox;
    }
    // Se a posição é inválida (maior que a lista)
    if (temp == NULL)
        return;
    // Ajustar ponteiros
    anterior->prox = temp->prox;
    free(temp);
}

remover_lista_ultimo.c
// Remover último nó
void remover_ultimo(Node **head){
    if (*head == NULL)
        return;
    Node *temp = *head;
    Node *anterior = NULL;

    // Se há apenas um nó
    if (temp->prox == NULL){
        *head = NULL;
        free(temp);
        return;
    }
    // Percorrer a lista para encontrar o último nó
    while (temp->prox != NULL){
        anterior = temp;
        temp = temp->prox;
    }
    // Ajustar ponteiros
    anterior->prox = NULL;
    // Liberar memória 
    free(temp);
}

L2E¶

Lista circular¶

L2C¶

Imprimir¶

Passos Gerais¶

Passagem por valor - não precisa modificar a estrutura, basta uma cópia para a função executar seu objetivo
Para não perder a referência da head, criar um ponteiro auxiliar temp (opcional em alguns casos, mas necessário em outros. Dispensável na impressão inversa de listas encadeadas, que usa função recursiva)
Verificar se estrutura está vazia - while (head != NULL) (pilhas e filas)
Imprimir cada elemento
Andar cada ponteiro - evitar loop infinito
Fora do loop - printf("NULL\n") - indicar fim da impressão

Variações¶

Pilha¶

imprimir_pilha.c
void printPilha(Node *head){
    // 1 - verificar se a pilha está vazia
    while (head != NULL){
        printf("%d -> ", head->data);
        head = head->next; // 2 - andar ponteiro do nó
    }
    printf("NULL\n");
}

Fila¶

Lista encadeada¶

imprimir_lista.c
// Impressão direta - lista completa
void imprimir_lista(Node *head){
    Node *temp = head;
    while (temp != NULL){
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

imprimir_lista_reversa.c
// Impressão reversa - lista completa
void imprimir_reverso(Node *head){
    if (head == NULL){
        return;
    }
    imprimir_reverso(head);
    printf("%d -> ", head->data);
}

imprimir_lista_index.c
// Imprimir nó na posição fornecida
void imprimir_dado_index(Node *head, int pos){
    Node *temp = head;
    int count = 0;
    while (temp != NULL && count < pos){
        temp = temp->next;
        count++;
    }
    if (temp != NULL){
        printf("Valor na posição %d: %d\n", pos, temp->data);
    } else {
        printf("Posição não encontrada");
    }
}

imprimir_lista_valor.c
// Imprimir posição de um valor específico fornecido
void imprimir_index_dado_valor(Node *head, int valor){
    Node *temp = head;
    int posicao = 0;
    int encontrado = 0;
    while (temp != NULL){
        if (temp->n == valor){
            printf("Valor %d encontrado no index %d\n", valor, posicao);
            encontrado = 1;
            break;
        }
        temp = temp->prox;
        posicao++;
    }
    if (!encontrado){
        printf("Valor %d não encontrado na lista\n");
    }
}

imprimir_lista_pares.c
// Imprimir pares
void imprimir_pares(Node *head){
    Node *temp = head;
    while (temp != NULL){
        if (temp->n % 2 == 0){
            printf("%d -> %d\n", temp->n);
        }
        temp = temp->prox;
    }
    printf("NULL\n");
}

imprimir_lista_maiores.c
void imprimir_maiores_que(Node *head, int limite){
    Node *temp = head;
    while (temp != NULL){
        if (temp->n > limite){
            printf("%d -> ", temp->n);
        }
        temp = temp->prox;
    }
    printf("NULL\n");
}

imprimir_lista_soma.c
// Imprimir soma
void imprimir_soma(Node *head){
    Node *temp = head;
    int soma = 0;
    while (temp != NULL){
        soma += temp->n;
        temp = temp->prox;
    }
    printf("Soma dos valores na lista: %d\n", soma);
}

imprimir_lista_encadeamento.c
// imprimir encadeamento dos nós com endereços de memória
void imprimir_encadeamento(Node *head){
    Node *temp = head;
    while (temp != NULL){
        printf("Valor %d (endereço %p): -> próximo %p\n)", temp->n, (void*)temp, (void*)temp->prox);
        temp = temp->prox;
    }
    printf("NULL\n");
}

imprimir_lista_distancia.c
// imprimir valores e o número de nós até o final da lista

void imprimir_distancia_fim(Node *head){
    Node *temp = head;
    int tamanho = 0;

    // 1 - contar o número total de nós
    while (temp != NULL){
        tamanho++;
        temp = temp->prox;
    }

    // 2 - reiniciar o ponteiro
    temp = head;
    while (temp != NULL){
        printf("Valor %d -> %d nós restantes até o fim", temp->valor, --tamanho);
        temp = temp->prox;
    }
}

imprimir_lista_ultimo.c
// Imprimir apenas o último nó
void imprimir_ultimo(Node *head){
    Node *temp = head;
    if (temp == NULL){
        printf("Lista vazia\n");
        return;
    }
    while (temp->prox != NULL){
        temp = temp->prox;
    }
    printf("Último valor = %d\n", temp->valor);
}

L2E¶

Lista circular¶

L2C¶

Tamanho¶

Passos Gerais¶

Passagem por valor - não precisa modificar a estrutura, basta uma cópia para a função executar seu objetivo
Criar contador
Percorrer lista - while (head != NULL)
Incrementar contador
Andar ponteiro
Return contador

Variações¶

Pilha¶

tamanho_pilha.c
int tamanhoPilha(Node *head){
    // 1 - criar contador
    int cont =  0;
    while (head != NULL){
        cont++;
        head = head->next; // 2 - andar ponteiro do nó
    }
    return cont;
}

Fila¶

tamanho_fila.c
int tamanhoFila(Node *head){
    // 1 - criar contador
    int cont =  0;
    while (head != NULL){
        cont++;
        head = head->next; // 2 - andar ponteiro do nó
    }
    return cont;
}

Lista encadeada¶

tamanho_lista.c
int tamanho_lista(Node *head){
    int cont = 0;
    Node *temp = head;
    while (temp != NULL){
        cont++;
        temp = temp->next;
    }
    return cont;
}

Estruturas de Dados Dinâmicas¶

Geral¶

Operações¶

Inserir¶

Passos Gerais¶

Variações¶

Pilha¶

Fila¶

Lista encadeada¶

L2E¶

Lista circular¶

L2C¶

Remover¶

Passos Gerais¶

Variações¶

Pilha¶

Fila¶

Lista encadeada¶

L2E¶

Lista circular¶

L2C¶

Imprimir¶

Passos Gerais¶

Variações¶

Pilha¶

Fila¶

Lista encadeada¶

L2E¶

Lista circular¶

L2C¶

Tamanho¶

Passos Gerais¶

Variações¶

Pilha¶

Fila¶

Lista encadeada¶

L2E¶

Lista circular¶

L2C¶

Pesquisar¶

Passos Gerais¶

Variações¶

Pilha¶

Fila¶

Lista encadeada¶

L2E¶

Lista circular¶

L2C¶