logo

TechCodeview

リンクリストの応用

この記事では、リンク リスト アプリケーションについて詳しく説明します。

リンクされたリストとはどういう意味ですか?

リンク リストは、ノードと呼ばれる要素で構成される線形データ構造です。各ノードは、情報部分とリンク部分 (ネクスト ポインター部分とも呼ばれます) の 2 つの部分で構成されます。

リンク リストは、次のようなさまざまなアプリケーションで使用されます。

  • 多項式操作の表現
  • 長い正の整数の加算
  • スパース行列の表現
  • 長い正の整数の加算
  • シンボルテーブルの作成
  • メーリングリスト
  • メモリ管理
  • ファイルのリンク割り当て
  • 多倍長演算など

多項式の操作

多項式操作は、リンク リストの最も重要なアプリケーションの 1 つです。多項式は数学の重要な部分ですが、ほとんどの言語ではデータ型として本質的にサポートされていません。多項式はさまざまな項の集合であり、それぞれの項は係数と指数で構成されます。リンクリストを使用して表現できます。この表現により、多項式操作が効率的に行われます。

リンク リストを使用して多項式を表す場合、各多項式項はリンク リスト内のノードを表します。処理の効率を高めるために、すべての多項式の項が指数の降順でリンク リスト内に格納されると仮定します。また、同じ指数を持つ 2 つの項はなく、係数がゼロで係数のない項もありません。係数の値は 1 です。

多項式を表すリンク リストの各ノードは、次の 3 つの部分を構成します。

Cプログラミングにおける行列
  • 最初の部分には項の係数の値が含まれます。
  • 2 番目の部分には指数の値が含まれます。
  • 3 番目の部分、LINK は次の項 (次のノード) を指します。

多項式を表すリンク リストのノードの構造を以下に示します。

リンクリストの応用

多項式 P(x) = 7x を考えてみましょう。2+15倍3- 2×2+ 9。ここで、7、15、-2、および 9 は係数であり、4、3、2、0 は多項式の項の指数です。リンク リストを使用してこの多項式を表すと、次のようになります。

リンクリストの応用

ノードの数が多項式の項の数と等しいことに注目してください。したがって、ノードは 4 つあります。さらに、項は、リンクされたリスト内の指数を減少させるために格納されます。このようにリンク リストを使用して多項式を表現すると、多項式に対する減算、加算、乗算などの演算が非常に簡単になります。

多項式の追加:

2 つの多項式を加算するには、リスト P と Q を調べます。リスト P と Q の対応する項を取得し、それらの指数を比較します。 2 つの指数が等しい場合、係数が加算されて新しい係数が作成されます。新しい係数が 0 に等しい場合、その項は削除され、ゼロでない場合は、結果の多項式を含む新しいリンク リストの最後に挿入されます。指数の一方が他方より大きい場合、対応する項は直ちに新しいリンクされたリストに入れられ、指数が小さい方の項が保持され、他のリストの次の項と比較されます。一方のリストが他方のリストより先に終了する場合、長いリストの残りの項は、結果の多項式を含む新しいリンク リストの最後に挿入されます。

2 つの多項式の加算がどのように実行されるかを示す例を考えてみましょう。

P(x) = 3x4+2倍3- 4×2+7

Q (x) = 5x3+4×2- 5

これらの多項式は、次のように指数の降順でリンク リストを使用して表されます。

リンクリストの応用
リンクリストの応用

指定された多項式 P(x) と Q(x) を加算して形成される多項式の新しいリンク リストを生成するには、次の手順を実行します。

  1. 2 つのリスト P と Q を調べて、すべてのノードを調べます。
  2. 2 つの多項式の対応する項の指数を比較します。多項式 P と Q の最初の項には、それぞれ指数 4 と 3 が含まれています。多項式 P の最初の項の指数は他の多項式 Q より大きいため、より大きい指数を持つ項が新しいリストに挿入されます。新しいリストは、最初は次のようになります。
    リンクリストの応用
  3. 次に、リスト P の次の項の指数とリスト Q の現在の項の指数を比較します。2 つの指数は等しいため、次のようにそれらの係数が新しいリストに追加されます。
    リンクリストの応用
  4. 次に、P リストと Q リストの次の項に移動し、それらの指数を比較します。これら両方の項の指数は等しく、それらの係数を加算すると 0 が得られるため、項は削除され、この後新しいリストにノードは追加されません。
    リンクリストの応用
  5. 2 つのリストの次の項 P と Q に移動すると、対応する項の指数が 0 に等しいことがわかります。それらの係数を追加し、以下に示すように、結果の多項式の新しいリストに追加します。
    リンクリストの応用

例：

2 つの多項式を加算する C++ プログラム 

 #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;>

説明：

上記の例では、リンク リストを使用して 2 つの多項式の和​​の例を作成しました。

出力：

以下は、この例の出力です。

np.concatenate
リンクリストの応用

複数の変数の多項式

多項式は複数の変数、つまり 2 つまたは 3 つの変数で表すことができます。以下は、単一リンク リストを使用して 3 つの変数 X、Y、Z を持つ多項式を表すのに適したノード構造です。

リンクリストの応用

多項式 P(x, y, z) = 10x を考えてみましょう。2そして2z + 17 x2yz2- 5xy2z+ 21y4と2+ 7. リンク リストを使用してこの多項式を表現すると、次のようになります。

リンクリストの応用

このような多項式の項は、x の次数の減少に従って順序付けされます。 x の次数が同じものは、y の次数の減少に従って順序付けされます。 x と y の次数が同じものは、z の次数の降順に従って順序付けされます。

例

2 つの多項式を乗算する単純な C++ プログラム 

 #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;>