Conceito de Lista Linear

Uma lista linear é uma estrutura de dados que armazena elementos em uma sequência ordenada, onde cada item possui uma posição bem definida. No cotidiano, essa estrutura pode ser observada em situações como listas de amigos em redes sociais ou menus de navegação em aplicativos.

Matematicamente, uma lista linear L pode ser descrita como L = {a₁, a₂, ..., aₙ}, onde aᵢ representa os elementos individuais e n indica o comprimento atual da lista. Quando n = 0, a lista é considerada vazia. Em termos formais, a estrutura é definida por um par ordenado (D, R), com D sendo o conjunto de eleemntos e R representando as relações de precedência entre eles.

Propriedades Essenciais

Elementos extremos: O primeiro elemento da lista não possui predecessor, enquanto o último não tem sucessor. Para elementos intermediários aᵢ (onde 1 < i < n), existe exatamente um predecessor imediato aᵢ₋₁ e um sucessor imediato aᵢ₊₁, garantindo a linearidade da estrutura.

Armazenamento Sequencial

Nesse esquema, os elementos são armazenados em endereços de memória contíguos, mantenod a ordem lógica diretamente mapeada para a organização física. Essa abordagem permite acesso aleatório direto aos elementos, desde que a posição seja conhecida, resultando em alta eficiência operacional.

Características principais:

• Localização física adjacente para elementos logicamente vizinhos.
• Capacidade de acesso direto via cálculo de endereço baseado no índice.
• Alta densidade de armazenamento, pois não há necessidade de ponteiros adicionais para relacionamentos.

Implementação em Linguagem C

A estrutura de dados é definida com um array estático e um contador de elementos:

#define CAPACIDADE 200

typedef struct {
    int dados[CAPACIDADE];
    int quantidade;
} ListaSeq;

Inicialização da lista com contador zerado:

void CriarLista(ListaSeq *l) {
    l->quantidade = 0;
}

Inserção de um elemento em posição específica:

int AdicionarElemento(ListaSeq *l, int posicao, int valor) {
    if (l->quantidade == CAPACIDADE) {
        return 0;
    }
    if (posicao < 0 || posicao > l->quantidade) {
        return 0;
    }
    for (int k = l->quantidade; k > posicao; k--) {
        l->dados[k] = l->dados[k-1];
    }
    l->dados[posicao] = valor;
    l->quantidade++;
    return 1;
}

Remoção de um elemento por índice:

int EliminarElemento(ListaSeq *l, int posicao) {
    if (l->quantidade == 0) {
        return 0;
    }
    if (posicao < 0 || posicao >= l->quantidade) {
        return 0;
    }
    for (int k = posicao; k < l->quantidade - 1; k++) {
        l->dados[k] = l->dados[k+1];
    }
    l->quantidade--;
    return 1;
}

Busca linear por valor, retornando o índice da primeira ocorrência:

int LocalizarValor(ListaSeq *l, int alvo) {
    for (int k = 0; k < l->quantidade; k++) {
        if (l->dados[k] == alvo) {
            return k;
        }
    }
    return -1;
}

Exibição sequencial dos elementos armazenados:

void MostrarConteudo(ListaSeq *l) {
    for (int k = 0; k < l->quantidade; k++) {
        printf("%d ", l->dados[k]);
    }
    printf("\n");
}

Operação de Fusão

Para combinar duas listas mantendo elementos únicos, percorre-se a segunda lista e insere na primeira apenas elementos não existentes:

void UnirListas(ListaSeq *listaPrincipal, ListaSeq *listaSecundaria) {
    for (int k = 0; k < listaSecundaria->quantidade; k++) {
        int valorAtual = listaSecundaria->dados[k];
        if (LocalizarValor(listaPrincipal, valorAtual) == -1) {
            AdicionarElemento(listaPrincipal, listaPrincipal->quantidade, valorAtual);
        }
    }
}

Exemplo de uso integrado:

int main() {
    ListaSeq listaA, listaB;
    CriarLista(&listaA);
    CriarLista(&listaB);

    AdicionarElemento(&listaA, 0, 10);
    AdicionarElemento(&listaA, 1, 20);
    AdicionarElemento(&listaA, 2, 30);

    AdicionarElemento(&listaB, 0, 20);
    AdicionarElemento(&listaB, 1, 40);
    AdicionarElemento(&listaB, 2, 50);

    UnirListas(&listaA, &listaB);
    MostrarConteudo(&listaA);

    return 0;
}