APLICACIÓN DE LISTA ENLAZADA

En este artículo, comprenderemos en detalle las aplicaciones de listas vinculadas.

¿Qué quieres decir con lista enlazada?

Una lista enlazada es una estructura de datos lineal que consta de elementos llamados nodos donde cada nodo se compone de dos partes: una parte de información y una parte de enlace, también llamada parte del siguiente puntero.

La lista enlazada se utiliza en una amplia variedad de aplicaciones, como

Representación de manipulación polinómica
Suma de números enteros positivos largos
Representación de matrices dispersas.
Suma de números enteros positivos largos
Creación de tabla de símbolos
Lista de correo
Gestión de la memoria
Asignación vinculada de archivos
Aritmética de precisión múltiple, etc.

Manipulación polinomial

Las manipulaciones polinómicas son una de las aplicaciones más importantes de las listas enlazadas. Los polinomios son una parte importante de las matemáticas que la mayoría de los lenguajes no admiten inherentemente como tipo de datos. Un polinomio es una colección de términos diferentes, cada uno de los cuales comprende coeficientes y exponentes. Se puede representar mediante una lista vinculada. Esta representación hace que la manipulación polinomial sea eficiente.

Si bien se representa un polinomio mediante una lista vinculada, cada término del polinomio representa un nodo en la lista vinculada. Para obtener una mayor eficiencia en el procesamiento, asumimos que el término de cada polinomio se almacena dentro de la lista vinculada en el orden de exponentes decrecientes. Además, no hay dos términos que tengan el mismo exponente y ningún término tiene coeficiente cero y sin coeficientes. El coeficiente toma un valor de 1.

Cada nodo de una lista enlazada que representa un polinomio constituye tres partes:

La primera parte contiene el valor del coeficiente del término.
La segunda parte contiene el valor del exponente.
La tercera parte, LINK, apunta al siguiente término (siguiente nodo).

La estructura de un nodo de una lista enlazada que representa un polinomio se muestra a continuación:

Considere un polinomio P(x) = 7x²+ 15x³- 2 veces²+ 9. Aquí 7, 15, -2 y 9 son los coeficientes y 4,3,2,0 son los exponentes de los términos del polinomio. Al representar este polinomio usando una lista enlazada, tenemos

Observe que el número de nodos es igual al número de términos del polinomio. Entonces tenemos 4 nodos. Además, los términos se almacenan para disminuir los exponentes en la lista vinculada. Esta representación de polinomios mediante listas enlazadas hace que operaciones como resta, suma, multiplicación, etc., en polinomios sean muy fáciles.

Suma de polinomios:

Para sumar dos polinomios, recorremos la lista P y Q. Tomamos los términos correspondientes de la lista P y Q y comparamos sus exponentes. Si los dos exponentes son iguales, los coeficientes se suman para crear un nuevo coeficiente. Si el nuevo coeficiente es igual a 0, entonces el término se elimina y, si no es cero, se inserta al final de la nueva lista enlazada que contiene el polinomio resultante. Si uno de los exponentes es mayor que el otro, el término correspondiente se coloca inmediatamente en la nueva lista vinculada y el término con el exponente menor se compara con el siguiente término de la otra lista. Si una lista termina antes que la otra, el resto de los términos de la lista más larga se inserta al final de la nueva lista enlazada que contiene el polinomio resultante.

Consideremos un ejemplo para mostrar cómo se realiza la suma de dos polinomios,

P(x) = 3x⁴+ 2x³- 4x²+ 7

Q(x) = 5x³+ 4x²- 5

Estos polinomios se representan mediante una lista enlazada en orden de exponentes decrecientes de la siguiente manera:

Para generar una nueva lista enlazada para los polinomios resultantes que se forma al sumar los polinomios dados P(x) y Q(x), realizamos los siguientes pasos:

Recorra las dos listas P y Q y examine todos los nodos.
Comparamos los exponentes de los términos correspondientes de dos polinomios. El primer término de los polinomios P y Q contienen exponentes 4 y 3, respectivamente. Dado que el exponente del primer término del polinomio P es mayor que el otro polinomio Q, el término que tiene un exponente mayor se inserta en la nueva lista. La nueva lista inicialmente tiene el aspecto que se muestra a continuación:
Luego comparamos el exponente del siguiente término de la lista P con los exponentes del término actual de la lista Q. Dado que los dos exponentes son iguales, sus coeficientes se suman y agregan a la nueva lista de la siguiente manera:
Luego pasamos al siguiente término de las listas P y Q y comparamos sus exponentes. Dado que los exponentes de ambos términos son iguales y después de la suma de sus coeficientes, obtenemos 0, por lo que el término se elimina y no se agrega ningún nodo a la nueva lista después de esto,
Pasando al siguiente término de las dos listas, P y Q, encontramos que los términos correspondientes tienen los mismos exponentes iguales a 0. Sumamos sus coeficientes y los agregamos a la nueva lista para el polinomio resultante como se muestra a continuación:

