Algoritmos e Estruturas de Dados/Lista encadeada
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
editarLista encadeada simples
editarUma 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
editarListas 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
editarNa 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
editarLista encadeada simples
editarrecord 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 }