Lección 9 · 9 de 20

Una lista enlazada · C

Programe en C una lista enlazada de tareas: nodos en el montón, añadir al final y al principio, borrar por id y liberar la lista entera.

C · Una lista enlazada en DMarlon Studio: el código del ejemplo y su salida en la terminal

Una lista enlazada es una cadena de nodos: cada Task guarda sus datos y un puntero next al siguiente, y el último tiene next a NULL. A diferencia de un array, añadir o quitar en medio no obliga a mover nada: basta con cambiar un puntero.

new_task reserva un nodo con malloc, lo rellena y lo enlaza delante de next. Con NULL crea un nodo suelto; con la lista actual, como en todo = new_task(4, "Server", todo), lo pone al principio, que es la operación más rápida de una lista.

append y remove_id usan un puntero a puntero, Task **link. Empieza apuntando a todo y, en cada paso, pasa a apuntar al campo next del nodo actual. Así no hay caso especial para el primer nodo: cuando el bucle para, *link es justo el puntero que hay que cambiar, sea la cabeza o el next de otro nodo.

Para borrar, remove_id guarda el nodo en gone, hace que *link salte a gone->next y libera gone. En la salida, la tarea 2 desaparece y las demás siguen enlazadas.

Al final, el bucle while libera la lista entera: guarda next antes del free, porque después de liberar un nodo ya no se puede leer su campo next.

Código · main.c

#include <stdio.h>#include <stdlib.h>typedef struct Task { int id; const char *title; struct Task *next; } Task;// A new node on the heap, linked in front of `next` (NULL: the end).Task *new_task(int id, const char *title, Task *next) {    Task *t = malloc(sizeof *t);    if (!t) exit(EXIT_FAILURE);    t->id = id; t->title = title; t->next = next;    return t;}// Task **link points at the pointer we may change: head or some ->next.void append(Task **link, Task *t) {    while (*link) link = &(*link)->next;    *link = t;}void remove_id(Task **link, int id) {    while (*link && (*link)->id != id) link = &(*link)->next;    if (*link) { Task *gone = *link; *link = gone->next; free(gone); }}void print(const char *label, const Task *t) {    for (printf("%-9s", label); t; t = t->next) printf(" [%d %s]", t->id, t->title);    printf("\n");}int main(void) {    Task *todo = NULL;  // an empty list    append(&todo, new_task(1, "Invoice", NULL)); append(&todo, new_task(2, "Call Ana", NULL));    append(&todo, new_task(3, "Backup", NULL));  print("Start:", todo);    remove_id(&todo, 2);                         print("Done 2:", todo);    todo = new_task(4, "Server", todo);          print("Urgent:", todo);    while (todo) { Task *next = todo->next; free(todo); todo = next; }  // free all    return 0;}

Salida · cc main.c -o main && ./main

Start:    [1 Invoice] [2 Call Ana] [3 Backup]
Done 2:   [1 Invoice] [3 Backup]
Urgent:   [4 Server] [1 Invoice] [3 Backup]

Para recordar

Cada nodo apunta al siguiente; el último, a NULL.
Insertar al principio no recorre nada.
Con Task **link se modifica la cabeza o cualquier next sin casos especiales.
Al liberar, guarde next antes de free.

Ejercicio

Escriba int count(const Task *t) y Task *find(Task *t, int id), y use find para cambiar el título de la tarea 3 a "Backup NAS".