1. Los nodos no son listas.
He visto en StackOverflow en Español varias veces esta confusión, y me resulta muy curioso que tantos usuarios cometan ese error.
Tienes una estructura de datos llamada nodo
que almacena un puntero al siguiente elemento y un dato, lo primero que haces con ella es declarar un alias diciendo que un puntero a nodo
es una lista
. Y eso es tan erróneo como decir que un escalón es una escalera, sinceramente ¿Te parecen lo mismo?:
Organizar las estructuras de datos de esta manera y poner nombres que no las describen adecuadamente es confuso y propenso a errores como has podido ver.
2. El alias oculta el tipo subyacente.
Normalmente cuando en C++ definimos una variable de tipo puntero, le añadimos el asterisco:
tipo_de_datos *puntero;
// ~ <--- ¡Esto es un puntero!
Pero podemos ocultar el puntero en un alias:
typedef tipo_de_datos * otro_tipo;
otro_tipo dato;
// ~~~~ <--- Aunque sea puntero, ¡no lo sabemos de un vistazo!
Debido a este uso del alias, no es evidente que lista
sea un puntero y acabas declarado un puntero que no apunta a nada:
int main()
{
lista mi_lista; // 'lista' es un puntero (nodo *) ¡aunque no lo parezca!
insertar(mi_lista, 42);
std::cout << mi_lista->dato;
return 0;
}
En la llamada a insertar
se usa el puntero (con el operador flecha ->
) y como no apunta a nada obtienes el error de fallo en la memoria (Segmentation fault
):
void insertar(lista l, int dato)
{
nodo *n = new nodo;
n->siguiente = NULL;
n->dato = dato;
l->siguiente = &n; // l es un puntero, pero no apunta a nada ¡Segmentation fault!
}
Propuesta.
Empecemos por resolver el primer punto: las listas y los nodos son cosas diferentes, así que crearemos un objeto lista:
struct lista
{
void insertar(int dato);
private:
struct nodo
{
int dato = 0;
nodo *siguiente = nullptr;
};
nodo *inicio = nullptr;
nodo *fin = inicio;
};
Si te fijas, el nodo
es ahora un sub-objeto de lista
que está en la zona privada de dicho objeto, de esta manera seguimos los principios de encapsulamiento. También hemos añadido inicializadores a todos los miembros para que tengan información controlada en el momento de crearse; por último, el usar dos punteros (uno para el inicio de la lista y otro para el final) nos ayuda a ahorrar trabajo a la hora de insertar datos.
La implementación corregida de insertar
quedaría así:
void lista::insertar(int dato)
{
if (fin)
{
fin->siguiente = new nodo{dato};
fin = fin->siguiente;
}
else
{
inicio = fin = new nodo{dato};
}
}