lista enlazada añadir a la cola, confusión

Question

Visual Studio 2008 C

Lo que no puedo entender acerca de esta lista enlazada es la adición a la cola en la parte else de la sentencia if.

Cuando se asignan la cabeza y las colas, la dirección de la memoria de node_temp tanto para la cola como para la cabeza apuntan a la misma ubicación de memoria.

Sin embargo, en la parte de más es la cabeza, de hecho, todavía apunta a la cola. ¿Hay algo que no puedo explicar y no entiendo sobre la parte else?

Espero que alguien pueda explicarme mejor.

static struct convert_temp 
{ 
    size_t cel; 
    size_t fah; 
    struct convert_temp *next; 
} *head = NULL, *tail = NULL; 

/** Add the new converted temperatures on the list */ 
void add(size_t cel, size_t fah) 
{ 
    struct convert_temp *node_temp = NULL; /* contain temp data */ 

    node_temp = malloc(sizeof(*node_temp)); 

    if(node_temp == NULL) 
    { 
     fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]\n", 
      __FUNCTION__, __LINE__); 
     exit(0); 
    } 

    /* Assign data */ 
    node_temp->cel = cel; 
    node_temp->fah = fah; 
    node_temp->next = NULL; 

    if(head == NULL) 
    { 
     /* The list is at the beginning */ 
     head = node_temp; /* Head is the first node = same node */ 
     tail = node_temp; /* Tail is also the last node = same node */ 
    } 
    else 
    { 
     /* Append to the tail */ 
     tail->next = node_temp; 
     /* Point the tail at the end */ 
     tail = node_temp; 
    } 
} 

Answer 1

La primera vez que agrega un elemento (llamémoslo A) a la lista, head es nulo y pasa por la parte if. Eso significa que tanto head como la cola se configuran para que apunten a A al agregar ese primer elemento.

Ahora agreguemos otro elemento B. Esta vez, head no es nulo por lo que pasa a través de la parte else, configurando tail para apuntar a B pero dejando head apuntando a A.

Esto es como se esperaba, ahora tiene head señalando A, A señalando B, B apuntando a nada (nulo) y tail señalando B.

Démoslo paso por paso.

Initial state: head -+-> null 
         | 
       tail -+ 

Insert item A: head -+-> A ---> null 
         | 
       tail -+ 

Insert item B: head ---> A -+-> B ---> null 
          | 
       tail --------+ 

Insert item C: head ---> A ---> B -+-> C ---> null 
            | 
       tail ---------------+ 

Se puede ver en cada etapa (que no sea el inicial) que la cola actual se establece para que apunte al nuevo nodo (que ya apunta a NULL para su siguiente nodo), el puntero de cola se actualiza a punto al nuevo último nodo.

De hecho, vamos a ir a través de la adición de C en aun más detalle (línea por línea) para que pueda ver lo que cada línea de código está haciendo (he cambiado el nombre node_temp-node sólo para ayudar con el formato) :

Starting state:    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node = malloc(sizeof(*node)); node ---> C ----------> ? 
(allocate node C)    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node->next = NULL;    node ---> C --------+ 
(ignore payload cel/fah       | 
    for now since it's not  head ---> A -+-> B -+-> null 
    relevant to the list     | 
       structure)  tail --------+ 

tail->next = node;    node ---------------+ 
(first in else clause)       | 
           head ---> A -+-> B -+-> C ---> null 
              | 
           tail --------+ 

tail = node;     node ---------------+ 
(second in else clause)       | 
           head ---> A ---> B -+-> C ---> null 
                | 
           tail ---------------+ 

Entonces, finalmente, desaparece node ya que es una variable local y tiene su estado final:

       head ---> A ---> B -+-> C ---> NULL 
                | 
           tail ---------------+ 

La ventaja de mantener unaEl punteroen una lista con un solo enlace es evitar tener que recorrer toda la lista para encontrar el final cuando intentes agregar un elemento hasta el final.

Recorrer toda la lista hace que la inserción al final sea una operación de tiempo O(n) (el tiempo empleado depende del número de elementos en la lista). El uso del puntero tail hace que sea una operación de tiempo O(1) (la misma cantidad de tiempo, independientemente del tamaño de la lista).

Como acotación al margen, una lista doblemente enlazada tiene un uso adicional para un puntero tail - se da la posibilidad de iniciar rápidamente un recorrido desde el final de la lista para el inicio, usando tail y los prev punteros en lugar de head y los punteros next.

Answer 2

La parte else simplemente actualiza la tail de la lista, puesto que la cabeza no cambia cuando se adiciona una lista enlazada.

Es una optimización para mantener un puntero al elemento de la cola amortiguado, por lo que no tiene que pasar por la lista completa del encabezado en cada anexo.

Answer 3

No es que la cabeza siga apuntando a la cola. La cabeza apunta hacia anterior cola. Cuando la lista contenía solo un elemento, era a la vez cabeza y cola. Cuando se agregó un nuevo nodo, se actualizó el puntero de cola. El puntero de la cabeza aún apunta al primer nodo, que es correcto.

Answer 4

En la primera llamada agregar, la cabeza y la cola apuntarán a un bloque de memoria recién creado. Todas las llamadas posteriores a agregar caerán a la parte else, que solo cambiará el puntero de cola, básicamente modificando el antiguo tail-> next para señalar el nuevo bloque de memoria, y luego actualizar tail para señalar también este nuevo bloque de memoria .

Es una forma eficiente de agregar. Si solo se usara head, cada vez que agregara un nuevo node_temp, tendría que recorrer todos los siguientes punteros comenzando desde la cabeza hasta llegar al node_temp previamente agregado (cuyo próximo puntero sería NULL), y luego agregar el nuevo nodo . Esto sería entonces un algoritmo O (n), en lugar del O (1) anterior.