Listas ligadas
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.
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 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;
}
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.
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.
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.
Nós e ponteiros
Cada nó aponta para o próximo; insira/exclua reencadeando.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 5/5 · Moedas 400 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.