Diferença entre a lista única e a lista vinculada dupla

Lista única vinculada versus Lista vinculada dupla

A lista vinculada é uma estrutura de dados linear que é usada para armazenar uma coleção de dados. Uma lista vinculada aloca memória para seus elementos separadamente em seu próprio bloco de memória e a estrutura geral é obtida ligando esses elementos como links em uma cadeia. Uma lista unicamente ligada é composta por uma seqüência de nós e cada nó tem uma referência ao próximo nó na seqüência. Uma lista duplamente vinculada contém uma seqüência de nós em que cada nó contém uma referência ao próximo nó, bem como ao nó anterior.

Lista individualmente vinculada

Cada elemento em uma lista unicamente vinculada possui dois campos como mostrado na Figura 1. O campo de dados contém os dados reais armazenados e o próximo campo contém a referência ao próximo elemento na cadeia. O primeiro elemento da lista vinculada é armazenado como o cabeçalho da lista vinculada.

A Figura 2 representa uma lista unicamente vinculada com três elementos. Cada elemento armazena seus dados e todos os elementos, exceto a última loja, uma referência ao próximo elemento. O último elemento possui um valor nulo no próximo campo. Qualquer elemento na lista pode ser acessado começando na cabeça e seguindo o próximo ponteiro até encontrar o elemento necessário.

Lista dupla vinculada

Cada elemento em uma lista duplamente vinculada possui três campos como mostrado na Figura 3. Semelhante à lista vinculada separadamente, o campo de dados contém os dados reais armazenados e o campo seguinte contém a referência ao próximo elemento na cadeia. Além disso, o campo anterior contém a referência ao elemento anterior na cadeia. O primeiro elemento da lista vinculada é armazenado como o cabeçalho da lista vinculada.

A Figura 4 representa uma lista duplamente vinculada com três elementos. Todos os elementos intermediários armazenam referências aos elementos anteriores e anteriores. O último elemento na lista mantém um valor nulo no próximo campo e o primeiro elemento na lista possui um valor nulo no campo anterior. A lista vinculada de forma dupla pode ser percorrida para a frente seguindo as próximas referências em cada elemento e, da mesma forma, pode ser percorrida para trás usando as referências anteriores em cada elemento.

Qual a diferença entre Singly Linked List e Doubly Linked List?

Cada elemento da lista unicamente vinculada contém uma referência ao próximo elemento da lista, enquanto cada elemento na lista duplamente vinculada contém referências ao próximo elemento, bem como o elemento anterior na lista. As listas duplamente vinculadas exigem mais espaço para cada elemento na lista e operações elementares, como inserção e exclusão, são mais complexas, uma vez que têm que lidar com duas referências. Mas as listas duplas de links permitem uma manipulação mais fácil, pois permite percorrer a lista em direções para frente e para trás.