What is a Linked List?

Uma lista encadeada é uma sequência de valores onde cada valor vive em seu próprio nó, e cada nó contém um ponteiro para o próximo nó. A lista conhece seu primeiro nó (a cabeça ou head); a partir daí, você alcança todos os outros nós seguindo a cadeia de ponteiros next.

Ao contrário de um array, uma lista encadeada não precisa de um único bloco contíguo de memória. Adicionar um item na cabeça é O(1): basta criar um novo nó e apontá-lo para a cabeça atual. A desvantagem é que alcançar o n-ésimo item é O(n), porque temos que percorrer a cadeia um nó por vez.

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

1. AddFirst: Adiciona um valor na frente da lista.
2. AddLast: Adiciona um valor no final da lista.
3. Get: Retorna o valor em um determinado índice.
4. Remove: Exclui o valor em um determinado índice.
5. Size: Retorna o número de valores armazenados atualmente.

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