What is a Doubly Linked List?

Uma lista duplamente encadeada é uma sequência de nós onde cada nó carrega um valor e dois ponteiros: prev para o nó anterior, e next para o próximo nó. A lista em si mantém o controle de ambas as extremidades, a head (primeiro nó) e a tail (último nó).

Os dois ponteiros por nó e a referência extra tail nos trazem muitas vantagens. Adicionar ao final agora é O(1) (pula-se direto para a tail em vez de percorrer a corrente), e remover o último nó também é O(1) (porque podemos alcançar o penúltimo nó a partir de tail.prev). A contrapartida é mais memória por nó, além de mais ponteiros para manter sincronizados em cada inserção e remoção.

As cinco operações principais em uma lista duplamente encadeada são:

1. AddFirst: Adiciona um valor na frente da lista.
2. AddLast: Adiciona um valor ao final da lista (O(1)!).
3. Get: Retorna o valor em um determinado índice.
4. RemoveLast: Exclui o último nó (O(1)!).
5. Size: Retorna o número de nós armazenados atualmente.

Vamos criar uma classe Node primeiro, e depois construir a DoublyLinkedList sobre ela!