Estruturas de Dados Intermediário/Lista encadeada

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

Lista encadeada simples

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

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

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

Lista encadeada simples

 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
 }