Conteúdo - Portfólio Enzo Stafuza

Listas Encadeadas

Na disciplina de Estrutura de Dados, estudamos as listas encadeadas, uma estrutura de dados dinâmica fundamental que organiza elementos de forma sequencial através de ponteiros, permitindo operações eficientes de inserção e remoção.

O que são Listas Encadeadas?

Uma lista encadeada é uma coleção de nós onde cada elemento contém um valor e um ponteiro para o próximo nó da sequência. Diferente dos vetores, as listas encadeadas não exigem alocação contígua de memória.

Cada elemento é chamado de nó (node)
O primeiro nó é chamado de cabeça (head)
O último nó aponta para NULL
Não possui tamanho fixo - cresce conforme a necessidade

Comparação: Vetores vs Listas Encadeadas

Vetores (Arrays)	Listas Encadeadas
Tamanho fixo	Tamanho dinâmico
Alocação contígua de memória	Alocação dispersa na memória
Acesso rápido por índice (O(1))	Acesso sequencial (O(n))
Inserções/remoções custosas no meio	Inserções/remoções eficientes

Estrutura de um Nó

Em C, cada nó é representado por uma struct que contém:

struct No { int valor; // Dado armazenado struct No *prox; // Ponteiro para o próximo nó };

Visualização de uma lista com 3 nós:

[10 | *] → [20 | *] → [30 | NULL]

Vantagens e Desvantagens

Vantagens:

Tamanho flexível (cresce/shrink conforme necessidade)
Inserções e remoções eficientes (O(1) no início)
Não desperdiça memória com alocação prévia
Ótima para implementação de pilhas e filas

Desvantagens:

Acesso sequencial (precisa percorrer para encontrar elementos)
Maior consumo de memória (armazena ponteiros além dos dados)
Não permite acesso aleatório eficiente
Mais complexa de implementar que arrays

Operações Principais

As operações básicas em listas encadeadas incluem:

Inserção no início - Adiciona um novo nó no começo da lista
Inserção no fim - Adiciona um novo nó no final da lista
Remoção - Remove um nó com valor específico
Busca - Procura um valor na lista
Percorrer - Visita todos os nós da lista

Inserção no Início

Adiciona um novo elemento no começo da lista, tornando-o o novo head:

struct No* inserirInicio(struct No *head, int novoValor) { struct No *novoNo = (struct No*)malloc(sizeof(struct No)); novoNo->valor = novoValor; novoNo->prox = head; // Novo nó aponta para o antigo head return novoNo; // Retorna o novo nó como novo head }

Complexidade: O(1) - tempo constante

Inserção no Fim

Adiciona um novo elemento no final da lista, exigindo percorrê-la até o último nó:

struct No* inserirFim(struct No *head, int novoValor) { struct No *novoNo = (struct No*)malloc(sizeof(struct No)); novoNo->valor = novoValor; novoNo->prox = NULL;
if (head == NULL) return novoNo;

struct No *atual = head;
while (atual->prox != NULL) {
    atual = atual->prox;
}
atual->prox = novoNo;
return head;
}

Complexidade: O(n) - precisa percorrer toda a lista

Remoção de um Elemento

Remove um nó específico da lista, ajustando os ponteiros vizinhos:

struct No* removerElemento(struct No *head, int valor) { if (head == NULL) return NULL;
// Caso especial: remoção do primeiro nó
if (head->valor == valor) {
    struct No *temp = head->prox;
    free(head);
    return temp;
}

struct No *anterior = head;
struct No *atual = head->prox;

while (atual != NULL && atual->valor != valor) {
    anterior = atual;
    atual = atual->prox;
}

if (atual != NULL) {
    anterior->prox = atual->prox;
    free(atual);
}

return head;
}

Percorrer a Lista

Visita cada nó da lista sequencialmente, útil para imprimir ou processar elementos:

void imprimirLista(struct No *head) { struct No *atual = head; while (atual != NULL) { printf("%d -> ", atual->valor); atual = atual->prox; } printf("NULL\n"); }

Busca de Elemento

Procura por um valor específico na lista, retornando seu endereço se encontrado:

struct No* buscarElemento(struct No *head, int valor) { struct No *atual = head; while (atual != NULL) { if (atual->valor == valor) { return atual; } atual = atual->prox; } return NULL; }

Aplicações das Listas Encadeadas

As listas encadeadas são fundamentais para implementar:

Pilhas (Stacks) - LIFO (Last In First Out)
Filas (Queues) - FIFO (First In First Out)
Listas duplamente encadeadas - Navegação em ambas direções
Grafos - Representação de adjacências
Sistemas de arquivos - Alocação não contígua

Lista Encadeada