The (Duel)lists cómo usar las Linked Lists en C

Si alguien habla mal de las Linked Lists lo reto a un duelo. Sí, lo haré igual que Harvey Keitel en una de las obras maestras de Ridley Scott. Tener cuidado.

¿Qué decías de las Linked Lists?

Por aquí ya habíamos abordado (indirectamente) el tema de las Linked Lists, en un post prehistórico sobre la malloc(): tendríais que ir a releerlo, pero, si realmente no tenéis ganas de hacerlo, os resumo una parte:

"Para aquellos que nunca la han utilizado, las linked list no son una frivolidad: son una de las herramientas más poderosas de la programación en general (y del C en particular). Los que trabajan intensamente en proyectos grandes y profesional, más pronto o más tarde, acabaran por usarlas: una razón más, por lo tanto, para familiarizarse con la asignación de memoria dinámica."

Premisa: si alguien no tiene la más mínima idea de lo que una lista enlazada le aconsejo la lectura (antes de continuar) de una de las muchas descripciones (algunas realmente buenas) que se encuentran en la red. Esta, por ejemplo. Para este nuevo post he decidido retomar el código que había escrito para el viejo y simplificarlo/mejorarlo de manera de obtener:

1. condensar en una sola función las dos que en el viejo código creaban un nuevo nodo en la lista (¡simplificar!).
2. añadir una función que permite colgar un nuevo nodo en lugar de ponerlo en la cabezas de la lista (¡mejorar!).

¡Vamos con el codigo!

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

// nodo de una linked list con campo datos
typedef struct snode {
    int data;
    struct snode *next;
} node_t;

// alloc en la cabeza de una lista un node con datos y un pointer al próximo elemento
void addNode(
    node_t **head,
    int    data)
{
    // alloc de un nuevo node
    node_t *node = malloc(sizeof(node_t));
    node->data = data;
    node->next = *head;

    // asigna head lista al nuevo node
    *head = node;
}

// alloc al final de una lista un node con datos y un pointer al próximo elemento
void appendNode(
    node_t **head,
    int    data)
{
    // alloc un nuevo node
    node_t *node = malloc(sizeof(node_t));
    node->data = data;
    node->next = NULL;

    // append el nuevo node
    node_t *current = *head;
    if (current == NULL) {
        // caso especial para lista vacia: asigna head lista al nuevo node
        *head = node;
    }
    else {
        // recurre la lista para encontrar el ultimo node
        while (current->next != NULL)
            current = current->next;

        // asigna al ultimo node el nuevo node
        current->next = node;
    }
}

// main() para test
void main()
{
    int i;

    // init lista vacia 1 y inserta con addNode() 3 nodes con data = índice loop
    node_t *head1 = NULL;
    for (i = 1; i <= 3; i++)
        addNode(&head1, i);

    // recurre la lista y enseña los valores
    node_t *myhead1 = head1;
    printf("myhead1=%p - metodo ADD\n", myhead1);
    while (myhead1) {
        printf("data=%d (myhead1=%p next=%p)\n", myhead1->data, myhead1, myhead1->next);
        myhead1 = myhead1->next ;
    }

    // init lista vacia 2 y inserta con addNode() 3 nodes con data = índice loop
    node_t *head2 = NULL;
    for (i = 1; i <= 3; i++)
        appendNode(&head2, i);

    // recurre la lista y enseña los valores
    node_t *myhead2 = head2;
    printf("myhead2=%p - metodo APPEND\n", myhead2);
    while (myhead2) {
        printf("data=%d (myhead2=%p next=%p)\n", myhead2->data, myhead2, myhead2->next);
        myhead2 = myhead2->next ;
    }
}

Como se puede ver es bastante simple y conciso, y, como siempre, el código es auto-explicativo, ampliamente comentado y los comentarios hablan por sí mismos.

En el main() he añadido un poco de trazas de log, que nos ayudan, mientras se ejecuta, a entender lo que ocurre cuando añadimos un nodo y cuando, en alternativa, lo colgamos. El resultado final es el mismo (en el ejemplo se muestra una lista con tres nodos), pero el diseño cambia: en el caso append tenemos una disposicion más lógica de nodos: la lista crece hacia adelante, y cada nuevo nodo es el último. En el caso insert, sin embargo, es la cabeza de la lista que cambia en cada inserción, y enyonces, cuando leemos los datos, los encontramos invertidos respeto  la orden de inserción.

Ambas listas tienen usos válidos (por ejemplo una es mejor para crear colas FIFO y la otra es mejor para crear colas LIFO), y, para aplicaciones más sofisticadas, donde se necesita añadir/leer/borrar nodos en posiciones determinadas se puede decidir (casi) sin distinción por una estructura o la otra. Normalmente yo uso el método de append, que me parece más lógico, aunque, lo admito, la función de append es un poco más complicada y menos inmediata. Pero la lista ordenada hacia adelante me parece más consistente y fácil de manejar.

Después de todo el programa nos enseña este log:

myhead1=0x11b5050 - metodo ADD
data=3 (myhead1=0x11b5050 next=0x11b5030)
data=2 (myhead1=0x11b5030 next=0x11b5010)
data=1 (myhead1=0x11b5010 next=(nil))
myhead2=0x11b5070 - metodo APPEND
data=1 (myhead2=0x11b5070 next=0x11b5090)
data=2 (myhead2=0x11b5090 next=0x11b50b0)
data=3 (myhead2=0x11b50b0 next=(nil))

que creo que es inútil explicar (¡habla por sí mismo!). Acabo con una ultima consideración: evidentemente lo que se ha enseñado es solo un programa de test: en una aplicación real habrá que añadir unas cuantas funciones accesorias para buscar y borrar nodos, etc. Y, visto che usamos unas malloc(), habrá que acordarse de usar las correspondientes free()...

Bueno, os deseo un buen trabajo con las Linked Lists, las cuales, sin duda, os darán unas satisfacciones. Y si no las dan, paciencia: si estos fuesen los problemas de la vida...

¡Hasta el próximo post!