Listas encadeadas em C

Uma lista encadeada é uma estrutura de dados dinâmica na qual os elementos (nós) são conectados usando ponteiros.

Nesta lição, você aprenderá:

• Como as listas encadeadas funcionam.
• Como inserir e excluir nós em uma lista encadeada.
• As vantagens das listas encadeadas em relação aos vetores.

Exemplo: definindo um Node de lista encadeada

Em C, um nó de lista encadeada é definido usando uma struct com um campo de dados e um ponteiro para o próximo nó.

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

struct Node {
    int data;
    struct Node *next;
};

int main() {
    struct Node *head = NULL;
    return 0;
}

Inserindo um Node no início

Para inserir um novo nó no início de uma lista encadeada:

• Crie um novo nó.
• Defina o ponteiro next dele para o início atual.
• Atualize o ponteiro inicial.

Exemplo: inserindo um Node no início

Este programa insere um novo nó no início de uma lista encadeada.

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

struct Node {
    int data;
    struct Node *next;
};

void insertAtBeginning(struct Node **head, int newData) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

int main() {
    struct Node *head = NULL;
    insertAtBeginning(&head, 10);
    printf("Inserted: %d\n", head->data);
    return 0;
}

Excluindo um Node

Para excluir um nó de uma lista encadeada:

• Encontre o nó que será excluído.
• Atualize o ponteiro next do nó anterior.
• Libere a memória do nó excluído.

Exemplo: excluindo um Node

Este programa exclui um nó de uma lista encadeada.

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

struct Node {
    int data;
    struct Node *next;
};

void deleteNode(struct Node **head, int key) {
    struct Node *temp = *head, *prev;
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

int main() {
    struct Node *head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 10;
    head->next = NULL;
    deleteNode(&head, 10);
    return 0;
}

Vantagens das listas encadeadas

As listas encadeadas têm várias vantagens em relação aos vetores:

• Tamanho dinâmico (não é necessário especificar o tamanho antecipadamente).
• Inserções e exclusões eficientes.
• Não há desperdício de memória causado por tamanhos fixos.

Resumo

Nesta lição, você aprendeu:

• O que são listas encadeadas e como elas funcionam.
• Como inserir e excluir nós.
• As vantagens das listas encadeadas em relação aos vetores.

Em seguida, você explorará pilhas e filas em C!