Lista vinculada individualmente x lista duplamente vinculada
A lista vinculada é uma estrutura de dados linear usada para armazenar uma coleção de dados. Uma lista encadeada aloca memória para seus elementos separadamente em seu próprio bloco de memória e a estrutura geral é obtida ligando esses elementos como elos em uma cadeia. Uma lista unida individualmente é composta de uma sequência de nós e cada nó tem uma referência ao próximo nó na sequência. Uma lista duplamente vinculada contém uma sequência de nós em que cada nó contém uma referência ao próximo nó, bem como ao nó anterior.
Lista vinculada individualmente
Cada elemento em uma lista vinculada individualmente tem dois campos, conforme 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 descreve uma lista unida com três elementos. Cada elemento armazena seus dados e todos os elementos, exceto o último, armazenam uma referência ao próximo elemento. O último elemento contém um valor nulo em seu próximo campo. Qualquer elemento da lista pode ser acessado começando no cabeçalho e seguindo o próximo ponteiro até encontrar o elemento necessário.
Lista duplamente vinculada
Cada elemento em uma lista duplamente vinculada tem três campos, conforme mostrado na Figura 3. Semelhante à lista vinculada individualmente, 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. 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 mostra uma lista duplamente vinculada com três elementos. Todos os elementos intermediários armazenam referências ao primeiro e aos elementos anteriores. O último elemento na lista contém um valor nulo em seu próximo campo e o primeiro elemento na lista contém um valor nulo em seu campo anterior. A lista duplamente vinculada pode ser percorrida para 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 na lista vinculada individualmente contém uma referência ao próximo elemento na lista, enquanto cada elemento na lista duplamente vinculada contém referências ao próximo elemento, bem como ao elemento anterior na lista. Listas duplamente vinculadas requerem mais espaço para cada elemento na lista e operações elementares, como inserção e exclusão, são mais complexas, pois precisam lidar com duas referências. Mas as listas duplamente de links permitem uma manipulação mais fácil, pois permitem percorrer a lista nas direções para frente e para trás.
