Lista Encadeada - Conceito, e implementação em C

A lista encadeada é uma das estruturas de dados fundamentais no estudo de programação e ciência da computação. Diferente dos arrays, que são estruturas estáticas, onde os elementos ocupam posições contínuas na memória, a Lista Encadeada é uma estrutura de dados composta por nós, onde cada nó contém um valor e um ponteiro para o próximo nó.

Isso permite que os elementos sejam armazenados em diferentes posições da memória. Essa flexibilidade é útil quando precisamos inserir ou remover elementos dinamicamente, sem a necessidade de pré-alocar toda a estrutura.

Neste artigo, explicaremos os conceitos principais das listas encadeadas, e demonstraremos a sua implementação usando linguagem C.

Antes de aprofundar no conceito e implementação da lista encadeada, é importante que você já esteja familiarizado com conceitos básicos de estruturas de dados, e já tenha familiaridade com registros e ponteiros.

O que é uma lista encadeada?

A lista encadeada é uma estrutura de dados que permite armazenar uma coleção de elementos de forma dinâmica. Diferente dos arrays, onde os elementos são armazenados em posições contínuas na memória, a lista encadeada consiste em nós que podem estar dispersos em diferentes locais.

Cada nó contém um valor e um ponteiro que aponta para o próximo nó da lista. Essa característica torna a lista encadeada uma escolha popular para situações em que a quantidade de dados pode variar ao longo do tempo, permitindo inserções e remoções de maneira eficiente.

Comparação entre um array e uma lista encadeada na memória do computador

A imagem acima demonstra a diferença da alocação de memória entre um array e uma lista encadeada. O array é alocado em um único bloco de memória, que contém todos os seus nós. Enquanto isso, a lista encadeada não tem nenhum padrão na alocação desses nós, sendo necessário que cada nó guarde o endereço do próximo.

O conceito de lista encadeada é fundamental na ciência da computação, pois proporciona uma maneira flexível de manipular dados. Os nós podem ser facilmente adicionados ou removidos sem a necessidade de deslocar outros elementos, como acontece em arrays.

Existem variações da lista encadeada simples, como as listas duplamente encadeadas e listas circulares. Cada variante possui suas próprias características e aplicações, mas todas compartilham o conceito de ter elementos armazenados em nós, conectados por ponteiros.

Vantagens e desvantagens de usar uma lista encadeada

A utilização de uma lista encadeada apresenta uma série de benefícios e também alguns pontos negativos que devem ser levados em consideração antes de decidir utilizá-la em um projeto.

Abaixo, destacamos as principais vantagens e desvantagens:

Vantagens

Inserção e remoção flexíveis:
- Ao contrário dos arrays, nos quais a remoção ou inserção de um elemento pode exigir o deslocamento de vários outros, as listas encadeadas permitem adicionar ou remover nós apenas atualizando ponteiros.
  - Isso torna as operações mais ágeis em termos de modificação da estrutura, especialmente em posições estratégicas (início ou fim da lista).
Alocação dinâmica de memória:
- A lista encadeada não depende de um tamanho pré-definido. Ela cresce ou diminui conforme novos nós são criados ou removidos.
  - Essa característica evita desperdício de memória e possibilita a adaptação conforme as necessidades da aplicação variam.
Facilidade de implementação de outras estruturas:
- A partir de uma lista encadeada, é simples implementar outras estruturas mais especializadas, como filas e pilhas, alterando apenas o padrão de inserção e remoção de elementos.

Desvantagens

Acesso sequencial aos elementos:
- Uma das principais limitações é que, para acessar um nó específico, é necessário percorrer a lista do início até encontrar o elemento desejado.
  - Isso resulta em complexidade O(n) para buscas, tornando a lista encadeada menos eficiente para acesso aleatório de elementos.
Consumo de memória adicional:
- Cada nó da lista precisa armazenar, além do valor, o ponteiro para o próximo nó (e, em listas duplamente encadeadas, o ponteiro para o nó anterior).
  - Isso aumenta o consumo de memória em relação a estruturas mais compactas como arrays.
Localidade de memória fraca:
- Como os nós podem estar espalhados na memória, o uso de caches de CPU é menos otimizado.
  - Isso pode resultar em menor eficiência do ponto de vista de desempenho em sistemas com grande volume de dados e alto índice de acessos aleatórios.

Em suma, as listas encadeadas são ideais quando o foco está em inserções e remoções frequentes, bem como na flexibilidade e adaptabilidade a diferentes tamanhos.

Contudo, quando o acesso rápido a elementos aleatórios é crítico, estruturas estáticas e indexadas (como os arrays) são mais indicadas.

Lista encadeada em C

Entendido o conceito básico de uma lista encadeada, podemos partir para a implementação. O primeiro passo é construir a estrutura que será utilizada para construir a lista.

Como foi comentado anteriormente, uma lista encadeada é formada por uma série de nós que contém um elemento, e um ponteiro para o próximo nó. Em Linguagem C, podemos construir uma estrutura assim da seguinte forma:

struct tipoNo {
    int elem;
    struct tipoNo* prox;
};

Com o registro acima, já temos o suficiente para construir uma lista encadeada, agora precisamos implementar as operações da nossa lista.

Inserção na lista encadeada

A primeira operação que vamos implementar, é a inserção de um elemento em uma lista encadeada. A inserção pode ser feita em qualquer ponto da lista, no início, no fim, ou após qualquer elemento, tudo vai depender do contexto.

