Lista Ligada Simples vs Lista Ligada Duplamente
Lista encadeada é uma estrutura de dados linear que é 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 encadeada simples é composta por uma sequência de nós e cada nó tem uma referência ao próximo nó na sequência. Uma lista duplamente encadeada 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 Simples
Cada elemento em uma lista encadeada simples 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 encadeada é armazenado como o cabeçalho da lista encadeada.
A Figura 2 mostra uma lista encadeada 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 Ligada
Cada elemento em uma lista duplamente encadeada possui 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 encadeada é armazenado como o cabeçalho da lista encadeada.
A Figura 4 mostra uma lista duplamente ligada com três elementos. Todos os elementos intermediários armazenam referências ao primeiro e aos elementos anteriores. O último elemento da lista contém um valor nulo em seu próximo campo e o primeiro elemento da lista contém um valor nulo em seu campo anterior. A lista duplamente encadeada 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 Lista Ligada Simples e Lista Ligada Duplamente?
Cada elemento na lista vinculada simples 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 ao elemento anterior na lista. Listas duplamente vinculadas exigem mais espaço para cada elemento da 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 de links duplos permitem uma manipulação mais fácil, pois permitem percorrer a lista nas direções para frente e para trás.
