Lista Encadeada

Ao utilizar vetores e pilhas até o momento, tem-se feito uso de armazenamento sequencial, cuja principal desvantagem é quantidade fixa que se reserva para seu uso, ao delimitar sua área permite-se a possibilidade de estouro, ou manter ocupado todo um bloco de memória quando em alguns momentos pode estar usando uma quantidade menor ou mesmo nenhum dado.

                Numa representação sequencial temos um item q[x] e implicitamente sabemos que o próximo elemento será q[x+1], para tornar explicita essa relação, o item irá ter dois campos, primeiro com a informação e o segundo com o endereço para o item seguinte, assim temos a estrutura de dados conhecida como lista encadeada, aonde cada item será chamada de nó.

                Com nó tendo um campo informação com o real elemento da lista e o campo endereço contendo um ponteiro para o próximo elemento, a lista encadeada é acessada a partir de um ponteiro externo (não incluído dentro do nó) lista que aponta para o primeiro nó da lista, o campo endereço para o ultimo nó irá ter o valor nulo, sendo invalido e indicando o final de uma lista.

info

next

info

next

info

next

info

next

lista

>

>

>

>

nulo

nó

nó

nó

nó

Por ser tratar de uma estrutura de dados dinâmica, o numero de nós na lista pode variar consideravelmente à medida que são inseridos e removidos. Basicamente existem duas maneiras de construir uma lista encadeada. A primeira consiste em adicionar o novo item sempre no inicio ou fim da lista. A outra é acrescentar itens em posições especificas da lista, podendo seguir a ordem crescente por exemplo.

A forma de armazenar os dados da lista dependerá do aplicativo, com três situações que podem ocorrer quando se insere um item na lista encadeada, como reflexo da inserção, quando se remove um item na lista encadeada, as três sequencias de operação se invertem:

                INSERIR

1.        Item pode se tornar o primeiro da lista;

info

next

info

next

Info

next

lista

>

>

nulo

·         Novo item copia o endereço de próximo que está em Lista.

·         Lista aponta para o novo item.

info

next

lista

>

>

info

next

info

next

>

nulo

2.       Inserir entre dois outros itens;

info

next

info

next

Info

next

lista

>

>

nulo

·         Novo item copia o endereço de próximo que está no item anterior.

·         Item anterior atualiza o endereço para o novo item.

info

next

>

info

next

info

next

lista

>

>

nulo

3.       Ser o ultimo item da lista;

info

next

Info

next

info

next

lista

>

>

nulo

·         Troca o Nulo pelo endereço do novo item no ultimo item da lista.

·         Indicar Nulo para o endereço de próximo no novo item.

info

next

info

next

info

next

lista

>

>

>

nulo

EXCLUIR

1.       Excluir o primeiro da lista

info

next

Info

next

info

next

lista

>

>

>

nulo

·         Copia o endereço de próximo no primeiro item para lista

Info

next

info

next

lista

>

>

nulo

2.       Elimina numa posição intermediaria

info

next

Info

next

info

next

lista

>

>

>

nulo

·         Copia no item anterior ao que vai ser excluído o endereço de próximo.

info

next

info

next

lista

>

>

nulo

3.       Excluir o ultimo item

info

next

info

next

info

next

lista

>

>

>

nulo

·         Troca o endereço que aponta para o item a ser excluído por nulo

info

next

info

next

lista

>

>

nulo

Um modelo simples e didático de código em linguagem C para uma lista encadeada está incluído na próxima postagem “Exemplo de lista encadeada” e serve como complemento prático mostrando a programação completa das rotinas para inserir, excluir e percorrer.