Diferença entre lista vinculada simples e lista vinculada dupla

Lista vinculada única vs lista vinculada dupla

Lista vinculada é uma estrutura de dados linear 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 ao vincular esses elementos como links em uma cadeia. Uma lista vinculada 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 na qual cada nó contém uma referência ao próximo nó e ao nó anterior.

Lista vinculada individualmente

Cada elemento em uma lista vinculada individualmente possui dois campos, como mostrado na Figura 1. O campo de dados mantém os dados reais armazenados e o próximo campo manté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 mostra uma lista vinculada individualmente com três elementos. Cada elemento armazena seus dados e todos os elementos, exceto o último, uma referência ao próximo elemento. O último elemento mantém um valor nulo em seu próximo campo. Qualquer elemento da lista pode ser acessado iniciando 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 possui três campos, como mostrado na Figura 3. Semelhante à lista isolada, o campo de dados mantém os dados reais armazenados e o próximo campo mantém a referência ao próximo elemento na cadeia. Além disso, o campo anterior manté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 aos elementos primeiro e anterior. O último elemento da lista mantém um valor nulo em seu próximo campo e o primeiro elemento da lista manté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 a lista vinculada simples e a lista vinculada dupla?

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 o elemento anterior na lista. Listas duplamente vinculadas requerem 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 duplamente as listas de links permitem uma manipulação mais fácil, pois permitem percorrer a lista nas direções para frente e para trás.