Ejemplo:

Programa C++ para sumar dos polinomios

 #include using namespace std; int max(int m, int n) { return (m &gt; n)? m: n; } int *add(int A[], int B[], int m, int n) { int size = max(m, n); int *sum = new int[size]; for (int i = 0; i<m; 4 6 i++) sum[i]="A[i];" for (int i="0;" i<n; +="B[i];" return sum; } void printpoly(int poly[], int n) { cout << poly[i]; if (i !="0)" 'x^' ; ' '; main() a[]="{" 5, 0, 10, }; b[]="{" 1, 2, m="sizeof(A)/sizeof(A[0]);" n="sizeof(B)/sizeof(B[0]);" 'first polynomial is 
'; printpoly(a, m); '
 second printpoly(b, n); *sum="add(A," b, m, size="max(m," sum of printpoly(sum, size); 0; < pre> <p> <strong>Explanation:</strong> </p> <p>In the above example, we have created an example of sum of two polynomial using array.</p> <p> <strong>Output:</strong> </p> <p>Below is the output of this example.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-9.webp" alt="Application of Linked List"> <h3>Addition of long positive integer using linked list</h3> <p>Most programming languages allow restrictions on the maximum value of integers stored. The maximum value of the largest integers is 32767, and the largest is 2147483647. Sometimes, applications such as security algorithms and cryptography require storing and manipulating integers of unlimited size. So in such a situation, it is desirable to use a linked list for storing and manipulating integers of arbitrary length.</p> <p>Adding long positive integers can be performed effectively using a circular linked list. As we know that when we add two long integers, the digits of the given numbers are individually traversed from right to left, and the corresponding digits of the two numbers along with a carry from prior digits sum are added. So to accomplish addition, we must need to know how the digits of a long integer are stored in a linked list.</p> <p>The digits of a long integer must be stored from right to left in a linked list so that the first node on the list contains the least significant digit, i.e., the rightmost digit, and the last node contains the most significant digit, i.e., leftmost digit.</p> <p> <strong>Example:</strong> An integer value 543467 can be represented using a linked list as</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-10.webp" alt="Application of Linked List"> <p> <strong>For performing the addition of two long integers, the following steps need to be followed:</strong> </p> <ul> <li>Traverse the two linked lists in parallel from left to right.</li> <li>During traversal, corresponding digits and a carry from prior digits sum are added, then stored in the new node of the resultant linked list.</li> </ul> <p>The first positive long integer 543467 is represented using a linked list whose first node is pointed by NUM1 pointer. Similarly, the second positive long integer 48315 is represented using the second linked list whose first node is pointed by NUM2 pointer. These two numbers are stored in the third linked list whose first node is pointed to by the RESULT pointer.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-11.webp" alt="Application of Linked List"> <h3>Example:</h3> <p> <strong>C++ program for addition of two polynomials using Linked Lists</strong> </p> <pre> #include #include using namespace std; struct Node { int coeff; int pow; struct Node* next; }; void create_node(int x, int y, struct Node** temp) { struct Node *r, *z; z = *temp; if (z == NULL) { r = (struct Node*)malloc(sizeof(struct Node)); r-&gt;coeff = x; r-&gt;pow = y; *temp = r; r-&gt;next = (struct Node*)malloc(sizeof(struct Node)); r = r-&gt;next; r-&gt;next = NULL; } else { r-&gt;coeff = x; r-&gt;pow = y; r-&gt;next = (struct Node*)malloc(sizeof(struct Node)); r = r-&gt;next; r-&gt;next = NULL; } } void polyadd(struct Node* poly1, struct Node* poly2, struct Node* poly) { while (poly1-&gt;next &amp;&amp; poly2-&gt;next) { if (poly1-&gt;pow &gt; poly2-&gt;pow) { poly-&gt;pow = poly1-&gt;pow; poly-&gt;coeff = poly1-&gt;coeff; poly1 = poly1-&gt;next; } else if (poly1-&gt;pow pow) { poly-&gt;pow = poly2-&gt;pow; poly-&gt;coeff = poly2-&gt;coeff; poly2 = poly2-&gt;next; } else { poly-&gt;pow = poly1-&gt;pow; poly-&gt;coeff = poly1-&gt;coeff + poly2-&gt;coeff; poly1 = poly1-&gt;next; poly2 = poly2-&gt;next; } poly-&gt;next = (struct Node*)malloc(sizeof(struct Node)); poly = poly-&gt;next; poly-&gt;next = NULL; } while (poly1-&gt;next || poly2-&gt;next) { if (poly1-&gt;next) { poly-&gt;pow = poly1-&gt;pow; poly-&gt;coeff = poly1-&gt;coeff; poly1 = poly1-&gt;next; } if (poly2-&gt;next) { poly-&gt;pow = poly2-&gt;pow; poly-&gt;coeff = poly2-&gt;coeff; poly2 = poly2-&gt;next; } poly-&gt;next = (struct Node*)malloc(sizeof(struct Node)); poly = poly-&gt;next; poly-&gt;next = NULL; } } void show(struct Node* node) { while (node-&gt;next != NULL) { printf(&apos;%dx^%d&apos;, node-&gt;coeff, node-&gt;pow); node = node-&gt;next; if (node-&gt;coeff &gt;= 0) { if (node-&gt;next != NULL) printf(&apos;+&apos;); } } } int main() { struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL; create_node(5, 2, &amp;poly1); create_node(4, 1, &amp;poly1); create_node(2, 0, &amp;poly1); create_node(-5, 1, &amp;poly2); create_node(-5, 0, &amp;poly2); printf(&apos;1st Number: &apos;); show(poly1); printf(&apos;
 2nd Number: &apos;); show(poly2); poly = (struct Node*)malloc(sizeof(struct Node)); polyadd(poly1, poly2, poly); printf(&apos;
 Sum of polynomial after addition: &apos;); show(poly); return 0; } </pre> <p> <strong>Explanation:</strong> </p> <p>In the above example, we have created an example of sum of two polynomial using linked list.</p> <p> <strong>Output:</strong> </p> <p>Below is the output of this example.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-12.webp" alt="Application of Linked List"> <h3>Polynomial of Multiple Variables</h3> <p>We can represent a polynomial with more than one variable, i.e., it can be two or three variables. Below is a node structure suitable for representing a polynomial with three variables X, Y, Z using a singly linked list.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-13.webp" alt="Application of Linked List"> <p>Consider a polynomial P(x, y, z) = 10x<sup>2</sup>y<sup>2</sup>z + 17 x<sup>2</sup>y z<sup>2</sup> - 5 xy<sup>2</sup> z+ 21y<sup>4</sup>z<sup>2</sup> + 7. On represnting this polynomial using linked list are:</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-14.webp" alt="Application of Linked List"> <p>Terms in such a polynomial are ordered accordingly to the decreasing degree in x. Those with the same degree in x are ordered according to decreasing degree in y. Those with the same degree in x and y are ordered according to decreasing degrees in z.</p> <h3>Example</h3> <p> <strong>Simple C++ program to multiply two polynomials</strong> </p> <pre> #include using namespace std; int *multiply(int A[], int B[], int m, int n) { int *prod = new int[m+n-1]; for (int i = 0; i<m+n-1; 4 6 i++) prod[i]="0;" for (int i="0;" i<m; { j="0;" j<n; j++) prod[i+j] +="A[i]*B[j];" } return prod; void printpoly(int poly[], int n) i<n; cout << poly[i]; if (i !="0)" 'x^' ; ' '; main() a[]="{" 5, 0, 10, }; b[]="{" 1, 2, m="sizeof(A)/sizeof(A[0]);" n="sizeof(B)/sizeof(B[0]);" 'first polynomial is 
'; printpoly(a, m); '
second printpoly(b, n); *prod="multiply(A," b, m, '
product of two printpoly(prod, m+n-1); 0; < pre> <p> <strong>Explanation:</strong> </p> <p>In the above example, we have created an example of multiple of two polynomial using arrays.</p> <p> <strong>Output:</strong> </p> <p>Below is the output of this example.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-15.webp" alt="Application of Linked List"> <h2>Some other applications of linked list:</h2> <ul> <tr><td>Memory Management:</td> Memory management is one of the operating system&apos;s key features. It decides how to allocate and reclaim storage for processes running on the system. We can use a linked list to keep track of portions of memory available for allocation. </tr><tr><td>Mailing List:</td> Linked lists have their use in email applications. Since it is difficult to predict multiple lists, maybe a mailer builds a linked list of addresses before sending a message. </tr><tr><td>LISP:</td> LISP is an acronym for LIST processor, an important programming language in artificial intelligence. This language extensively uses linked lists in performing symbolic processing. </tr><tr><td>Linked allocation of files:</td> A file of large size may not be stored in one place on a disk. So there must be some mechanism to link all the scattered parts of the file together. The use of a linked list allows an efficient file allocation method in which each block of a file contains a pointer to the file&apos;s text block. But this method is good only for sequential access. </tr><tr><td>Virtual Memory:</td> An interesting application of linked lists is found in the way systems support virtual memory. </tr><tr><td>Support for other data structures:</td> Some other data structures like stacks, queues, hash tables, graphs can be implemented using a linked list. </tr></ul> <hr></m+n-1;></pre></m;>

Explicación:

En el ejemplo anterior, hemos creado un ejemplo de suma de dos polinomios usando una lista vinculada.

Producción:

A continuación se muestra el resultado de este ejemplo.

Polinomio de múltiples variables

Podemos representar un polinomio con más de una variable, es decir, puede tener dos o tres variables. A continuación se muestra una estructura de nodo adecuada para representar un polinomio con tres variables X, Y, Z utilizando una lista enlazada individualmente.

Considere un polinomio P(x, y, z) = 10x²y²z+17x²y z²- 5 xy²z+ 21 años⁴Con²+ 7. Sobre la representación de este polinomio usando una lista enlazada son:

Los términos de dicho polinomio se ordenan de acuerdo con el grado decreciente en x. Aquellos que tienen el mismo grado en x se ordenan según grado decreciente en y. Aquellos que tienen el mismo grado en xey se ordenan según grados decrecientes en z.

Ejemplo

Programa simple en C++ para multiplicar dos polinomios

 #include using namespace std; int *multiply(int A[], int B[], int m, int n) { int *prod = new int[m+n-1]; for (int i = 0; i<m+n-1; 4 6 i++) prod[i]="0;" for (int i="0;" i<m; { j="0;" j<n; j++) prod[i+j] +="A[i]*B[j];" } return prod; void printpoly(int poly[], int n) i<n; cout << poly[i]; if (i !="0)" \'x^\' ; \' \'; main() a[]="{" 5, 0, 10, }; b[]="{" 1, 2, m="sizeof(A)/sizeof(A[0]);" n="sizeof(B)/sizeof(B[0]);" \'first polynomial is 
\'; printpoly(a, m); \'
second printpoly(b, n); *prod="multiply(A," b, m, \'
product of two printpoly(prod, m+n-1); 0; < pre> <p> <strong>Explanation:</strong> </p> <p>In the above example, we have created an example of multiple of two polynomial using arrays.</p> <p> <strong>Output:</strong> </p> <p>Below is the output of this example.</p> <img src="//techcodeview.com/img/ds-tutorial/92/application-linked-list-15.webp" alt="Application of Linked List"> <h2>Some other applications of linked list:</h2> <ul> <tr><td>Memory Management:</td> Memory management is one of the operating system&apos;s key features. It decides how to allocate and reclaim storage for processes running on the system. We can use a linked list to keep track of portions of memory available for allocation. </tr><tr><td>Mailing List:</td> Linked lists have their use in email applications. Since it is difficult to predict multiple lists, maybe a mailer builds a linked list of addresses before sending a message. </tr><tr><td>LISP:</td> LISP is an acronym for LIST processor, an important programming language in artificial intelligence. This language extensively uses linked lists in performing symbolic processing. </tr><tr><td>Linked allocation of files:</td> A file of large size may not be stored in one place on a disk. So there must be some mechanism to link all the scattered parts of the file together. The use of a linked list allows an efficient file allocation method in which each block of a file contains a pointer to the file&apos;s text block. But this method is good only for sequential access. </tr><tr><td>Virtual Memory:</td> An interesting application of linked lists is found in the way systems support virtual memory. </tr><tr><td>Support for other data structures:</td> Some other data structures like stacks, queues, hash tables, graphs can be implemented using a linked list. </tr></ul> <hr></m+n-1;>

TechCodeview