Listas ligadas
Nodes unidos por links
- Uma linked list é uma cadeia de nodes.
- Cada node guarda um pedaço de data e um link para o próximo node.
- O último node liga-se a
None, que marca o fim.
Um node é um pequeno registro
- Podemos armazenar um node em um dicionário:
{"data": ..., "next": ...}. "data"guarda o valor;"next"guarda o próximo node (ouNone).- O primeiro node é chamado de head da lista.
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
Percorrer a lista
- Comece no head e siga cada link
"next". - Pare quando chegar em
None. - Essa visita de cada node é chamada de traversal.
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
Por que uma linked list?
- Você pode inserir ou remover um node alterando links — sem mover itens.
- Um array teria que mover todos os itens após a alteração.
- Mas uma linked list não tem índice: para alcançar o item 5 você deve caminhar desde o head.
Em pseudocódigo do Cambridge
- O exame armazena nodes em um array;
NextIndexé o índice do próximo node, eNULLmarca o fim.
TYPE Node
DECLARE Data : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].NextIndex
ENDWHILE
Erros comuns
- Nunca perca o ponteiro
head, ou toda a lista torna-se inacessível. - O último node aponta para
None.
Agora você tenta
- Um node é um dict
{"data": ..., "next": ...}. Siga"next"para percorrer a cadeia. - Clique em Check answer para testar seu código.
Nodes linked by pointers
Each node points to the next; you insert/delete by re-linking.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Build a linked list 1 → 2 → 3 using dictionaries. Make the three nodes, link each to the next, and point head at the first one. The last node's "next" must be None.
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60).
Clique em Executar para ver a saída aqui.
Dificuldade 4/5 · Moedas 280 + pequeno bônus na primeira conclusão hoje
Write length(head) that decrescentes how many nodes are in the linked list. An empty list (head é None) has length 0.
Clique em Executar para ver a saída aqui.