[C] Listas enlazadas utilizando arreglos

[MAFUS]

La premisa para que funcione la función es que la lista siempre debe estar terminada con NULL. Si está vacía debe estar apuntando a NULL.

La función pondrá el nodo generado con el dato al final de la lista. Siguiendo la primera premisa éste último nodo debe apuntar a NULL en next.

Lo que se hace es:
Se genera un nodo a partir de la información dada por data.

Si la lista está vacía, NULL, pasará a apuntar al nodo nuevo.
Si la lista no está vacía hay que recorrerla hasta encontrar el último elemento (aquel que apunte a NULL), cambiar el valor next para que apunte al nuevo nodo generado y regresar la lista entera, eso es el primer elemento (list).

Lo que ves en

Código (c) [Seleccionar] Expandir


while (slist_next(node) != slist_nil()) {
    node = slist_next(node);
es precisamente ese recorrido. node apunta al principio de la lista (list) y vamos a trabajar sobre node. Mientras el elemento next de node no sea NULL, node apuntará a node->next (en el código esto está encapsulado por node = slist_next(node). Una vez llegado a éste último elemento la orden list_next(node) = newNode; coloca el nuevo nodo al final de la lista.
Como el inicio de la lista no ha sido modificado (list) y hay que regresar un puntero, precisamente al inicio de la lista, devolvemos list.

Otra versión sin estas macros es así:

Código (c) [Seleccionar] Expandir


SList slist_append(SList list, int data) {
    Slist node;
    SList newNode = malloc(sizeof(SNode));
   
    newNode->data = data;
    newNode->next = NULL;

    if(list == NULL)
        return newNode;

    node = list;

    while(node->next != NULL)
        node = node->next;

    node->next = newNode;

    return list;
}

[GGZ]

Me explicaste todo lo que yo ya sabía, se como trabaja la función se lo que hace, pero no entiendo como la enlaza o sea como relaciona list con node, eso es lo que no entiendo.

O sea como que yo modifico node y también se modifica list si nunca lo relacioné sólo dije node = list (pero acá no estoy cambiando ningún valor de list) y nada más.


ENTIENDO TODO LO QUE HACE LA FUNCIÓN, LO QUE NO ENTIENDO ES PORQUE RETORNA LIST SI NUNCA LO TOCA SI NUNCA LO MODIFICA A LIST, NUNCA DICE "EL SIGUIENTE ELEMENTO DE LIST APUNTA AL NODE"

[MAFUS]

A ver si me se explicar ahora:
node es una variable puntero auxiliar. Su única función es, junto al while, encontrar el último nodo de la lista.
La variable list no se toca, es el inicio de la lista, lo que hay que regresar. Pero la lista sí que se ha modificado, ha crecido en un elemento.

node = list; es porqué la lista es un dato dinámico y no sabemos que extensión tiene pero sabemos que list, al menos, tiene un nodo válido y que ése es el primero; por tanto hay que empezar a buscar el último nodo de la lista por el primero y recorrerla hasta llegar al final.

A ver si me salen los dibujitos esquemáticos:

Código [Seleccionar] Expandir



XXXXXXXXX <- Esto es nuestra lista

y como toda lista enlazada tiene un puntero apuntando a su cabeza

list
v
XXXXXXXXX



Y <- elemento nuevo que se debe colocar a la lista

como list no se puede tocar, que es lo que hay que regresar nos inventamos node

list
v
XXXXXXXXX      <- esto es node = list
^
node


Y <- por simplicidad lo dejaré perdido por el limbo hasta que lo coloque

ahora node debe encontrar el último elemento

list
v
XXXXXXXXX
^
node

list
v
XXXXXXXXX
 ^
 node

list
v
XXXXXXXXX
  ^
  node

...

list
v
XXXXXXXXX
       ^
       node

Ahora el next de node, que es exactamente lo mismo al next del último elemento enlaza a Y y virtualmente obtenemos lo siguiente

list
v
XXXXXXXXXY


node, ya no me sirve y lo dejo tranquilo. Desaparecerá cuándo desaparezca la función ya que es una variable local.

La lista se queda ya que es algo que hay en el motón y por tanto permanente.

Debo retornar list porqué apunta a la lista modificada.

Ahora me puedes decir: pero si list tiene la misma posición de memoria al principio de la función que al final, no se ha modificado en nada el valor que guarda, no hace falta devolverla.

Y te digo: sí que hace falta porqué también sirve la función para generar la lista desde cero. Si se le pasa list=NULL a la función ocurre lo siguiente:

Código [Seleccionar] Expandir



list
v
NULL

genero un dato

list
v
NULL

X <- el dato

y enlazo list con el dato

list
v
X



Ahora si no devuelvo list fuera de la función no existiría esta modificación.

[GGZ]

Lo que yo no entiendo es este paso:

Código [Seleccionar] Expandir


list
v
XXXXXXXXX
       ^
       node

Ahora el next de node, que es exactamente lo mismo al next del último elemento enlaza a Y y virtualmente obtenemos lo siguiente

list
v
XXXXXXXXXY

Ya sé que el next de node es el ÚLTIMO elemento ya sé eso, pero no sé como lo enlaza capaz no entendí bien la definición de las estructuras o sea yo tenía entendido que se debe poner CUAL ES EL SIGUIENTE elemento.

Es decir uno define node y busca hasta el último elemento y luego lo enlaza con newNode PERFECTO! ESO SE ENTIENDE.

La pregunta es: ¿cuando enlaza list con node? capaz hay algo de la defición que no entiendo

O sea para mi falta un list->next=node; ¿me entendés?
Así como hace node->next=newNode;

¿Por qué no hace falta enlazar de algún modo list con node? yo lo estoy pensando mal y lo sé pero es por alguna estructura o algo que no entendí

[MAFUS]

No se puede hacer list->next = node porqué node es solo un puntero y no tiene dato.
En la práctica es esto:

Código (c) [Seleccionar] Expandir


int* pint = malloc((sizeof(int));
int* node;

node = pint;



Cuándo haces node = list ya creas la relación. node es list.

[GGZ]

AAahhh ¡Claro! que tonto, ahora si entendí
Eso era todo lo que quería que me digas no que me expliques el código entero  


Muchas gracias!

[MAFUS]

Perfecto