A linkitetty lista on eräänlainen lineaarinen dynaaminen tietorakenne, jota käytämme tietoelementtien tallentamiseen. Taulukot ovat myös eräänlainen lineaarinen tietorakenne, jossa tietokohteet tallennetaan jatkuviin muistilohkoihin.
Toisin kuin taulukot, linkitetyn luettelon ei tarvitse tallentaa tietoelementtejä vierekkäisille muistialueille tai lohkoille.
A linkitetty lista koostuu elementeistä, jotka tunnetaan nimellä 'solmut', jotka on jaettu kahteen osaan. Ensimmäinen komponentti on osa, johon tallennamme todelliset tiedot, ja toinen on osa, johon tallennamme osoittimen seuraavaan solmuun. Tämän tyyppinen rakenne tunnetaan nimellä ' yksittäin linkitetty lista .'
Linkitetty luettelo C++:ssa
Tämä opetusohjelma käy läpi yksittäin linkitetyn luettelon perusteellisesti.
Yksittäin linkitetyn luettelon rakenne on kuvattu alla olevassa kaaviossa
- Kuten yllä olevassa osassa olemme nähneet, linkitetyn luettelon ensimmäinen solmu tunnetaan nimellä 'pää', kun taas viimeistä solmua kutsutaan 'häntäksi'. Koska viimeisessä solmussa ei ole määritetty muistiosoitetta, linkitetyn luettelon viimeisellä solmulla on tyhjä seuraava osoitin.
- Koska jokainen solmu sisältää osoittimen seuraavaan solmuun, linkitetyn luettelon tietoelementtejä ei tarvitse säilyttää vierekkäisissä paikoissa. Solmut voivat olla hajallaan koko muistissa. Koska jokaisella solmulla on sen jälkeen olevan osoite, voimme käyttää solmuja milloin tahansa.
- Voimme nopeasti lisätä ja poistaa datakohteita yhdistettyjen luettelosta. Tämän seurauksena linkitetty luettelo voi kasvaa tai supistua dynaamisesti. Linkitetyssä luettelossa ei ole enimmäismäärää datakohteita, jotka se voi sisältää. Tämän seurauksena voimme lisätä linkitettyyn luetteloon niin monta datakohdetta kuin haluamme, kunhan RAM-muistia on käytettävissä.
- Koska meidän ei tarvitse määrittää etukäteen, kuinka monta kohdetta tarvitsemme linkitetyssä luettelossa, linkitetty luettelo säästää muistitilaa sen lisäksi, että se on helppo lisätä ja poistaa. Ainoa linkitetyn luettelon käyttämä tila on tallentaa osoitin seuraavaan solmuun, mikä lisää kustannuksia.
Tämän jälkeen käymme läpi erilaisia toimintoja, jotka voidaan suorittaa linkitetyssä luettelossa.
1) Lisäys
Linkitettyä luetteloa laajennetaan lisäämällä siihen. Vaikka se näyttää yksinkertaiselta, linkitetyn luettelon rakenteen vuoksi tiedämme, että joka kerta kun tietokohde lisätään, meidän on muutettava lisäämämme uuden kohteen edellisen ja seuraavan solmun seuraavat osoittimet.
Toinen huomioitava näkökohta on se, mihin uusi tietokohde lisätään.
Tietokohteen voi lisätä linkitettyyn luetteloon kolmessa paikassa.
a. Aloita linkitetystä luettelosta
Alla on yhdistetty luettelo numeroista 2->4->6->8->10. Solmuun 2 osoittava pää osoittaa nyt solmuun 1 ja solmun 1 seuraavalla osoittimella on solmun 2 muistiosoite, kuten alla olevassa kuvassa näkyy, jos lisäämme uuden solmun 1 luettelon ensimmäiseksi solmuksi. .
Tämän seurauksena uusi linkitetty lista on 1->2->4->6->8->10.
b. Annetun solmun jälkeen
Tässä tapauksessa meille annetaan solmu ja sen taakse on lisättävä uusi solmu. Linkitetty luettelo näyttää tältä, jos solmu f lisätään linkitettyyn luetteloon a->b->c->d->e solmun c jälkeen:
Siksi tarkistamme, onko määritetty solmu yllä olevassa kaaviossa. Jos se on olemassa, luodaan uusi solmu f. Sen jälkeen osoitamme solmun c seuraavan osoittimen aivan uuteen solmuun f. Solmun f seuraava osoitin osoittaa nyt solmuun d.
c. Linkitetyn luettelon viimeinen kohde
Kolmannessa tapauksessa uusi solmu lisätään linkitetyn luettelon loppuun. Ota huomioon alla oleva linkitetty luettelo: a->b->c->d->e, lisäämällä solmu f loppuun. Solmun lisäämisen jälkeen linkitetty luettelo näyttää tältä.
Tämän seurauksena rakennamme uuden solmun f. Nollaan johtava häntäosoitin osoitetaan sitten kohtaan f, ja solmun f seuraava osoitin osoitetaan nollaan. Alla olevalla ohjelmointikielellä olemme luoneet kaikki kolme lisäystoimintotyyppiä.
Linkitetty lista voidaan ilmoittaa C++:ssa rakenteena tai luokkana. Rakenteeksi ilmoitettu linkitetty lista on klassinen C-tyylinen lause. Linkitettyä listaa käytetään luokkana nykyaikaisessa C++:ssa, lähinnä käytettäessä vakiomallikirjastoa.
Rakennetta käytettiin seuraavassa sovelluksessa linkitetyn luettelon ilmoittamiseen ja luomiseen. Sen jäsenet ovat dataa ja osoitin seuraavaan elementtiin.
C++-ohjelma:
#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) Poistaminen
Samoin kuin lisääminen, solmun poistaminen linkitetystä luettelosta vaatii monia pisteitä, joista solmu voidaan poistaa. Voimme poistaa linkitetyn luettelon ensimmäisen, viimeisen tai k:nnen solmun satunnaisesti. Meidän on päivitettävä seuraava osoitin ja kaikki muut linkitetyn luettelon osoittimet oikein, jotta linkitetty luettelo säilyy poiston jälkeen.
Seuraavassa C++-toteutuksessa meillä on kaksi poistotapaa: luettelon alkuperäisen solmun poistaminen ja luettelon viimeisen solmun poistaminen. Aloitamme lisäämällä solmuja luettelon päähän. Luettelon sisältö näytetään sitten jokaisen lisäyksen ja poiston jälkeen.
C++-ohjelma:
#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> Solmujen määrä
Linkitettyä luetteloa kulkiessa voidaan suorittaa solmujen lukumäärän laskentaprosessi. Edellisessä lähestymistavassa näimme, että jos meidän piti lisätä/poistaa solmu tai näyttää linkitetyn luettelon sisältö, meidän piti kulkea linkitetty luettelo alusta alkaen.
Laskurin asettaminen ja lisääminen sekä jokaisen solmun läpi kulkeminen antaa meille linkitetyn luettelon solmujen määrän.
Erot taulukon ja linkitetyn luettelon välillä:
| Array | Linkitetty lista |
|---|---|
| Matriiseilla on määritelty koko. | Linkitetyn luettelon koko vaihtelee. |
| Uuden elementin lisääminen on vaikeaa. | Lisääminen ja poistaminen on yksinkertaisempaa. |
| Pääsy on sallittu satunnaisesti. | Satunnainen pääsy ei ole mahdollista. |
| Elementit ovat suhteellisen lähellä tai vierekkäin. | Elementit eivät ole vierekkäisiä. |
| Seuraavalle osoittimelle ei tarvita lisätilaa. | Seuraava osoitin vaatii lisämuistia. |
Toiminnallisuus
Koska linkitetyt luettelot ja taulukot ovat molemmat lineaarisia tietorakenteita, joissa on objekteja, niitä voidaan käyttää samalla tavalla useimmissa sovelluksissa.
Seuraavassa on esimerkkejä linkitetyistä luettelosovelluksista:
- Pinot ja jonot voidaan toteuttaa linkitettyjen listojen avulla.
- Kun meidän on ilmaista graafit vierekkäisyysluetteloina, voimme käyttää linkitettyä luetteloa niiden toteuttamiseen.
- Voimme myös käyttää linkitettyä listaa sisältämään matemaattisen polynomin.
- Hajautustapauksessa segmenttien toteuttamiseen käytetään linkitettyjä listoja.
- Kun ohjelma vaatii dynaamista muistin varausta, voimme käyttää linkitettyä listaa, koska linkitetyt listat ovat tässä tapauksessa tehokkaampia.
Johtopäätös
Linkitetyt luettelot ovat tietorakenteita, joita käytetään pitämään tietoelementtejä lineaarisessa mutta ei-viereisessä muodossa. Linkitetty luettelo koostuu solmuista, joissa kussakin on kaksi komponenttia. Ensimmäinen komponentti koostuu tiedoista, kun taas toisessa puoliskossa on osoitin, joka tallentaa luettelon seuraavan jäsenen muistiosoitteen.
Merkiksi siitä, että linkitetty luettelo on päättynyt, luettelon viimeisen kohteen seuraava osoitin on asetettu arvoon NULL. Pää on luettelon ensimmäinen kohta. Linkitetty luettelo mahdollistaa erilaisia toimintoja, kuten lisäämisen, poistamisen, läpikäynnin ja niin edelleen. Linkitettyjä luetteloita suositaan taulukoiden sijaan dynaamista muistin varaamista varten.
java-lajittelutaulukko
Linkitettyjä luetteloita on vaikea tulostaa tai käydä läpi, koska emme voi käyttää elementtejä satunnaisesti kuten taulukoita. Matriisiin verrattuna lisäys-poistotoimenpiteet ovat halvempia.
Tässä opetusohjelmassa opimme kaiken lineaarisista linkitetyistä luetteloista. Linkitetyt luettelot voivat olla myös kaksinkertaisia tai pyöreitä. Tulevissa opetusohjelmissamme käymme nämä luettelot läpi yksityiskohtaisesti.