Conforme o prometido no artigo Listas Simplesmente Ligadas e Exemplo de Implementação em C da passada edição, aqui está o artigo das listas duplamente ligadas. Uma vez que este se engloba num mesmo tema, certos aspectos podem tornar-se um pouco repetitivos, isto porque a única diferença no nó entre os dois tipos de listas referidos é um apontador adicional nas segundas.

Para começar, vamos estudar as vantagens das listas duplamente face às simplesmente ligadas. Se bem se lembram uma lista simplesmente é possível percorre-la apenas num sentido. Nas que vamos ver de seguida é possível percorrê-las em ambos os sentidos e é essa a principal diferença entre o modo de funcionamento das segundas. Esta diferença é muito vantajosa. Imaginemos que estamos no nó número 1000 e queríamos imprimir o conteúdo do nó 999, com as listas simplesmente ligadas teríamos de voltar à cabeça da lista e percorrer os 999 nós até chegarmos ao pretendido, com as listas duplamente ligadas basta andar uma posição para trás.

O que muda na estrutura de cada nó relativamente às simplesmente ligadas, como já foi referido, é apenas a adição de um novo apontador, o qual irá apontar para o elemento da posição imediatamente anterior da lista.

Já que estamos a falar de apontadores convém alertar para uma situação muito específica desta estrutura de dados. Vamos focar-nos na primeira posição da lista. Se todas as posições têm um apontador para os elementos anterior e posterior, como será que definimos o apontador para elemento anterior ao da cabeça?

O que será isto das listas? Uma lista é uma estrutura de dados sequencial que resolve o típico problema dos arrays. E qual é o problema do arrays (vectores) poderá pensar o leitor? Se pensarmos mais concretamente na linguagem C, o que precisamos para definir um array? O tipo de dados e o número de elementos que iremos ter! E no início da implementação de um programa, definir o número de elementos que o array poderá ter pode ser problemático. Ou porque não sabemos em definitivo quantos elementos vai ter o array ou porque depois poderemos querer adicionar ou remover elementos.

Mantendo sempre o nosso pensamento na linguagem C, temos uma forma de aumentar ou diminuir o número de elementos de um array usando a função realloc disponível na biblioteca stdlib.h, mas o que esta função faz na prática é realocar todos os elementos novamente, ou seja, se pensarmos no caso em que só queremos adicionar um elemento, e se o nosso array tiver vários elementos, realocar toda a memória novamente é um desperdício de recursos computacionais, recursos estes que poderíamos estar a utilizar noutra operação do nosso programa.

Para além do problema da realocação de memória ainda existe o facto de, na linguagem C, os elementos dos arrays serem alocados de forma sequencial, ou seja, se o array for grande só o conseguimos alocar havendo quantidade suficiente de memória contígua livre. Contudo, no caso das listas os elementos são alocados dinamicamente, não sendo preciso existir grandes quantidades de memória contígua.