Estrutura de Armazenamento Encadeado de Listas Lineares - Parte 2

Criação Completa de Listas Encadeadas Simples

Conceito Básico de Criação de Listas

Enquanto a criação de listas lineares com armazenamento sequencial pode ser compreendida intuitivamente através da inicialização de arrays, as listas encadeadas simples operam de maneira diferente. Diferentemente das estruturas sequenciais onde os dados estão concentrados, os dados em listas encadeadas podem estar espalhados por diferentes áreas da memória, com crescimento dinâmico.

Cada lista encadeada não requer alocação prévia de espaço fixo - o tamanho e localização da memória ocupada podem ser determinados em tempo real com base nas condições do sistema e nas necessidades práticas. Em comparação com estruturas sequenciais, as listas encadeadas oferecem maior flexibilidade.

O processo de criação envolve uma geração dinâmica da lista, partindo de um estado inicial vazio e construindo progressivamente nós de elementos para inserção subsequente na lista.

Algoritmo de criação:

• Declarar um nó temporário e variável contador;
• Inicializar uma lista vazia;
• Atribuir NULL ao ponteiro do nó cabeça, criando assim uma lista encadeada com nó cabeça;
• Iterar para atribuição e inserção de nós subsequentes;

Método de Inserção pela Cabeça

Este método começa com uma lista vazia, gera novos nós, armazena dados no campo de dados do novo nó e insere o novo nó na posição imediatamente após a cabeça da lista (posição referenciada pelo ponteiro head).

Basicamente, posiciona cada novo elemento na primeira posição após a cabeça:

• Fazer o next do novo nó apontar para o que vinha após a cabeça;
• Fazer o next da cabeça apontar para o novo nó;

Analogamente, é como se estivesse constantemente fazendo fila com prioridade na primeira posição.

void criarListaCabeca(ListaEncadeada *lista, int tamanho) {
    ListaEncadeada novoNo;
    int indice;

    srand(time(0)); // inicializa semente para números aleatórios
    
    *lista = (ListaEncadeada)malloc(sizeof(No));
    (*lista)->proximo = NULL;

    for(indice = 0; indice < tamanho; indice++) {
        novoNo = (ListaEncadeada)malloc(sizeof(No)); // cria novo nó
        novoNo->dados = rand() % 100 + 1;
        novoNo->proximo = (*lista)->proximo;
        (*lista)->proximo = novoNo;
    }
}

Método de Inserção pela Cauda

Embora o método de inserção pela cabeça seja algoritmicamente simples, ele resulta em ordem inversa dos dados de entrada. Podemos inverter essa abordagem: inserir novos nós sempre no final, conhecido como método de inserção pela cauda - um tópico importante para exames.

Este método lê sequencialmente elementos de um array, cria um novo nó para cada elemento, armazena o dado no nó e o insere no final da lista atual até que todos os elementos do array sejam processados. É necessário manter um ponteiro auxiliar que sempre aponta para o último nó da lista, atualizando-o após cada inserção. Finalmente, o campo próximo do nó final deve ser definido como NULL.

void criarListaCauda(NoLista *&cabeca, TipoElemento dados[], int quantidade) {
    NoLista *novo, *ultimo;
    cabeca = (NoLista *)malloc(sizeof(NoLista)); // cria nó cabeça
    ultimo = cabeca; // ultimo sempre aponta para o nó final, inicialmente o nó cabeça
    for(int idx = 0; idx < quantidade; idx++) {
        novo = (NoLista *)malloc(sizeof(NoLista));
        novo->conteudo = dados[idx]; // cria nó de dados
        ultimo->proximo = novo; // insere nó novo após nó ultimo
        ultimo = novo;
    }
    ultimo->proximo = NULL; // define next do nó final como NULL
}

Exclusão Completa de Listas Encadeadas

Quando uma lista encadeada não será mais utilizada, ela deve ser destruída, liberando a memória para uso por outros programas ou softwares. O algoritmo segue esta lógica:

• Declarar nós temporários;
• Atribuir o primeiro nó a um temporário, o próximo a outro;
• Iterar liberando o nó atual e movendo para o próximo;

Status limparLista(ListaEncadeada *cabeca) {
    ListaEncadeada atual, proximo;
    atual = (*cabeca)->proximo;
    
    while(atual != NULL) {
        proximo = atual->proximo;
        free(atual);
        atual = proximo;
    }
    (*cabeca)->proximo = NULL;

    return SUCESSO;
}

Um erro comum é acreditar que a variável 'proximo' é desnecessária, pensando que basta escrever free(atual); atual = atual->proximo; dentro do loop. No entanto, 'atual' é um nó completo com dados e campo de ponteiro. Quando executamos free(atual), todo o nó é excluído e sua memória liberada, incluindo o ponteiro para o próximo nó. Como a exclusão completa requer remoção nó por nó, precisamos do auxiliar 'proximo' para manter registro do próximo nó.

Vantagens Comparativas entre Estruturas Encadeadas e Sequenciais

Vamos comparar sob três aspectos: alocação de armazenamento, desempenho temporal e desempenho espacial.

Alocação de Armazenamento

• Estruturas sequenciais usam segmentos contíguos de memória para armazenar elementos lineares;
• Listas encadeadas usam estrutura encadeada com unidades arbitrárias de memória para armazenar elementos;

Desempenho Temporal

Pesquisa:

• Estruturas sequencaiis têm complexidade O(1)
• Listas encadeadas têm complexidade O(n)

Inserção e Exclusão:

• Estruturas sequenciais requerem movimentação média de metade dos elementos, tempo O(n)
• Listas encadeadas executam inserção/exclusão em tempo O(1) após calcular ponteiro da posição

Desempenho Espacial

• Estruturas sequenciais requerem alocação prévia, excesso causa desperdício, insuficiência causa overflow;
• Listas encadeadas não precisam de alocação fixa, elementos são alocados conforme disponibilidade;

Conclusão

Com base nessa comparação, podemos tirar conclusões empíricas:

• Para listas lineares com pesquisa frequente e poucas operações de inserção/exclusão, estruturas sequenciais são adequadas;
• Para listas com inserções/exclusões frequentes, estruturas encadeadas são preferíveis;

Por exemplo, em desenvolvimento de jogos, para informações pessoais de usuários registrados, além da inserção inicial, a maioria das operações são leituras, então estruturas sequenciais devem ser consideradas. Já para inventários de armas ou listas de equipamentos dos jogadores, que podem aumentar ou diminuir durante o jogo, estruturas sequenciais tornam-se inadequadas e listas encadeadas se mostram mais eficazes.

Quando o número de elementos varia significativamente ou é desconhecido, listas encadeadas são ideais, eliminando preocupações com tamanho de espaço de armazenamento. Se o tamanho aproximado da lista linear é conhecido previamente, como 12 meses ou 7 dias da semana, estruturas sequenciais oferecem maior eficiência.

Em resumo, estruturas sequenciais e encadeadas de listas lineares possuem vantagens e desvantagens respectivas, não podendo afirmar categoricamente qual é melhor. A escolha depende da análise das circunstâncias reais para determinar qual estrutura de dados atende melhor aos requisitos e desempenho esperados.