Linked lists · Listas ligadas
Nodes joined by links
- A linked list is a chain of nodes.
- Each node holds a piece of data and a link to the next node.
- The last node links to
None, which marks the end.
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.
A node is a small record
- We can store one node in a dictionary:
{"data": ..., "next": ...}. "data"holds the value;"next"holds the next node (orNone).- The first node is called the head of the list.
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"])
Walk the list
- Start at the head and follow each
"next"link. - Stop when you reach
None. - This visiting of every node is called traversal.
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"]
Why a linked list?
- You can insert or remove a node by changing links — no shifting of items.
- An array would have to move every item after the change.
- But a linked list has no index: to reach item 5 you must walk from the head.
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.
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
Em pseudocódigo do Cambridge
- O exame armazena nodes em um array;
Nexté o índice do próximo node, eNULLmarca o fim.
TYPE Node
DECLARE Data : INTEGER
DECLARE Next : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].Next
ENDWHILE
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - The last node points to
None.
Erros comuns
- Nunca perca o ponteiro
head, ou toda a lista torna-se inacessível. - O último node aponta para
None.
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
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 · Nós ligados por ponteiros
Each node points to the next; you insert/delete by re-linking. · Cada nó aponta para o próximo; você insere/exclui relinkando.
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. · Construa uma lista ligada 1 → 2 → 3 usando dicionários. Crie os três nós, ligue cada um ao próximo, e aponte head para o primeiro. O "next" do último nó deve ser None.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · Percorra a lista ligada começando em head e some o "data" de cada nó. Armazene o total em total (a resposta é 60).
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write length(head) that returns · decrescentes how many nodes are in the linked list. An empty list (head is None) has length 0. · Escreva length(head) que retorna quantos nós estão na lista ligada. Uma lista vazia (head é None) tem comprimento 0.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.