Lista ligada

Instruções

Implementa uma lista duplamente ligada.

Tal como um array, uma lista ligada é uma estrutura de dados linear simples. Vários tipos de dados comuns podem ser implementados com listas ligadas, como filas, pilhas e arrays associativos.

Uma lista ligada é uma coleção de elementos de dados chamados nós. Numa lista simplesmente ligada, cada nó tem um valor e uma ligação para o nó seguinte. Numa lista duplamente ligada, cada nó tem também uma ligação para o nó anterior.

Vais escrever uma implementação de uma lista duplamente ligada. Implementa um Node para guardar um valor e ponteiros para o nó seguinte e para o nó anterior. Depois implementa uma List que guarda referências ao primeiro e ao último nó e oferece uma interface semelhante a um array para adicionar e remover itens:

• push (insere um valor no fim);
• pop (remove um valor no fim);
• shift (remove um valor no início).
• unshift (insere um valor no início);

Para manteres a tua implementação simples, os testes não vão cobrir condições de erro. Em concreto: nunca vais chamar pop ou shift numa lista vazia.

Lê mais sobre listas ligadas na Wikipédia.