Listas encadenadas
Nodos unidos por punteros
- Una lista enlazada es una cadena de pequeñas estructuras llamadas nodos, dispersos en el heap.
- Cada nodo contiene un valor y un puntero al siguiente nodo. Siga los punteros para recorrer la lista.
- A diferencia de un array, una lista puede crecer un nodo a la vez sin mover los demás.
Estructura autorreferencial
- Un nodo es una estructura que contiene un puntero a su propio tipo:
struct Node { int data; struct Node *next; };—dataes el valor,nextapunta al siguiente nodo.- Esto se le proporciona como
Nodeen cada plantilla inicial. Elnextdel último nodo esNULL.
head y el final NULL
- Un único puntero, el head (cabeza), apunta al primer nodo. Desde allí se acciona al resto.
- El último nodo apunta a
NULL, lo cual marca el final de la lista. - Una lista vacía es simplemente
head == NULL— no hay ningún nodo.
#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;
}
Añadir un nodo al principio
- Para añadir al principio, cree un nuevo nodo, apunte su
nextal head anterior y devuelva el nuevo nodo como el nuevo head. - Esto es rápido — no toca ningún otro nodo.
- Dado que el head cambia, la función devuelve el nuevo head, y el llamador lo guarda.
Errores comunes
- Nunca pierda el puntero
head, de lo contrario toda la lista será inaccesible. - Libere todos los nodos; el último nodo apunta a
NULL.
Ahora tú prueban
- Recorra una lista con un puntero
curycur = cur->next, deteniéndose enNULL. - Los nuevos nodos provienen de
malloc(sizeof(Node)); el verificador libera la lista. No escriba unmain.
Nodos y punteros
Each node points to the next; insert/delete by re-linking.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
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 no write a main.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
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 no write a main.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 5/5 · 400 monedas + un pequeño bono en el primer intento de hoy
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 no write a main.
Haz clic en Ejecutar para ver la salida aquí.