Lista Encadeada

Instruções

Implemente uma lista duplamente encadeada.

Assim como um array, uma lista encadeada é uma estrutura de dados linear simples. Vários tipos de dados comuns podem ser implementados usando listas encadeadas, como filas, pilhas e arrays associativos.

Uma lista encadeada é uma coleção de elementos de dados chamados nós. Em uma lista simplesmente encadeada, cada nó guarda um valor e um link para o próximo nó. Em uma lista duplamente encadeada, cada nó também guarda um link para o nó anterior.

Você vai escrever uma implementação de uma lista duplamente encadeada. Implemente um Node que guarde um valor e ponteiros para os nós seguinte e anterior. Depois, implemente uma List que guarde referências para o primeiro e o último nó e ofereça uma interface parecida com a de um array para adicionar e remover itens:

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

Para manter sua implementação simples, os testes não vão cobrir condições de erro. Especificamente: pop ou shift nunca serão chamados em uma lista vazia.

Leia mais sobre listas encadeadas na Wikipédia.