Aula 10: Listas encadeadas
Imagine uma caça ao tesouro: cada bilhete guarda um valor e uma pista para o próximo bilhete, e para chegar ao quinto é preciso ir um de cada vez. Isso é uma 'lista encadeada' — uma cadeia de 'nós'. A vantagem: inserir ou remover no meio é O(1), você só redireciona uma pista. A desvantagem: chegar a
Uma lista encadeada é como uma caça ao tesouro: cada bilhete guarda um valor e uma pista de para onde ir depois. Para chegar ao quinto bilhete, você precisa seguir as pistas uma a uma — não dá para pular direto para o meio como em um array, onde você pode alcançar qualquer lugar de uma vez.
- classe
- Um molde para uma caixinha com campos. class Node define uma caixa com dois campos: val (o valor) e next (um ponteiro para o próximo nó). Node(1) cria uma caixa dessas, e self simplesmente significa "esta caixa".
- lista encadeada
- Uma estrutura de dados de nós, cada um guardando um valor e um ponteiro next para o nó seguinte; inserção/remoção O(1) ao lado de um nó conhecido, mas acesso por posição O(n).
- nó
- A peça fundamental de uma lista encadeada: um pequeno objeto que guarda um valor (val) e um ponteiro (next) para o próximo nó, ou None no final.
- localidade de cache
- O quão próximos na memória estão dados que são usados juntos; um array contíguo é amigável ao cache, enquanto nós de lista encadeada espalhados são menos.
