Punteros y listas enlazadas

Recientemente, en una entrada anterior, usamos listas enlazadas para animar un sistema de partículas. Aunque la implementación en Javascript en esa entrada funciona correctamente, existen formas de mejorarla.

En esta entrada hablaré sobre listas enlazadas y su implementación en C. La inspiración para este post es un video en Computerphile con el Profesor Braisfold. Usando bloques de Lego el profesor logra comunicar de manera simple las ideas detrás de esto.

Esta entrada abordará las mismas ideas, enfocándonos más en el código que en las analogías.

Un nodo

Una lista consta de una serie de nodos enlazados por medio de punteros. El primer paso para entenderlas es empezar por uno de sus componentes.

typedef struct _nodo
{
    char *palabra;
    struct _nodo *siguiente;
} Nodo;

Esto combina dos conceptos de C:

  • Las estructuras, que se declaran con la palabra struct seguida del nombre que le daremos. Las estructuras agrupan varios tipos de variables primitivas.

  • Declaración de tipo, que usa la palabra typedef y al final de la llave una palabra clave que lo identificará. Esto nos permite declarar nuevos tipos de variables.

Nótese que la estructura nodo contiene un puntero de tipo char, que nos permite guardar palabras; y un puntero de tipo nodo, que nos permite apuntar hacia el siguiente nodo en la lista.

Ahora necesitamos una forma de crear nodos. Como haremos esto frecuentemente lo mejor es poner el código en una función.

Nodo *crear_nodo(char *texto)
{
    Nodo *nodo = NULL;
    nodo = (Nodo *)malloc(sizeof(Nodo));
    nodo->palabra = texto;
    nodo->siguiente = NULL;
    return nodo;
}

Analicemos paso a paso la función:

  • La declaración indica que esta función regresa un puntero de tipo Nodo.

  • La primera línea crea un puntero de tipo Nodo que no apunta a ningún lado, por eso tiene el valor NULL. Algunos programadores recomiendan establecer el valor de nuevos punteros explícitamente a NULL.

  • Enseguida reservamos memoria para el nuevo nodo. Esta linea tiene dos partes principales. La instrucción malloc que reserva memoria del tamaño indiciado en su parámetro y regresa un puntero que apunta hacia ese registro creado en la memoria. Luego la expresión entre paréntesis convierte el puntero en un puntero de tipo Nodo (esto se conoce como pointer casting).

  • Las expresiones nodo->texto y nodo->palabra asignan los valores correspondientes dentro de la estructura. La notación con flechas se usa para asignación en punteros de estructuras. Para manipular estructuras directamente se usa un punto.

  • Finalmente return nodo termina la ejecución del código en la función y regresa el valor de nodo.

Y bueno, así es C, control preciso a cambio de una sintaxis rebuscada.

Ahora vamos a probar nuestro generador de nodos en el programa principal:

int main(void)
{
    Nodo *cabeza = NULL;
    cabeza = crear_nodo("nariz");
    printf("La palabra es: %s \n", cabeza->palabra);

    return 0;
}

Por supuesto la salida al compilar y ejecutar el programa es la siguiente:

La palabra es: nariz

Enlazando nodos

Ahora que podemos crear nodos, vamos conectarlos para crear una lista enlazada. Haremos esto directamente en nuestra función principal:

cabeza->siguiente = crear_nodo("papel");
cabeza->siguiente->siguiente = crear_nodo("pie");

Agregamos dos nodos adicionales. La lista completa queda identificada por el nodo que está a la cabeza.

Ahora bien, hay que imprimir la lista completa, y hacerlo usando un montón de flechas para acceder a cada nodo no es la forma más eficiente. Así que vamos a escribir una función para imprimir todas las palabras en la lista:

void imprimir_lista(Nodo *lista)
{
    Nodo *temporal = NULL;
    temporal = lista;
    while (temporal)
    {
        printf("elemento: %s \n", temporal->palabra);
        temporal = temporal->siguiente;
    }
}

La única parte interesante aquí es el puntero temporal que nos permite recorrer cada elemento de la lista. La asignación temporal = temporal->siguiente asigna al elemento temporal el siguiente en la lista, hasta que se encuentra con NULL.

Si lo usamos en nuestra función principal:

imprimir_lista(cabeza);

Obtenemos la salida de texto esperada.

elemento: nariz
elemento: papel
elemento: pie

Insertar elementos usando punteros dobles

Ahora solo nos resta encontrar una mejor forma de insertar nuevos elementos en la lista, que no sea esa seguidilla de flechas apuntando hacia el siguiente elemento.

