Algoritmos e Estruturas de Dados/Lista encadeada

Origem: Wikilivros, livros abertos por um mundo aberto.
Diagrama conceitual de uma lista ligada.

Lista ligada ou Lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por uma sequência de nodos ou células que contém seus dados e também uma ou duas referências ("links") que apontam para o nodo anterior ou posterior. Há diversos modelos de lista ligadas como lista-encadeada simples, listas duplamente ligadas e listas encadeadas circulares.

Para se "ter" uma lista ligada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula. O esquema a seguir representa uma lista ligada com 5 elementos:

Célula 1 ---> Célula 2 ---> Célula 3 ---> Célula 4 ---> Célula 5 ---> (Nulo)

Para manipularmos estas listas nomeadamente: inserir dados ou remover dados temos que ter sempre em atenção em ter um ponteiro que aponte para o 1º elemento e outro que aponte para o fim, isto porque se queremos inserir ou apagar dados que estão no inicio ou no fim da lista então a operação é rapidamente executada caso seja um nó que esteja no meio da lista pois terá que haver uma procura até encontrar a posição desejada.

Tipos de listas encadeadas[editar | editar código-fonte]

Lista encadeada simples[editar | editar código-fonte]

Uma lista encadeada simples é aquela que contém apenas um link por nodo. Este link aponta para o próximo nodo da lista, ou para um valor nulo (vazio) quando se trata do nodo final.


Lista encadeada simples com três valores inteiros.

Lista duplamente encadeadas[editar | editar código-fonte]

Listas duplamente encadeadas ou lista de duas vias, são um modelo mais sofisticado das listas simples: cada nodo possui dois ponteiros - um que aponta para o nodo anterior (ou null se é o primeiro valor ou a lista está vazia) e outro que aponta para o próximo nodo (ou null se é o último nodo ou a lista está vazia).


Um exemplo de uma lista duplamente encadeada

Listas encadeadas circulares[editar | editar código-fonte]

Na lista encadeada circular, o primeiro e o último nodo são ligados entre si. Nas listas circulares simples, há apenas um link que aponta para o próximo nodo; enquanto nas listas circulares duplas há dois links em cada nodo que apontam para o elemento anterior e para o posterior.


Um exemplo de uma lista circular simples

Pseudo-código de listas encadeadas[editar | editar código-fonte]

Lista encadeada simples[editar | editar código-fonte]

 record Node {
    data // O dado a ser armazenado no nodo
    next // Referência ao próximo nodo; null se for o último nodo
 }
 record List {
     Node firstNode   // ponteiro para o primeiro nodo da lista; null para uma lista   
     vazia
 }

Atravessar uma lista simples é fácil iniciando pelo primeiro nodo e seguindo cada next até o fim.

 node := list.firstNode
 while node not null {
     node := node.next
 }