Lista enlazada de encabezado en C

Requisito previo : lista enlazada , lista enlazada circular

Un Node de encabezado es un Node especial que se encuentra al principio de la lista. Una lista que contiene este tipo de Node se denomina lista enlazada por encabezado. Este tipo de lista es útil cuando se necesita información diferente a la que se encuentra en cada Node.
Por ejemplo , supongamos que hay una aplicación en la que a menudo se calcula el número de elementos de una lista. Por lo general, siempre se recorre una lista para encontrar la longitud de la lista. Sin embargo, si la longitud actual se mantiene en un Node de encabezado adicional, esa información se puede obtener fácilmente.

Tipos de lista enlazada de encabezado

Grounded Header Linked List
Es una lista cuyo último Node contiene el puntero NULL . En la lista enlazada de encabezado, el puntero de inicio siempre apunta al Node de encabezado. start -> next = NULL indica que la lista enlazada del encabezado conectado a tierra está vacía . Las operaciones que son posibles en este tipo de lista enlazada son Inserción, Eliminación y Recorrido .

Lista enlazada de encabezado circular
Una lista en la que el último Node apunta al Node de encabezado se denomina lista enlazada circular. Las strings no indican el primer o el último Node. En este caso, los punteros externos proporcionan un marco de referencia porque el último Node de una lista enlazada circular no contiene el puntero NULL . Las operaciones posibles sobre este tipo de lista enlazada son Inserción, Eliminación y Recorrido .

// C program for a Header Linked List
#include <malloc.h>
#include <stdio.h>
  
// Structure of the list
struct link {
    int info;
    struct link* next;
};
  
// Empty List
struct link* start = NULL;
  
// Function to create a header linked list
struct link* create_header_list(int data)
{
  
    // Create a new node
    struct link *new_node, *node;
    new_node = (struct link*)
        malloc(sizeof(struct link));
    new_node->info = data;
    new_node->next = NULL;
  
    // If it is the first node
    if (start == NULL) {
  
        // Initialize the start
        start = (struct link*)
            malloc(sizeof(struct link));
        start->next = new_node;
    }
    else {
  
        // Insert the node in the end
        node = start;
        while (node->next != NULL) {
            node = node->next;
        }
        node->next = new_node;
    }
    return start;
}
  
// Function to display the
// header linked list
struct link* display()
{
    struct link* node;
    node = start;
    node = node->next;
    while (node != NULL) {
        printf("%d ", node->info);
        node = node->next;
    }
    printf("\n");
    return start;
}
  
// Driver code
int main()
{
  
    // Create the list
    create_header_list(11);
    create_header_list(12);
    create_header_list(13);
  
    // Print the list
    display();
    create_header_list(14);
    create_header_list(15);
  
    // Print the list
    display();
  
    return 0;
}

Producción:

11 12 13 
11 12 13 14 15

Aplicaciones de
polinomios de lista enlazada de cabecera

Las listas enlazadas de cabecera se utilizan con frecuencia para mantener los polinomios en la memoria. El Node de cabecera se utiliza para representar el polinomio cero .
Supongamos que tenemos
F(x) = 5x ⁵ – 3x ³ + 2x ² + x ¹ +10x ⁰
Del polinomio representado por F(x) es claro que este polinomio tiene dos partes, coeficiente y exponente , donde x es un parámetro formal . Por tanto, podemos decir que un polinomio es una suma de términos, cada uno de los cuales consta de un coeficiente y un exponente.
La implementación por computadora requiere implementar polinomios como una lista de pares de coeficiente y exponente . Cada uno de estos pares constituirá una estructura, por lo que un polinomio se representará como una lista de estructuras.
Si uno quiere representar F(x) con la ayuda de una lista enlazada, la lista contendrá 5 Nodes. Cuando vinculamos cada Node, obtenemos una estructura de lista vinculada que representa el polinomio F(x) .

Addition of polynomials

Para sumar dos polinomios, necesitamos escanearlos una vez.
Si encontramos términos con el mismo exponente en los dos polinomios, entonces sumamos los coeficientes, de lo contrario, copiamos el término de mayor exponente en la suma y seguimos.
Cuando llegamos al final de uno de los polinomios, la parte restante del otro se copia en la suma.
Supongamos que tenemos dos polinomios como se ilustra y tenemos que realizar la suma de estos polinomios.

Cuando escaneamos el primer Node de los dos polinomios, encontramos que la potencia exponencial del primer Node en el segundo polinomio es mayor que la del primer Node del primer polinomio.
Aquí el exponente del primer Node del segundo polinomio es mayor, por lo que tenemos que copiar el primer Node del segundo polinomio en la suma.
Luego, consideramos el primer Node del primer polinomio y, una vez más, el valor del primer Node del primer polinomio se compara con el valor del segundo Node del segundo polinomio.
Aquí, el valor del exponente del primer Node del primer polinomio es mayor que el valor del exponente del segundo Node del segundo polinomio. Copiamos el primer Node del primer polinomio en la suma.
Ahora considere el segundo Node del primer polinomio y compárelo con el segundo Node del segundo polinomio.
Aquí, el valor del exponente del segundo Node del segundo polinomio es mayor que el segundo Node del primer polinomio, por lo que copiamos el segundo Node de la segunda lista en la suma.
Ahora consideramos el exponente del tercer Node del segundo polinomio y lo comparamos con el valor del exponente del segundo Node del primer polinomio. Encontramos que ambos son iguales, por lo tanto, realice la suma de su coeficiente y copie la suma.
Este proceso continúa hasta que se agotan todos los Nodes de ambos polinomios. Por ejemplo, después de sumar los dos polinomios anteriores, obtenemos el siguiente polinomio resultante como se muestra.