Vamos a ser un poco ambiciosos. Nuestro objetivo es que cada que insertemos un nuevo elemento este se ubique correctamente en orden alfabético. Estas son la cosas a considerar:

  • Si insertamos un nuevo elemento al inicio debemos asegurarnos que el puntero cabeza apunta a la dirección de memoria correcta.

  • Al insertar un elemento entre dos existentes hay que asegurarnos que todo se actualice correctamente. Debemos desconectar los nodos y reconectarlos asegurándonos de que los campos siguiente de cada uno apuntan a donde deben apuntar. Esto además requiere un puntero temporal auxiliar.

  • Hay que asegurarnos de que nos detendremos al encontrar el puntero NULL.

  • Al insertar elementos al final de la lista debemos tener en cuenta que el campo siguiente del último elemento es un puntero nulo.

Y por supuesto hay que encontrar una forma de determinar si una palabra va después de otra alfabéticamente. Esta parte fácil porque existe una función en la librería string que hace eso.

Tratar de implementar las consideraciones listadas requiere crear una función específica para cada caso.

Pero existe un truco súper fácil de implementar usando un puntero que apunta a un puntero. Éste es el código:

void insertar_elemento(Nodo **lista, Nodo *nuevo)
{
    Nodo **rastreador = lista;

    while ((*rastreador != NULL) &&
            strcmp((*rastreador)->palabra, nuevo->palabra) < 1)
    {
        rastreador = &(*rastreador)->siguiente;
    }
    nuevo->siguiente = *rastreador;
    *rastreador = nuevo;
}

Luego lo usamos en la función principal.

int main(void)
{
    Nodo *cabeza = NULL;
    cabeza = crear_nodo("nariz");
    insertar_elemento(&cabeza, crear_nodo("papel"));
    insertar_elemento(&cabeza, crear_nodo("zapato"));
    insertar_elemento(&cabeza, crear_nodo("elefante"));
    insertar_elemento(&cabeza, crear_nodo("pie"));

    imprimir_lista(cabeza);

    return 0;
}

Y el resultado es el siguiente:

elemento: elefante
elemento: nariz
elemento: papel
elemento: pie
elemento: zapato

Cómo funciona

Aunque la implementación es simple, el entender la función insertar_elemento no lo es tanto. Vamos a analizarla con cuidado.

  • La función toma dos parámetros: un puntero hacia un puntero de tipo Nodo, y un puntero de tipo Nodo. El usar un puntero hacia un puntero, o una referencia doble, parece extraño pero es justo esto lo que simplifica el código.

  • La línea Nodo **rastreador = lista crea un puntero que apunta hacia el puntero del inicio de la lista. Esto es importante, este puntero apunta hacia la dirección de memoria que contiene los registros donde encontraremos cada nodo.

  • El bucle while verifica que no hayamos llegado al final de la lista o sobrepasado la siguiente palabra en orden alfabético. El rastreador actualiza su valor apuntando al siguiente registro de memoria en la lista en cada paso, tal como lo hace el puntero en la función imprimir_lista.

  • La penúltima línea de la función garantiza que el campo siguiente del nodo que vamos a insertar apunta hacia el elemento correcto.

  • La última línea actualiza el valor del puntero rastreador, que previamente apuntaba al elemento inmediatamente siguiente al nodo que insertaremos. Esto garantiza que el puntero inmediatamente anterior actualiza correctamente su campo next.

Para entender claramente la función hay que entender correctamente qué hace un puntero doble. La primera vez que se encuentra uno esta sintaxis puede tomar un buen rato comprender lo que está pasando. Mi única recomendación es releer el código y tratar con diferente ejemplos, hasta que estés seguro de que entiendes cómo funciona.

A continuación puedes ver el código completo de lo que discutimos en este post:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct _nodo
{
    char *palabra;
    struct _nodo *siguiente;
} Nodo;

Nodo *crear_nodo(char *texto)
{
    Nodo *nodo = NULL;
    nodo = (Nodo *)malloc(sizeof(Nodo));
    nodo->palabra = texto;
    nodo->siguiente = NULL;
    return nodo;
}

void imprimir_lista(Nodo *lista)
{
    Nodo *temporal = NULL;
    temporal = lista;
    while (temporal)
    {
        printf("elemento: %s \n", temporal->palabra);
        temporal = temporal->siguiente;
    }
}

void insertar_elemento(Nodo **lista, Nodo *nuevo)
{
    Nodo **rastreador = lista;

    while ((*rastreador != NULL) &&
            strcmp((*rastreador)->palabra, nuevo->palabra) < 1)
    {
        rastreador = &(*rastreador)->siguiente;
    }
    nuevo->siguiente = *rastreador;
    *rastreador = nuevo;
}

int main(void)
{
    Nodo *cabeza = NULL;
    cabeza = crear_nodo("nariz");
    insertar_elemento(&cabeza, crear_nodo("papel"));
    insertar_elemento(&cabeza, crear_nodo("zapato"));
    insertar_elemento(&cabeza, crear_nodo("elefante"));
    insertar_elemento(&cabeza, crear_nodo("pie"));

    imprimir_lista(cabeza);

    return 0;
}

Referencias adicionales

Además del video referido al inicio existe un segundo video en el que el Profesor Brailsford explica punteros dobles. Y un video adicional en el que muestra la implementación.