Listas enlazadas: la primera estructura de datos que se construye a mano, nodo a nodo,
con malloc. Dieciocho ejercicios que van del elemento suelto a listas ordenadas que se
fusionan sin duplicar memoria — y que introducen el puntero a puntero (t_list **) para
poder cambiar la cabeza desde dentro.
ft_list.h:
typedef struct s_list
{
struct s_list *next;
void *data;
} t_list;
Dos ideas clave. El nodo se apunta a sí mismo (struct s_list *next): esa
recursividad en el tipo es la que encadena la lista. Y void *data: un
puntero «a cualquier cosa», que permite que la misma lista guarde enteros, cadenas o structs. La lista
es genérica porque no sabe qué guarda.C 12 es el módulo de las listas enlazadas, y con ellas llegan palabras de estructuras de datos y de gestión de memoria. Aquí está cada una explicada desde cero y con un ejemplo sacado del propio módulo. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.
Una secuencia de elementos en la que cada uno sabe dónde está el siguiente. Al contrario que un array, los elementos no están seguidos en memoria: cada uno puede estar en cualquier sitio, y lo que los une es un puntero de uno al siguiente. Se llama simplemente enlazada cuando cada elemento solo apunta al siguiente (no al anterior), como la de C 12.
Una lista con "uno", "dos" y "tres" se dibuja así:
begin_list → [ "uno" | •]→[ "dos" | •]→[ "tres" | NULL]
Cada caja de la lista. En C 12 es un t_list con dos campos: data, lo que
guarda, y next, la dirección del nodo siguiente. El enunciado lo llama «elemento». Cada
nodo se crea con ft_create_elem, que es la única función del módulo que llama a
malloc (las demás que crean nodos tienen que usarla a ella).
Un struct que tiene un campo que apunta a otro struct de su mismo tipo:
struct s_list *next dentro de struct s_list. Es lo que permite encadenar.
Por eso dentro del struct se escribe struct s_list y no t_list:
el nombre corto del typedef todavía no existe en esa línea, porque el
typedef no termina hasta el t_list; del final. Y el campo tiene que ser un
puntero: un struct s_list next (sin *) contendría otro struct entero
dentro, que contendría otro, y no tendría tamaño finito.
void *: puntero genéricoUn puntero que guarda una dirección sin decir de qué tipo es lo que hay allí. Se puede asignar a y
desde cualquier otro puntero a datos sin conversión, pero no se puede desreferenciar directamente:
para leer lo que apunta hay que convertirlo primero, por ejemplo (char *)elem->data.
Es lo que hace genérica la lista: data puede apuntar a una cadena, a un
int o a un struct. La contrapartida es que la lista no sabe qué guarda, y por eso necesita
que le pasen cmp para comparar y free_fct para liberar.
->Acceso a un campo a través de un puntero. elem->next es una forma corta de escribir
(*elem).next: primero se sigue el puntero hasta el struct y luego se coge el campo. Con
un struct que no es puntero se usa el punto (elem.next).
Cuando hay doble puntero hacen falta paréntesis: (*begin_list)->data en ex12 y
ex16. Sin ellos, *begin_list->data se leería como *(begin_list->data),
porque -> va antes que *.
La cabeza es el primer nodo, y la variable que la apunta (begin_list) es la
única puerta de entrada a la lista: desde ahí se llega a todos los demás siguiendo
next. El final se marca con next == NULL.
Una lista vacía no es un nodo especial: es begin_list == NULL. Casi todos los
ejercicios tienen que funcionar con ella: ft_list_size devuelve 0, ft_list_at
devuelve NULL y ft_list_push_back tiene que convertir el nodo nuevo en la
cabeza.
Las variables locales de una función viven en la pila (stack) y desaparecen al
salir de ella. Lo que se reserva con malloc vive en el heap, que no se vacía solo:
sigue ahí hasta que se llama a free.
Por eso ft_create_elem tiene que usar malloc: si declarase un
t_list elem; local y devolviera &elem, el llamante recibiría la dirección
de algo que ya no existe.
malloc, free y sizeofmalloc(n) reserva n bytes y devuelve su dirección, o NULL si no puede.
free(p) devuelve al sistema lo que se reservó en p; después,
p sigue teniendo la misma dirección pero ya no se puede usar. sizeof(t_list)
es lo que mide un nodo: dos punteros, 16 bytes en los Linux de 64 bits de 42.
Cada malloc necesita exactamente un free: ninguno es una fuga y dos son un
double free, que puede romper el programa. El enunciado de C 12 avisa de que un segfault, un
bus error o un double free es un 0.
t_list **)En C los argumentos se pasan siempre por copia. Si una función recibe t_list *begin_list
y hace begin_list = elem, cambia su copia y el llamante no se entera. Para que pueda
cambiar la variable del llamante, hay que pasarle la dirección de esa variable: un
t_list **, y escribir a través de él con *begin_list = elem.
t_list *lista = NULL;
ft_list_push_front(&lista, "hola"); /* ahora lista apunta al nodo nuevo */
La regla para leer las firmas del módulo: recibe t_list ** la función que puede tener
que cambiar la cabeza (push_front, push_back, reverse,
remove_if, merge, sort, las sorted_), y
t_list * la que solo mira o cambia los data (size,
last, at, foreach, find,
clear, reverse_fun).
Usar memoria después de haberla liberado. Es un error grave porque a menudo parece que
funciona: la memoria liberada suele seguir conteniendo lo de antes un rato, hasta que otro
malloc la reutiliza y aparecen datos absurdos o un segfault lejos del fallo.
En listas sale al liberar: free(p); p = p->next; lee el campo next de un
nodo ya liberado. La solución de ex06 y ex12 es guardar el siguiente en tmp antes del
free.
Memoria reservada que ya nadie puede liberar porque se ha perdido su dirección. En un programa corto
no se nota, pero en uno que funciona mucho tiempo se va comiendo la memoria. valgrind
ejecuta el programa vigilando cada malloc y free y al final dice cuántos bytes
se quedaron sin liberar y dónde se reservaron.
En C 12 una fuga típica es desenganchar un nodo en ft_list_remove_if sin hacer
free del nodo, o hacer free del nodo pero no llamar a free_fct con
su data.
Para cada bloque reservado tiene que estar claro quién es su dueño, el responsable de
liberarlo. En C 12 hay dos dueños distintos: el nodo lo creó la lista (con ft_create_elem)
y lo libera la lista con free; el data lo trajo el llamante, y solo él sabe si
es memoria reservada, una cadena literal o un struct con más punteros dentro. Por eso se lo libera con
la función que él pasa, free_fct.
Ejemplo: en una lista hecha con ft_list_push_strs a partir de argv, los
data no se reservaron con malloc; un free_fct que no hace nada es
lo correcto, y uno que llame a free rompería el programa.
Visitar los nodos uno a uno desde la cabeza siguiendo next hasta llegar a
NULL. Es el bucle de casi todo el módulo:
while (p)
{
/* hacer algo con p->data */
p = p->next;
}
Si el bucle es while (p->next), se para en el último nodo en vez de después
(lo que quiere ft_list_last), pero entonces hay que comprobar antes que p no es
NULL.
O(1) es coste constante: lo mismo con 3 nodos que con un millón. O(n) es coste lineal: crece en proporción al número de nodos, porque hay que recorrerlos.
ft_list_push_front es O(1): crea un nodo y toca dos punteros. ft_list_push_back
es O(n), porque antes de enganchar tiene que ir hasta el último; lo mismo ft_list_size,
ft_list_last, ft_list_merge y ft_list_at.
En un array, tab[5] se calcula: la dirección del principio más 5 veces el tamaño de un
elemento, y se llega en un paso. En una lista no hay fórmula: los nodos están dispersos y solo se llega
al quinto pasando por los cuatro anteriores. El array tiene acceso directo; la lista,
secuencial.
A cambio, la lista gana al insertar o quitar en medio: basta con cambiar un next, sin
desplazar el resto como en un array. ft_list_reverse_fun paga ese precio: busca el nodo
de la derecha con un node_at en cada vuelta, así que en total recorre del orden de n²
nodos.
Una pila es una estructura en la que el último en entrar es el primero en salir (Last In, First Out), como una pila de platos. Una lista en la que siempre se inserta y se saca por la cabeza funciona así.
Por eso ft_list_push_strs invierte el orden: con {"uno", "dos", "tres"}
mete "uno" el primero y queda al fondo. Compilado y recorrido, sale
tres dos uno, que es justo lo que pide el enunciado («el primer elemento de la tabla se
encontrará al final de la lista»).
Una propiedad que el código se compromete a mantener cierta siempre, antes y después de cada operación. Sirve para razonar: si al entrar la lista está ordenada y la función conserva el orden, al salir sigue ordenada, sin tener que comprobarlo entero.
En C 12 hay dos: «un nodo nuevo tiene next a NULL» (ex00) y «la lista está
ordenada de forma creciente según cmp» (ex16 y ex17, que la reciben ordenada y tienen que
dejarla igual).
Se comparan dos vecinos y, si están al revés, se intercambian; se repite hasta que no quede ninguna pareja al revés. Hace del orden de n² comparaciones, así que es lenta con listas grandes, pero se adapta bien a una lista enlazada porque solo mira vecinos, que es lo único barato en una lista.
ft_list_sort la usa intercambiando los data y no los nodos, y tras cada
intercambio vuelve a la cabeza (cur = *begin_list), así que hace más vueltas que la
burbuja clásica.
Meter un elemento en una secuencia ya ordenada en el único sitio en que sigue ordenada: delante del primero que sea mayor que él. Repetido con cada elemento, es la ordenación por inserción.
Es ft_sorted_list_insert: avanza mientras el siguiente sea menor o igual
(cmp(cur->next->data, data) <= 0) y empalma ahí. Con ese <= 0, un
elemento igual a otros entra detrás de ellos.
Juntar dos secuencias ordenadas en una sola ordenada. La forma clásica va con un dedo en cada lista: compara los dos primeros, coge el menor, avanza ese dedo y repite. Así cada elemento se mira una vez y el coste es lineal, n + m. Es el paso central del merge sort.
ft_sorted_list_merge llega al mismo resultado de otra forma: inserta los nodos de
begin2 uno a uno con la lógica de ex16, buscando el hueco desde la cabeza cada vez. Es
correcto y no crea nodos, pero no aprovecha que begin2 ya viene ordenada: cuesta del orden
de n·m comparaciones en vez de n + m.
f, cmp y free_fctFunciones que la lista recibe como argumento para llamarlas ella (los punteros a función de C 11).
En C 12 hay tres papeles: f actúa sobre un data, cmp
compara dos (0 si «casan», con el convenio de signo de strcmp) y
free_fct destruye un data.
El enunciado dice cómo se llaman: (*cmp)(list_ptr->data, data_ref), con el dato de
la lista primero y la referencia después. Respetar ese orden importa cuando el comparador no es
simétrico. Sobre por qué algunos prototipos llevan int (*cmp)() con los paréntesis vacíos, ver
la entrada siguiente.
int (*cmp)() con los paréntesis vacíosEn ex11, ex12, ex14, ex16 y ex17 el enunciado declara int (*cmp)(), sin tipos dentro.
En el C de la piscine eso significa «puntero a función que devuelve int, con argumentos
sin especificar»: el compilador no comprueba qué le pasas. No es lo mismo que
(void), que significa «sin argumentos».
Por eso se le puede pasar ft_strcmp, que recibe char *, aunque la lista
le dé void *. Hay que copiar el prototipo tal cual lo da el enunciado, porque es con el
que compila la Moulinette.
Crear un nodo: reservar memoria, poner su data y dejar next a NULL.
elem = malloc(sizeof(t_list));
if (!elem)
return (NULL);
elem->data = data;
elem->next = NULL;
return (elem);
malloc): sobrevive a la función que lo crea, al revés que una
variable local. Dejar next a NULL no es un detalle: es la invariante
de que un nodo recién nacido no apunta a basura. Toda la piscina de listas se apoya en que esta
función sea impecable.Añadir un elemento al principio y actualizar la cabeza.
void ft_list_push_front(t_list **begin_list, void *data)
{
t_list *elem;
elem = ft_create_elem(data);
if (!elem)
return ;
elem->next = *begin_list;
*begin_list = elem;
}
t_list ** y es el
concepto más difícil del módulo. Para cambiar a dónde apunta la cabeza del llamante, no basta
con recibir la cabeza: hay que recibir la dirección de la variable cabeza. Con un solo
* cambiarías una copia y el llamante no se enteraría. El doble puntero es «pásame dónde
vive tu puntero para que yo lo reescriba».Contar los elementos.
size = 0;
while (begin_list)
{
size++;
begin_list = begin_list->next;
}
return (size);
p = p->next hasta caer en NULL. Como begin_list es una copia
local del puntero, puedes machacarla sin dañar la lista: mueves la vista, no los nodos. Ese
bucle while (p) es el for de las listas.Devolver el último nodo.
while (begin_list->next)
begin_list = begin_list->next;
return (begin_list);
next == NULL
(el último nodo) y parar en el nodo mismo == NULL (te has pasado). Aquí se para en
begin_list->next. Y el caso borde: una lista vacía no tiene último, hay que devolver
NULL sin desreferenciar. Este «buscar el final» es lo que hace lento el
push_back ingenuo.Añadir al final. Si la lista está vacía, el nuevo nodo pasa a ser la cabeza.
if (!*begin_list)
{
*begin_list = elem;
return ;
}
last = *begin_list;
while (last->next)
last = last->next;
last->next = elem;
last->next. Distinguir esos dos casos es el
ejercicio.Construir una lista con las cadenas de strs. El primer elemento de la tabla acaba al
final de la lista; se devuelve la cabeza.
i = 0;
while (i < size)
{
elem = ft_create_elem(strs[i]);
elem->next = list; /* push_front manual */
list = elem;
i++;
}
return (list);
strs[0] primero y queda al fondo; strs[size-1] entra el último y queda
en cabeza. Entender esa inversión es el ejercicio, y es la misma razón por la que una pila (LIFO)
devuelve las cosas del revés.Liberar todos los nodos y, con free_fct, también sus data.
while (begin_list)
{
tmp = begin_list->next;
free_fct(begin_list->data);
free(begin_list);
begin_list = tmp;
}
free(p); p = p->next;
lee memoria ya liberada (use-after-free). Por eso hay que guardar next en
tmp antes de liberar. Y la doble propiedad: el nodo lo liberas tú con
free, pero el data lo libera free_fct — porque quien creó el
dato sabe cómo destruirlo, y la lista no.Devolver el nodo n-ésimo (el primero es el 0), o NULL si no existe.
i = 0;
while (begin_list)
{
if (i == nbr)
return (begin_list);
i++;
begin_list = begin_list->next;
}
return (NULL);
tab[5]). Ese es el gran trade-off de las listas frente a los arrays: baratas
para insertar/borrar en cualquier punto, caras para acceder por índice.Invertir el orden de los nodos. Ojo: este ejercicio entrega solo el .c (usa el
ft_list.h del corrector).
prev = NULL;
cur = *begin_list;
while (cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
*begin_list = prev;
prev, cur, next) que da la vuelta a los enlaces sin perder el
resto de la lista. Si le das la vuelta a cur->next sin haber guardado antes
next, pierdes la cola. Es una de esas piezas que hay que dibujar en papel una vez y ya no
se olvida. Se hace en una pasada, O(n), sin memoria extra.Aplicar f al data de cada nodo, en orden.
while (begin_list)
{
f(begin_list->data);
begin_list = begin_list->next;
}
ft_foreach de C 11, pero sobre una
lista en vez de un array. Junta las dos ideas del bloque de C: puntero a función (el qué) y
recorrido de lista (el cómo). A partir de aquí, casi todo lo que queda es este bucle con una
condición o una acción distinta.Como foreach, pero solo aplica f donde cmp(data, data_ref)
devuelva 0.
while (begin_list)
{
if (cmp(begin_list->data, data_ref) == 0)
f(begin_list->data);
begin_list = begin_list->next;
}
cmp decide, f actúa. Y una función con cuatro parámetros, justo el máximo que
permite la Norma. Es filter + map combinados: recorre, filtra por comparación con una
referencia y transforma solo lo que pasa el filtro.Devolver el primer nodo cuyo data, comparado con data_ref, hace que
cmp devuelva 0.
while (begin_list)
{
if (cmp(begin_list->data, data_ref) == 0)
return (begin_list);
begin_list = begin_list->next;
}
return (NULL);
find localiza por igualdad exacta, por prefijo o por lo que quieras. Es el
find de cualquier librería, sobre tu propia estructura.Borrar todos los nodos que casen con data_ref según cmp, liberando su
data con free_fct.
/* 1) quitar los que casen mientras estén en la cabeza */
while (*begin_list && cmp((*begin_list)->data, data_ref) == 0)
{ ... free ... *begin_list = tmp; }
/* 2) recorrer el resto mirando cur->next */
while (cur && cur->next)
{
if (cmp(cur->next->data, data_ref) == 0)
{ tmp = cur->next; cur->next = tmp->next; free_fct(tmp->data); free(tmp); }
else
cur = cur->next;
}
*begin_list,
de ahí el doble puntero) y los del interior (se miran desde el nodo anterior, con
cur->next). Y no avanzar cuando borras, o te saltas el siguiente. Coordinar el
desenganche con el free sin dejar cabos sueltos es el examen.Pegar begin2 al final de begin1. Sin crear nodos.
if (!*begin_list1)
{
*begin_list1 = begin_list2;
return ;
}
last = *begin_list1;
while (last->next)
last = last->next;
last->next = begin_list2;
begin2 tal
cual, enganchando el next del último de begin1. Coste O(n) por buscar la
cola, pero cero memoria nueva.Ordenar la lista de forma creciente comparando con cmp.
if (cmp(cur->data, cur->next->data) > 0)
{
tmp = cur->data;
cur->data = cur->next->data;
cur->next->data = tmp;
cur = *begin_list; /* vuelve al principio tras cada cambio */
}
next), se intercambian los data. La lista física no
cambia; cambia qué guarda cada nodo. Es una ordenación por burbuja: correcta y fácil de razonar,
aunque O(n²). El comparador genérico ordena enteros, cadenas o lo que sea.Invertir la lista, pero recibiendo t_list * (un solo puntero, no doble).
while (i < n / 2)
{
right = node_at(begin_list, n - 1 - i);
tmp = left->data; /* intercambia extremos hacia el centro */
left->data = right->data;
right->data = tmp;
left = left->next;
i++;
}
t_list * (no **), no puede cambiar la cabeza del llamante.
Así que no vale reencadenar nodos (el primero pasaría a ser el último y el llamante se quedaría
apuntando al sitio equivocado); hay que invertir los data intercambiando extremos hacia el
centro. La forma de una función te dicta qué solución es legal.Insertar un nuevo elemento en su sitio de una lista ya ordenada, de modo que siga creciente.
if (!*begin_list || cmp((*begin_list)->data, data) > 0)
{ elem->next = *begin_list; *begin_list = elem; return ; }
cur = *begin_list;
while (cur->next && cmp(cur->next->data, data) <= 0)
cur = cur->next;
elem->next = cur->next;
cur->next = elem;
Fusionar begin2 (ordenada) dentro de begin1 (ordenada) manteniendo el orden
creciente.
while (begin_list2)
{
next2 = begin_list2->next; /* guarda antes de mover el nodo */
ins_sorted(begin_list1, begin_list2, cmp);
begin_list2 = next2;
}
begin2 uno a
uno en su sitio. Hay que guardar next2 antes de reengancharlo, porque al insertarlo su
next se sobrescribe. Esta fusión de dos listas ordenadas es, en esencia, el corazón del
merge sort.Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado. Están agrupadas en: punteros, memoria, casos límite y entrega. Antes de mirar la respuesta, intenta contestar tú. Pide papel: en listas casi todo se explica mejor dibujando cajas y flechas.
ft_list_push_front recibe t_list ** y ft_list_size no?Porque push_front cambia la cabeza del llamante, y para escribir en una variable ajena
hace falta su dirección. size solo lee, y puede avanzar su copia del puntero sin dañar
nada. → doble puntero, ex01
ft_list_reverse_fun intercambia los data en vez de darle la vuelta a los enlaces?Porque recibe t_list *: si se reencadenaran los nodos, la cabeza pasaría a ser el
último y el llamante seguiría apuntando al nodo viejo, con una lista de un solo elemento. Moviendo los
data, los nodos no se mueven y la cabeza sigue siendo la misma. → ex15
ft_list_reverse con una lista de tres.Con uno → dos → tres: en cada vuelta se guarda next, se hace que el nodo
actual apunte a prev y se avanzan los dos. Tras tres vueltas, prev es
tres y se escribe en *begin_list; recorrida, sale tres dos uno
(comprobado compilando el fragmento). → ex08
ft_list_clear, ¿por qué el tmp?Porque después de free(begin_list) ya no se puede leer begin_list->next:
sería un use-after-free. Se guarda el siguiente antes y se avanza con él. → use-after-free,
ex06
free_fct? ¿No bastaría con free(data)?No, porque la lista no sabe qué es data: puede no venir de malloc (una
cadena de argv) o ser un struct con más memoria dentro. Lo libera quien sabe cómo, y la
lista solo libera sus nodos. Si no se llamara a free_fct, cada data reservado
sería una fuga. → propiedad de la memoria
malloc?ft_create_elem devuelve NULL y push_front lo comprueba y no
toca la lista. Punto débil: el fragmento de ft_list_push_strs hace
elem->next = list sin mirar si elem es NULL, y ahí sería un
segfault. → ex05, malloc y free
ft_list_merge, ¿cuántos malloc haces?Ninguno: el enunciado prohíbe crear elementos. Se engancha la segunda lista entera al
next del último nodo de la primera. Y si la primera está vacía, la segunda pasa a ser la
cabeza. → ex13
size devuelve 0, at y find devuelven NULL,
push_back y merge ponen el nodo o la lista como cabeza. ft_list_last
tiene que devolver NULL antes del bucle: el fragmento de la página empieza directamente
con while (begin_list->next), que con NULL es un segfault, así que esa
comprobación tiene que estar en tu versión. → lista vacía, ex03
ft_list_remove_if, ¿por qué dos bucles y por qué no avanzas al borrar?El primero quita los nodos que casan mientras estén en la cabeza, porque eso cambia
*begin_list. El segundo mira siempre cur->next, para poder enganchar el
anterior con el siguiente; si avanzara tras borrar, se saltaría el nodo que acaba de subir. Con
x a x x b x y referencia "x" queda a b (comprobado).
→ ex12
ft_list.h y por qué ex08 no lo entrega?El t_list tal cual lo da el enunciado y los prototipos que uses, como el de
ft_create_elem, que a partir de ex01 lo pone la Moulinette (no lo entregas tú). En ex08 el
enunciado dice que se usa su propio ft_list.h, así que solo se entrega el .c.
→ ex08, struct autorreferente
malloc en push_back o push_strs?No: allí la única función autorizada es ft_create_elem. Usar otra es trampa y es un
−42. malloc solo aparece en ex00, y free en ex06 y ex12. → ex04