연결리스트 적용 - DS 튜토리얼

이번 글에서는 연결리스트 응용에 대해 자세히 알아보겠습니다.

연결리스트란 무엇을 의미하나요?

연결된 목록은 노드라는 요소로 구성된 선형 데이터 구조입니다. 여기서 각 노드는 정보 부분과 링크 부분(다음 포인터 부분이라고도 함)의 두 부분으로 구성됩니다.

연결리스트는 다음과 같은 다양한 응용프로그램에서 사용됩니다.

다항식 조작 표현
긴 양의 정수 추가
희소 행렬 표현
긴 양의 정수 추가
심볼 테이블 생성
메일링 리스트
메모리 관리
파일 연결 할당
다중 정밀 연산 등

다항식 조작

다항식 조작은 연결 목록의 가장 중요한 응용 프로그램 중 하나입니다. 다항식은 대부분의 언어에서 데이터 유형으로 본질적으로 지원되지 않는 수학의 중요한 부분입니다. 다항식은 각각 계수와 지수로 구성된 다양한 항의 모음입니다. 연결리스트(Linked List)를 사용하여 표현할 수 있습니다. 이 표현은 다항식 조작을 효율적으로 만듭니다.

연결리스트를 사용하여 다항식을 표현하는 동안 각 다항식 항은 연결리스트의 노드를 나타냅니다. 처리의 효율성을 높이기 위해 모든 다항식의 항은 지수가 감소하는 순서로 연결 리스트 내에 저장된다고 가정합니다. 또한 두 항의 지수가 동일하지 않으며 계수가 0이거나 계수가 없는 항은 없습니다. 계수는 1의 값을 갖습니다.

문자열에 Java가 포함되어 있습니다.

다항식을 나타내는 연결된 목록의 각 노드는 세 부분으로 구성됩니다.

첫 번째 부분에는 항의 계수 값이 포함됩니다.
두 번째 부분에는 지수 값이 포함됩니다.
세 번째 부분인 LINK는 다음 용어(다음 노드)를 가리킵니다.

다항식을 나타내는 연결리스트의 노드 구조는 다음과 같습니다.

다항식 P(x) = 7x를 생각해 보세요.²+ 15배^삼- 2번²+ 9. 여기서 7, 15, -2, 9는 계수이고 4,3,2,0은 다항식 항의 지수입니다. 연결리스트를 사용하여 이 다항식을 표현하면 다음과 같습니다.

노드 수가 다항식의 항 수와 동일하다는 점을 확인하세요. 따라서 4개의 노드가 있습니다. 또한 연결된 목록의 지수를 줄이기 위해 용어가 저장됩니다. 연결 리스트를 사용하여 다항식을 표현하면 다항식에 대한 뺄셈, 덧셈, 곱셈 등과 같은 연산이 매우 쉬워집니다.

다항식의 추가:

두 개의 다항식을 더하기 위해 목록 P와 Q를 순회합니다. 목록 P와 Q의 해당 항을 가져와 해당 지수를 비교합니다. 두 지수가 동일하면 계수가 추가되어 새 계수가 생성됩니다. 새 계수가 0이면 해당 항은 삭제되고, 0이 아니면 결과 다항식을 포함하는 새 연결 목록의 끝에 삽입됩니다. 지수 중 하나가 다른 것보다 크면 해당 용어는 즉시 새 연결 목록에 배치되고 지수가 더 작은 용어는 다른 목록의 다음 용어와 비교됩니다. 한 목록이 다른 목록보다 먼저 끝나면 더 긴 목록의 나머지 용어는 결과 다항식을 포함하는 새 연결 목록의 끝에 삽입됩니다.

두 다항식의 덧셈이 어떻게 수행되는지 보여주는 예를 생각해 보겠습니다.

사자와 호랑이의 비교

P(x) = 3x⁴+ 2배^삼- 4배²+ 7

Q(x) = 5x^삼+ 4배²- 5

이러한 다항식은 다음과 같이 지수가 감소하는 순서로 연결된 목록을 사용하여 표현됩니다.

주어진 다항식 P(x)와 Q(x)의 덧셈으로 형성된 결과 다항식에 대한 새로운 연결 목록을 생성하려면 다음 단계를 수행합니다.

두 개의 목록 P와 Q를 순회하고 모든 노드를 검사합니다.
두 다항식의 해당 항의 지수를 비교합니다. 다항식 P와 Q의 첫 번째 항은 각각 지수 4와 3을 포함합니다. 다항식 P의 첫 번째 항의 지수가 다른 다항식 Q보다 크므로 지수가 더 큰 항이 새 리스트에 삽입됩니다. 새 목록은 처음에 아래와 같이 표시됩니다.
그런 다음 목록 P의 다음 항의 지수를 목록 Q의 현재 항의 지수와 비교합니다. 두 지수가 동일하므로 해당 계수가 다음과 같이 새 목록에 추가되고 추가됩니다.
그런 다음 P 및 Q 목록의 다음 항으로 이동하여 지수를 비교합니다. 이 두 항의 지수는 동일하고 계수를 더한 후에는 0이 되므로 항은 삭제되고 이후에는 새 목록에 노드가 추가되지 않습니다.
두 목록 P와 Q의 다음 항으로 이동하면 해당 항의 지수가 0과 동일하다는 것을 알 수 있습니다. 아래와 같이 계수를 추가하고 결과 다항식에 대한 새 목록에 추가합니다.

예:

두 개의 다항식을 더하는 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;>

설명:

다중 테이블 SQL 선택

위의 예에서는 연결리스트를 사용하여 두 다항식의 합을 구하는 예를 만들었습니다.

산출:

아래는 이 예제의 출력입니다.

다중 변수의 다항식

하나 이상의 변수를 갖는 다항식을 표현할 수 있습니다. 즉, 두 개 또는 세 개의 변수가 될 수 있습니다. 다음은 단일 연결 리스트를 사용하여 X, Y, Z 세 개의 변수를 갖는 다항식을 표현하는 데 적합한 노드 구조입니다.

다항식 P(x, y, z) = 10x를 생각해 보세요.²그리고²z + 17x²y z²- 5xy²z+ 21년⁴와 함께²+ 7. 연결된 리스트를 사용하여 이 다항식을 표현하면 다음과 같습니다.

이러한 다항식의 항은 x의 감소 정도에 따라 정렬됩니다. x에서 동일한 차수를 갖는 항목은 y에서 감소하는 차수에 따라 정렬됩니다. x와 y에서 동일한 차수를 갖는 요소는 z에서 감소하는 차수에 따라 정렬됩니다.

b트리와 b트리

예

두 개의 다항식을 곱하는 간단한 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;>