A prepojený zoznam je druh lineárnej dynamickej dátovej štruktúry, ktorú používame na ukladanie dátových prvkov. Polia sú tiež typom lineárnej dátovej štruktúry, kde sú dátové položky uložené v kontinuálnych pamäťových blokoch.
Na rozdiel od polí nemusí prepojený zoznam ukladať dátové prvky v súvislých pamäťových oblastiach alebo blokoch.
A prepojený zoznam pozostáva z prvkov známych ako „uzly“, ktoré sú rozdelené na dve časti. Prvým komponentom je časť, kde ukladáme aktuálne dáta, a druhým je časť, kde ukladáme ukazovateľ na nasledujúci uzol. Tento typ štruktúry je známy ako „ jednotlivo prepojený zoznam .'
Prepojený zoznam v C++
Tento návod podrobne prejde jednotlivo prepojený zoznam.
Štruktúra jedného prepojeného zoznamu je znázornená na obrázku nižšie
- Ako sme videli vo vyššie uvedenej časti, prvý uzol prepojeného zoznamu je známy ako „hlava“, zatiaľ čo posledný uzol sa nazýva „chvost“. Je to preto, že v poslednom uzle nie je špecifikovaná žiadna adresa pamäte, posledný uzol prepojeného zoznamu bude mať ďalší ukazovateľ nula.
- Pretože každý uzol obsahuje ukazovateľ na nasledujúci uzol, dátové prvky v prepojenom zozname nie je potrebné uchovávať v súvislých miestach. Uzly môžu byť rozptýlené po celej pamäti. Pretože každý uzol má adresu toho nasledujúceho, môžeme k uzlom pristupovať kedykoľvek chceme.
- Môžeme rýchlo pridávať a odstraňovať dátové položky z pripojeného zoznamu. Výsledkom je, že prepojený zoznam sa môže dynamicky zväčšovať alebo zmenšovať. Prepojený zoznam nemá žiadne maximálne množstvo dátových položiek, ktoré môže obsahovať. Výsledkom je, že do prepojeného zoznamu môžeme pridať toľko údajových položiek, koľko chceme, pokiaľ je k dispozícii RAM.
- Pretože nemusíme vopred špecifikovať, koľko položiek potrebujeme v prepojenom zozname, prepojený zoznam okrem jednoduchého vkladania a odstraňovania šetrí miesto v pamäti. Jediný priestor, ktorý využíva prepojený zoznam, je uloženie ukazovateľa na nasledujúci uzol, čo zvyšuje náklady.
Potom si prejdeme rôzne operácie, ktoré možno vykonať na prepojenom zozname.
1) Vloženie
Prepojený zoznam sa rozšíri akciou pridania. Hoci by sa to mohlo zdať jednoduché, vzhľadom na štruktúru prepojeného zoznamu vieme, že vždy, keď sa pridá údajová položka, musíme zmeniť ďalšie ukazovatele predchádzajúceho a nasledujúceho uzla novej položky, ktorú sme pridali.
Druhým aspektom, na ktorý treba myslieť, je to, kam sa vloží nová údajová položka.
blokovanie reklám na youtube v systéme Android
Existujú tri miesta, kde je možné pridať údajovú položku do prepojeného zoznamu.
a. Počnúc prepojeným zoznamom
Nižšie je pripojený zoznam čísel 2->4->6->8->10. Hlavička smerujúca na uzol 2 bude teraz ukazovať na uzol 1 a ďalší ukazovateľ uzla 1 bude mať pamäťovú adresu uzla 2, ako je znázornené na obrázku nižšie, ak pridáme nový uzol 1 ako prvý uzol v zozname. .
Výsledkom je, že nový prepojený zoznam je 1->2->4->6->8->10.
b. Po danom Node
V tomto prípade dostaneme uzol a musíme za ním pridať nový uzol. Prepojený zoznam bude vyzerať nasledovne, ak sa uzol f pridá do prepojeného zoznamu a->b->c->d->e za uzol c:
Preto skontrolujeme, či je uvedený uzol prítomný v diagrame vyššie. Ak je prítomný, vytvorí sa nový uzol f. Potom nasmerujeme ďalší ukazovateľ uzla c na úplne nový uzol f. Ďalší ukazovateľ uzla f teraz ukazuje na uzol d.
c. Posledná položka prepojeného zoznamu
V treťom prípade sa na koniec prepojeného zoznamu pridá nový uzol. Berte do úvahy prepojený zoznam nižšie: a->b->c->d->e, s pridaním uzla f na konci. Po pridaní uzla sa prepojený zoznam zobrazí takto.
jfx java tutoriál
Výsledkom je vytvorenie nového uzla f. Koncový ukazovateľ vedúci k nule je potom nasmerovaný na f a ďalší ukazovateľ uzla f je nasmerovaný na nulu. V nižšie uvedenom programovacom jazyku sme vygenerovali všetky tri typy funkcií vkladania.
Prepojený zoznam môže byť deklarovaný ako štruktúra alebo ako trieda v C++. Prepojený zoznam deklarovaný ako štruktúra je klasický príkaz v štýle C. Prepojený zoznam sa používa ako trieda v modernom C++, hlavne pri použití štandardnej knižnice šablón.
Štruktúra bola použitá v nasledujúcej aplikácii na deklarovanie a generovanie prepojeného zoznamu. Jeho členmi budú dáta a ukazovateľ na nasledujúci prvok.
Program C++:
t ff
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) Vymazanie
Podobne ako pri vložení, aj vymazanie uzla z prepojeného zoznamu vyžaduje veľa bodov, z ktorých môže byť uzol odstránený. Prvý, posledný alebo k-tý uzol prepojeného zoznamu môžeme odstrániť náhodne. Musíme správne aktualizovať nasledujúci ukazovateľ a všetky ostatné ukazovatele prepojeného zoznamu, aby sa po odstránení zachoval prepojený zoznam.
V nasledujúcej implementácii C++ máme dve metódy vymazania: vymazanie počiatočného uzla zoznamu a vymazanie posledného uzla zoznamu. Začneme pridaním uzlov do hlavy zoznamu. Po každom pridaní a odstránení sa potom zobrazí obsah zoznamu.
Program C++:
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> Počet uzlov
Počas prechádzania prepojeného zoznamu je možné vykonať proces počítania počtu uzlov. V predchádzajúcom prístupe sme videli, že ak sme potrebovali vložiť/vymazať uzol alebo zobraziť obsah prepojeného zoznamu, museli sme prepojený zoznam prechádzať od začiatku.
Nastavenie počítadla a zvyšovanie, ako aj prechádzanie každým uzlom nám poskytne počet uzlov v prepojenom zozname.
Rozdiely medzi Array a Linked listom:
| Pole | Prepojený zoznam |
|---|---|
| Polia majú definovanú veľkosť. | Veľkosť prepojeného zoznamu je variabilná. |
| Vloženie nového prvku je náročné. | Vkladanie a mazanie je jednoduchšie. |
| Prístup je povolený náhodne. | Nie je možný náhodný prístup. |
| Prvky sú relatívne blízko alebo susedia. | Prvky nie sú priľahlé. |
| Pre nasledujúci ukazovateľ nie je potrebná žiadna ďalšia miestnosť. | Nasledujúci ukazovateľ vyžaduje dodatočnú pamäť. |
Funkčnosť
Keďže prepojené zoznamy a polia sú lineárne dátové štruktúry, ktoré obsahujú objekty, možno ich použiť podobným spôsobom pre väčšinu aplikácií.
Nasleduje niekoľko príkladov aplikácií prepojených zoznamov:
- Zásobníky a fronty je možné implementovať pomocou prepojených zoznamov.
- Keď potrebujeme vyjadriť grafy ako susediace zoznamy, môžeme na ich implementáciu použiť prepojený zoznam.
- Na obsiahnutie matematického polynómu môžeme použiť aj prepojený zoznam.
- V prípade hašovania sa na implementáciu segmentov používajú prepojené zoznamy.
- Keď program vyžaduje dynamické prideľovanie pamäte, môžeme použiť prepojený zoznam, pretože prepojené zoznamy sú v tomto prípade efektívnejšie.
Záver
Prepojené zoznamy sú dátové štruktúry používané na uchovávanie dátových prvkov v lineárnej, ale nesúvislej forme. Prepojený zoznam sa skladá z uzlov, z ktorých každý pozostáva z dvoch komponentov. Prvý komponent tvoria dáta, zatiaľ čo druhá polovica má ukazovateľ, ktorý ukladá pamäťovú adresu nasledujúceho člena zoznamu.
Na znak toho, že prepojený zoznam skončil, posledná položka v zozname má svoj ďalší ukazovateľ nastavený na NULL. Hlava je prvou položkou na zozname. Prepojený zoznam umožňuje rôzne akcie, ako je vkladanie, mazanie, prechádzanie atď. Prepojené zoznamy sú pri dynamickom prideľovaní pamäte uprednostňované pred poliami.
Prepojené zoznamy je ťažké vytlačiť alebo prechádzať, pretože k prvkom nemôžeme pristupovať náhodne ako polia. V porovnaní s poliami sú postupy vkladania a vymazania lacnejšie.
V tomto návode sme sa naučili všetko, čo je potrebné vedieť o lineárnych prepojených zoznamoch. Prepojené zoznamy môžu byť tiež dvojito prepojené alebo kruhové. V našich pripravovaných tutoriáloch si tieto zoznamy podrobne prejdeme.