TechCodeview

Bu yazımızda bağlantılı liste uygulamalarını detaylı olarak ele alacağız.

Bağlantılı liste ile ne demek istiyorsunuz?

Bağlantılı liste, her düğümün iki bölümden oluştuğu, düğüm adı verilen öğelerden oluşan doğrusal bir veri yapısıdır: bir bilgi bölümü ve bir sonraki işaretçi bölümü olarak da adlandırılan bir bağlantı bölümü.

Bağlantılı liste, aşağıdaki gibi çok çeşitli uygulamalarda kullanılır:

• Polinom Manipülasyon gösterimi
• Uzun pozitif tam sayıların toplanması
• Seyrek matrislerin temsili
• Uzun pozitif tam sayıların toplanması
• Sembol tablosu oluşturma
• Mail listesi
• Bellek yönetimi
• Dosyaların bağlantılı tahsisi
• Çoklu duyarlıklı aritmetik vb.

Polinom Manipülasyonu

Polinom manipülasyonları bağlantılı listelerin en önemli uygulamalarından biridir. Polinomlar matematiğin önemli bir parçasıdır ve çoğu dil tarafından veri türü olarak desteklenmez. Bir polinom, her biri katsayılar ve üslerden oluşan farklı terimlerin bir koleksiyonudur. Bağlantılı bir liste kullanılarak temsil edilebilir. Bu gösterim polinom manipülasyonunu verimli hale getirir.

Bağlantılı liste kullanarak bir polinomu temsil ederken, her polinom terimi bağlantılı listedeki bir düğümü temsil eder. İşlemede daha iyi verim elde etmek için, her polinomun teriminin bağlantılı listede azalan üsler sırasına göre saklandığını varsayıyoruz. Ayrıca hiçbir iki terim aynı üste sahip değildir ve hiçbir terim sıfır katsayılı ve katsayısız değildir. Katsayı 1 değerini alır.

Polinomu temsil eden bağlantılı listenin her düğümü üç bölümden oluşur:

• İlk kısım terimin katsayısının değerini içerir.
• İkinci kısım üssün değerini içerir.
• Üçüncü bölüm olan LINK, bir sonraki terime (sonraki düğüme) işaret eder.

Bir polinomu temsil eden bağlantılı listenin düğümünün yapısı aşağıda gösterilmiştir:

P(x) = 7x polinomunu düşünün²+ 15x³- 2 kere²+ 9. Burada 7, 15, -2 ve 9 katsayılardır ve 4,3,2,0 polinomdaki terimlerin üsleridir. Bu polinomu bağlantılı bir liste kullanarak temsil ederken,

Düğüm sayısının polinomdaki terim sayısına eşit olduğunu gözlemleyin. Yani 4 düğümümüz var. Ayrıca terimler bağlantılı listedeki üsleri azaltmak için saklanır. Polinomun bağlantılı listeler kullanılarak bu şekilde temsil edilmesi, polinom üzerinde çıkarma, toplama, çarpma vb. işlemleri çok kolaylaştırır.

Polinomların Toplanması:

İki polinomu eklemek için P ve Q listesinin üzerinden geçiyoruz. P ve Q listesinin karşılık gelen terimlerini alıyoruz ve bunların üslerini karşılaştırıyoruz. Eğer iki üs eşitse, yeni bir katsayı oluşturmak için katsayılar toplanır. Yeni katsayı 0'a eşitse terim çıkarılır, sıfır değilse elde edilen polinomu içeren yeni bağlantılı listenin sonuna eklenir. Üslerden biri diğerinden büyükse, karşılık gelen terim hemen yeni bağlantılı listeye yerleştirilir ve daha küçük üslü olan terim, diğer listedeki bir sonraki terimle karşılaştırılmak üzere tutulur. Bir liste diğerinden önce biterse, uzun listenin geri kalan terimleri, elde edilen polinomu içeren yeni bağlantılı listenin sonuna eklenir.

Java'da yakalamayı deneyin

İki polinomun toplamının nasıl yapıldığını gösteren bir örnek ele alalım,

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

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

Bu polinomlar, azalan üslerin sırasına göre bağlantılı bir liste kullanılarak aşağıdaki şekilde temsil edilir:

Verilen P(x) ve Q(x) polinomlarının eklenmesiyle oluşan sonuçtaki polinomlar için yeni bir bağlantılı liste oluşturmak için aşağıdaki adımları uygularız,

1. P ve Q listelerini dolaşın ve tüm düğümleri inceleyin.
2. İki polinomun karşılık gelen terimlerinin üslerini karşılaştırıyoruz. P ve Q polinomlarının ilk terimi sırasıyla 4 ve 3 üslerini içerir. P polinomunun ilk teriminin üssü diğer Q polinomundan büyük olduğundan üssü daha büyük olan terim yeni listeye eklenir. Yeni liste başlangıçta aşağıda gösterildiği gibi görünür:
   
3. Daha sonra P listesinin bir sonraki teriminin üssünü Q listesinin mevcut teriminin üsleriyle karşılaştırırız. İki üs eşit olduğundan katsayıları aşağıdaki gibi yeni listeye eklenir ve eklenir:
   
4. Daha sonra P ve Q listelerinin bir sonraki terimine geçiyoruz ve üslerini karşılaştırıyoruz. Her iki terimin üsleri eşit olduğundan ve katsayıları toplandıktan sonra 0 elde ettiğimiz için terim düşürülür ve bundan sonra yeni listeye hiçbir düğüm eklenmez,
   
5. İki listenin bir sonraki terimi olan P ve Q'ya geçtiğimizde, karşılık gelen terimlerin 0'a eşit aynı üslere sahip olduğunu buluruz. Katsayılarını toplarız ve bunları aşağıda gösterildiği gibi elde edilen polinom için yeni listeye ekleriz:
   

Örnek:

İki polinomu toplayan C++ programı

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

Açıklama:

Yukarıdaki örnekte, bağlantılı listeyi kullanarak iki polinomun toplamına ilişkin bir örnek oluşturduk.

Çıktı:

Bu örneğin çıktısı aşağıdadır.

tostring yöntemi

Çok Değişkenli Polinom

Bir polinomu birden fazla değişkenle temsil edebiliriz, yani iki veya üç değişkenli olabilir. Aşağıda, tek bağlantılı bir liste kullanarak X, Y, Z üç değişkenli bir polinomu temsil etmeye uygun bir düğüm yapısı verilmiştir.

P(x, y, z) = 10x polinomunu düşünün²Ve²z + 17x²y z²- 5xy²z+ 21y⁴İle²+ 7. Bu polinomun bağlantılı liste kullanılarak temsil edilmesiyle ilgili olarak:

Böyle bir polinomdaki terimler x'teki azalan dereceye göre sıralanır. X'te derecesi aynı olanlar, y'de azalan dereceye göre sıralanır. X ve y'de derecesi aynı olanlar z'de azalan derecelere göre sıralanır.

Örnek

İki polinomu çarpmak için basit C++ programı

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