Para o nosso exemplo, vamos adotar o padrão de sempre inserir os elementos no fim da lista. Nesse caso, o nosso algoritmo vai precisar percorrer a lista inteira, a fim de achar o último elemento, e inserir o novo elemento após ele.

void insereItem(struct tipoNo** lista, int elem)
{
    struct tipoNo* novo = (struct tipoNo*) malloc(sizeof(struct tipoNo));
    struct tipoNo* aux = *lista;

    novo->elem = elem;
    novo->prox = NULL;

    while (aux->prox != NULL) {
        aux = aux->prox;
    }
    aux->prox = novo;
}

A linha 3 da função, é responsável por fazer a alocação do novo nó que será inserido na lista. Caso você ainda não esteja familiarizado com esse contexto, é importante dar uma estudada sobre alocação dinâmica de memória.

Uma vez que o novo nó tenha sido criado, o loop while da linha 9, vai percorrer a lista inteira, até o último elemento (aux->prox == NULL). Ao encontrar o último elemento da lista, fazemos o ponteiro prox dele apontar para o novo elemento.

Busca na lista encadeada

Uma outra operação necessária em conjuntos de dados, é encontrar um elemento específico. Vamos imaginar que temos a seguinte necessidade: dada uma lista encadeada, e um elemento x devemos retornar a posição em que o elemento está localizado na lista, ou -1 caso ele não seja encontrado.

Para implementar essa funcionalidade, podemos criar uma função como a abaixo:

int buscaItem(struct tipoNo** lista, int elem)
{
    struct tipoNo* aux = *lista;
    int pos = 0;
    
    while (aux != NULL) {
        if (aux -> elem == elem) {
            break;
        }
    
        aux = aux -> prox;
        pos++;
    }
    
    if (aux != NULL) {
        return pos;
    }

    return -1;
}

O loop da linha 6, vai percorrer a lista inteira, caso encontre o elemento em algum momento, na condição da linha 7, interrompe o loop, e a cada iteração, incrementa a variável pos que será responsável por controlar a última posição checada.

Ao final do loop, temos uma condição na linha 15, que é responsável por identificar se o loop foi interrompido pela condição da linha 7 (indicando que o elemento foi encontrado), nesse caso, retorna a posição onde o elemento foi encontrado.

Em caso negativo, a função retorna -1 indicando que o elemento não existe na lista.

Remoção na lista encadeada

Para a operação de remoção em uma lista encadeada, podemos ter diversas abordagens, a mais simples de todas é a de remover o elemento do início da lista.

Para isso, basta fazer o ponteiro do primeiro elemento passar a próximo, e liberar a memória do primeiro nó.

void removeItem(struct tipoNo** lista)
{
    struct tipoNo* aux = *lista;
    *lista = aux -> prox; // aponta o início da lista o proximo elemento
    
    free(aux); // libera a memória do primeiro nó
}

O código acima demonstra essa implementação. Ao utilizar as funções de inserção e remoção demonstradas aqui, teremos uma lista implementando o algoritmo FIFO (First In, First Out). Ou seja, temos uma fila implementada utilizando lista encadeada.

Uma abordagem um pouco mais complexa, é remover um elemento específico da lista, nesse caso, é necessário buscar o elemento na mesma, e só então removê-lo.

void removeItem(struct tipoNo** lista, int elem)
{
    struct tipoNo* aux = *lista;
    
    // checa se o elemento é o primeiro da lista
    if (aux -> elem == elem) {
        *lista = aux -> prox;
        free(aux);
    }
    
    struct tipoNo* prev = aux;
    aux = aux -> prox;
    while (aux != NULL) {
        if (aux -> elem == elem) {
            break;
        }
    
        prev = aux;
        aux = aux -> prox;        
    }
    
    // elemento foi encontrado
    if (aux != NULL) {
        prev -> prox = aux -> prox;
        free(aux);
    }
}

O código acima implementa o algoritmo descrito anteriormente. O laço while é responsável por buscar o elemento, guardando sempre um ponteiro para o elemento anterior prev, isso é necessário para fazer a remoção do elemento, fazendo o elemento anterior passar para o elemento posterior ao removido prev->prox = aux->prox.

Conclusão e desafio para casa

Essas são as principais operações que podem ser implementadas com uma Lista Encadeada, que é uma estrutura básica para construção de diversas outras estruturas de dados mais complexas.

Espero que você tenha conseguido entender bem essa estrutura. Para testar um pouco seus conhecimentos, tente resolver o seguinte exercício:

Implemente uma lista encadeada que mantenha os seus elementos utilizando a estrutura LIFO (Last In, First out). Ou seja, o último elemento a ser inserido na fila, é sempre o primeiro a ser removido.

Você pode tentar apenas adaptar os algoritmos deste artigo para seguir a lógica solicitada, mas pode também tentar implementar do zero.

Qualquer dúvida, não deixe de colocar nos comentários.

Um abraço e até a próxima.

Andrew Cavalcante Pacífico

Bacharel em Ciência da Computação pela Universidade Federal do Amazonas, MBA em Gerenciamento de Projetos pela Fundação Getúlio Vargas.

Atualmente trabalha como Gerente de Engenharia na Meliuz.

Com 20 anos de experiência na área, já trabalhou com um pouco de tudo, C, C++, Java, C#, Delphi, Node.js, AWS, PHP, Python, React, Angular, jQuery, e mais um monte de coisa que nem existe mais 😀

andrewpacifico.com

Busca Binária e Sequencial:...

O que é versionamento...

O que é NPX...

Javascript filter(): Como Usar...