Conceitos Fundamentais de Listas Lineares

Uma lista linear é uma estrutura de dados que organiza elementos em uma sequência ordenada, onde cada item posui um predecessor e um sucessor, com exceção do primeiro e último elementos. Esta estrutura pode ser implementada de duas maneiras principais: listas sequenciais (baseadas em arrays) e listas encadeadas (baseadas em ponteiros).

Lista Sequencial

A lista sequencial, também chamada de lista estática, armazena elementos em posições de memória contíguas. Essa característica permite acesso aleatório em tempo constante O(1), dado o endereço inicial e o índice do elemento desejado. Em linguagens como C, isso é frequentemente implementado com arrays de tamanho fixo ou dinâmico. O código abaixo ilustra uma implemenatção estática com capacidade predefinida.

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

#define CAPACIDADE 100  // Capacidade máxima da lista

typedef struct {
    int itens[CAPACIDADE]; // Array que armazena os dados
    int quant;             // Número atual de elementos
} ListaArray;

void InicializarLista(ListaArray *arr) {
    arr->quant = 0;
}

int InserirNaLista(ListaArray *arr, int pos, int elem) {
    if (pos < 1 || pos > arr->quant + 1) {
        fprintf(stderr, "Posição de inserção inválida!\n");
        return 0;
    }
    if (arr->quant >= CAPACIDADE) {
        fprintf(stderr, "Lista cheia, não é possível inserir!\n");
        return 0;
    }
    for (int idx = arr->quant; idx >= pos; idx--) {
        arr->itens[idx] = arr->itens[idx - 1];
    }
    arr->itens[pos - 1] = elem;
    arr->quant++;
    return 1;
}

int RemoverDaLista(ListaArray *arr, int pos, int *removido) {
    if (pos < 1 || pos > arr->quant) {
        fprintf(stderr, "Posição de remoção inválida!\n");
        return 0;
    }
    *removido = arr->itens[pos - 1];
    for (int idx = pos; idx < arr->quant; idx++) {
        arr->itens[idx - 1] = arr->itens[idx];
    }
    arr->quant--;
    return 1;
}

int LocalizarElemento(ListaArray arr, int valor) {
    for (int i = 0; i < arr.quant; i++) {
        if (arr.itens[i] == valor) {
            return i + 1; // Retorna posição (base 1)
        }
    }
    return 0; // Elemento não encontrado
}

int RecuperarElemento(ListaArray arr, int pos, int *valor) {
    if (pos < 1 || pos > arr.quant) {
        fprintf(stderr, "Posição inválida!\n");
        return 0;
    }
    *valor = arr.itens[pos - 1];
    return 1;
}

void MostrarLista(ListaArray arr) {
    printf("Conteúdo da lista: ");
    for (int i = 0; i < arr.quant; i++) {
        printf("%d ", arr.itens[i]);
    }
    printf("\n");
}

int main() {
    ListaArray minhaLista;
    InicializarLista(&minhaLista);

    InserirNaLista(&minhaLista, 1, 5);
    InserirNaLista(&minhaLista, 2, 15);
    InserirNaLista(&minhaLista, 3, 25);
    MostrarLista(minhaLista);

    int pos = LocalizarElemento(minhaLista, 15);
    if (pos) {
        printf("O elemento 15 está na posição: %d\n", pos);
    }

    int rem;
    if (RemoverDaLista(&minhaLista, 2, &rem)) {
        printf("Elemento removido: %d\n", rem);
    }
    MostrarLista(minhaLista);

    int val;
    if (RecuperarElemento(minhaLista, 1, &val)) {
        printf("Primeiro elemento: %d\n", val);
    }

    return 0;
}

Lista Encadeada

Em uma lista encadeada, os elementos são armazenados em nós distribuídos em diferentes posições de memória. Cada nó contém um campo de dados e um ou mais ponteiros que apontam para outros nós, estabelecendo a ordem lógica. As variantes incluem listas simplesmente encadeadas, circulares e duplamente encadeadas.

Lista Simplesmente Encadeada

Cada nó possui um único ponteiro que aponta para o próximo nó na sequência. O primeiro nó é frequentemente referenciado por uma cabeça de lista, e um nó cabeça pode ser usado para simplificar operações.

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

typedef struct No {
    int dado;
    struct No *seguinte;
} No;

No* CriarNo(int valor) {
    No *novo = (No *)malloc(sizeof(No));
    if (!novo) {
        perror("Erro na alocação de memória");
        exit(EXIT_FAILURE);
    }
    novo->dado = valor;
    novo->seguinte = NULL;
    return novo;
}

void AdicionarNoInicio(No **cabeca, int valor) {
    No *novo = CriarNo(valor);
    novo->seguinte = *cabeca;
    *cabeca = novo;
}

void AdicionarNoFim(No **cabeca, int valor) {
    No *novo = CriarNo(valor);
    if (*cabeca == NULL) {
        *cabeca = novo;
        return;
    }
    No *atual = *cabeca;
    while (atual->seguinte != NULL) {
        atual = atual->seguinte;
    }
    atual->seguinte = novo;
}

void ExcluirNo(No **cabeca, int valor) {
    No *atual = *cabeca;
    No *anterior = NULL;

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

    if (atual == NULL) return; // Valor não encontrado

    if (anterior == NULL) {
        *cabeca = atual->seguinte;
    } else {
        anterior->seguinte = atual->seguinte;
    }
    free(atual);
}

