Linked lists · Listas ligadas
Nodes joined by pointers
- A linked list is a chain of small structs called nodes, scattered around the heap.
- Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
- Unlike an array, a list can grow one node at a time without moving the others.
Nós conectados por ponteiros
- Uma linked list é uma cadeia de pequenas structs chamadas nós, espalhadas pelo heap.
- Cada nó segura um valor e um ponteiro para o próximo nó. Siga os ponteiros para percorrer a lista.
- Diferente de um array, uma lista pode crescer um nó de cada vez sem mover os outros.
A self-referential struct
- A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; };—datais the value,nextpoints to the following node.- This is given for you as
Nodein each starter. The last node'snextisNULL.
Uma struct autorreferencial
- Um nó é uma struct que contém um ponteiro para seu próprio tipo:
struct Node { int data; struct Node *next; };—dataé o valor,nextaponta para o nó seguinte.- Isso é dado para você como
Nodeem cada starter. Onextdo último nó éNULL.
head and the NULL end
- A single pointer, the head, points to the first node. From there you reach the rest.
- The very last node points to
NULL, which marks the end of the list. - An empty list is just
head == NULL— there are no nodes at all.
head e o fim NULL
- Um único ponteiro, o head, aponta para o primeiro nó. Daí você alcança o resto.
- O muito último nó aponta para
NULL, que marca o fim da lista. - Uma lista vazia é apenas
head == NULL— não há nós de todo.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
Adding a node at the front
- To add to the front, make a new node, point its
nextat the old head, and return the new node as the new head. - This is fast — it does not touch any other node.
- Because the head changes, the function returns the new head, and the caller saves it.
Adicionar um nó na frente
- Para adicionar na frente, crie um novo nó, aponte seu
nextpara o head antigo, e retorne o novo nó como o novo head. - Isso é rápido — não toca em nenhum outro nó.
- Como o head muda, a função retorna o novo head, e o caller o salva.
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
Erros comuns
- Nunca perca o ponteiro
head, ou toda a lista torna-se inacessível. - Libere todos os nós; o último nó aponta para
NULL.
Now you try
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - New nodes come from
malloc(sizeof(Node)); the checker frees the list. Do not write amain.
Agora você tenta
- Percorra uma lista com um ponteiro
curecur = cur->next, parando emNULL. - Novos nós vêm de
malloc(sizeof(Node)); ochecker libera a lista. Não escreva ummain.
Nodes and pointers · Nós e ponteiros
Each node points to the next; insert/delete by re-linking. · Cada nó aponta para o próximo; insira/exclua reencadeando.
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not · não write a main. · Complete int length(const Node *head) para contar os nós na lista (0 para uma lista vazia). Percorra com ->next até NULL. O tipo Node é fornecido. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not · não write a main. · Complete int sum_list(const Node *head) para retornar o total de cada data de todos os nós (0 para uma lista vazia). O tipo Node é fornecido. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not · não write a main. · Complete Node *push_front(Node *head, int value) para criar um novo nó (com malloc), apontar seu next para o antigo head e retorná-lo como o novo cabeçalho. O verificador libera a lista. Não escreva um main.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.