void ImprimirLista(No *cabeca) {
    No *temp = cabeca;
    while (temp != NULL) {
        printf("%d -> ", temp->dado);
        temp = temp->seguinte;
    }
    printf("NULL\n");
}

void LiberarLista(No *cabeca) {
    No *temp;
    while (cabeca != NULL) {
        temp = cabeca;
        cabeca = cabeca->seguinte;
        free(temp);
    }
}

int main() {
    No *lista = NULL;

    AdicionarNoInicio(&lista, 30);
    AdicionarNoInicio(&lista, 20);
    AdicionarNoInicio(&lista, 10);
    AdicionarNoFim(&lista, 40);
    AdicionarNoFim(&lista, 50);

    printf("Lista inicial: ");
    ImprimirLista(lista);

    ExcluirNo(&lista, 30);
    printf("Após remover o 30: ");
    ImprimirLista(lista);

    LiberarLista(lista);
    return 0;
}

Lista Circular

Em uma lista circular, o último nó aponta de volta para o primeiro nó, formando um anel. Isso permite traversar a lista continuamente a partir de qualquer nó.

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

typedef struct NoCirc {
    int valor;
    struct NoCirc *prox;
} NoCirc;

typedef NoCirc* ListaCirc;

void CriarListaCirc(ListaCirc *lista) {
    *lista = (ListaCirc)malloc(sizeof(NoCirc));
    (*lista)->prox = *lista; // Aponta para si mesmo, lista vazia
}

int InserirEmCirc(ListaCirc lista, int pos, int elem) {
    NoCirc *p = lista;
    int cont = 0;

    while (p->prox != lista && cont < pos - 1) {
        p = p->prox;
        cont++;
    }

    if (cont != pos - 1) {
        fprintf(stderr, "Posição inválida!\n");
        return 0;
    }

    NoCirc *novo = (NoCirc *)malloc(sizeof(NoCirc));
    novo->valor = elem;
    novo->prox = p->prox;
    p->prox = novo;
    return 1;
}

int RemoverDeCirc(ListaCirc lista, int pos, int *removido) {
    NoCirc *p = lista;
    int cont = 0;

    while (p->prox != lista && cont < pos - 1) {
        p = p->prox;
        cont++;
    }

    if (p->prox == lista || cont != pos - 1) {
        fprintf(stderr, "Posição inválida!\n");
        return 0;
    }

    NoCirc *alvo = p->prox;
    *removido = alvo->valor;
    p->prox = alvo->prox;
    free(alvo);
    return 1;
}

void ExibirListaCirc(ListaCirc lista) {
    NoCirc *p = lista->prox;
    printf("Lista circular: ");
    while (p != lista) {
        printf("%d ", p->valor);
        p = p->prox;
    }
    printf("\n");
}

int main() {
    ListaCirc lista;
    CriarListaCirc(&lista);

    InserirEmCirc(lista, 1, 100);
    InserirEmCirc(lista, 2, 200);
    InserirEmCirc(lista, 3, 300);
    ExibirListaCirc(lista);

    int rem;
    if (RemoverDeCirc(lista, 2, &rem)) {
        printf("Elemento removido: %d\n", rem);
    }
    ExibirListaCirc(lista);

    free(lista);
    return 0;
}

Lista Duplamente Encadeada

Cada nó contém ponteiros tanto para o nó anterior quanto para o próximo, permitindo navegação bidirecional. Quando conectada em um ciclo, torna-se uma lista duplamente encadeada circular.

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

typedef struct NoDuplo {
    int chave;
    struct NoDuplo *ant;
    struct NoDuplo *prox;
} NoDuplo;

typedef NoDuplo* ListaDupla;

void InicializarDupla(ListaDupla *lista) {
    *lista = (ListaDupla)malloc(sizeof(NoDuplo));
    (*lista)->ant = *lista;
    (*lista)->prox = *lista;
}

int InserirDupla(ListaDupla lista, int pos, int elem) {
    NoDuplo *p = lista;
    int cont = 0;

    while (p->prox != lista && cont < pos - 1) {
        p = p->prox;
        cont++;
    }

    if (cont != pos - 1) {
        fprintf(stderr, "Posição inválida!\n");
        return 0;
    }

    NoDuplo *novo = (NoDuplo *)malloc(sizeof(NoDuplo));
    novo->chave = elem;
    novo->prox = p->prox;
    novo->ant = p;
    p->prox->ant = novo;
    p->prox = novo;
    return 1;
}

int RemoverDupla(ListaDupla lista, int pos, int *removido) {
    NoDuplo *p = lista->prox;
    int cont = 1;

    while (p != lista && cont < pos) {
        p = p->prox;
        cont++;
    }

    if (p == lista || cont > pos) {
        fprintf(stderr, "Posição inválida!\n");
        return 0;
    }

    *removido = p->chave;
    p->ant->prox = p->prox;
    p->prox->ant = p->ant;
    free(p);
    return 1;
}

void ImprimirDupla(ListaDupla lista) {
    NoDuplo *p = lista->prox;
    printf("Lista duplamente encadeada: ");
    while (p != lista) {
        printf("%d ", p->chave);
        p = p->prox;
    }
    printf("\n");
}

int main() {
    ListaDupla lista;
    InicializarDupla(&lista);

    InserirDupla(lista, 1, 500);
    InserirDupla(lista, 2, 600);
    InserirDupla(lista, 3, 700);
    ImprimirDupla(lista);

    int rem;
    if (RemoverDupla(lista, 2, &rem)) {
        printf("Elemento removido: %d\n", rem);
    }
    ImprimirDupla(lista);

    free(lista);
    return 0;
}