A susietas sąrašas yra linijinė dinaminė duomenų struktūra, kurią naudojame duomenų elementams saugoti. Masyvai taip pat yra linijinės duomenų struktūros tipas, kai duomenų elementai saugomi ištisiniuose atminties blokuose.
Skirtingai nuo masyvų, susietame sąraše nereikia saugoti duomenų elementų gretimuose atminties regionuose ar blokuose.
A susietas sąrašas susideda iš elementų, žinomų kaip „mazgai“, kurie yra padalinti į dvi dalis. Pirmasis komponentas yra dalis, kurioje saugome tikruosius duomenis, o antrasis yra dalis, kurioje saugome žymeklį į kitą mazgą. Šio tipo struktūra yra žinoma kaip ' atskirai susietas sąrašas .'
Susietas sąrašas C++
Šioje pamokoje bus išsamiai aprašytas atskirai susietas sąrašas.
Toliau pateiktoje diagramoje pavaizduota atskirai susieto sąrašo struktūra
- Kaip matėme anksčiau pateiktoje dalyje, pirmasis susieto sąrašo mazgas yra žinomas kaip „galva“, o paskutinis mazgas vadinamas „uodega“. Kadangi paskutiniame mazge nenurodytas atminties adresas, galutinis susieto sąrašo mazgas turės nulinį kitą žymeklį.
- Kadangi kiekviename mazge yra žymeklis į kitą mazgą, duomenų elementų susietame sąraše nereikia laikyti gretimose vietose. Mazgai gali būti išsklaidyti visoje atmintyje. Kadangi kiekvienas mazgas turi po jo esančio adresą, galime pasiekti mazgus kada tik norime.
- Galime greitai pridėti ir pašalinti duomenų elementus iš prijungto sąrašo. Dėl to susietas sąrašas gali dinamiškai didėti arba susitraukti. Susietame sąraše nėra maksimalaus jame galinčių būti duomenų elementų kiekio. Dėl to į susietą sąrašą galime įtraukti tiek duomenų elementų, kiek norime, jei tik yra RAM.
- Kadangi mes neturime iš anksto nurodyti, kiek elementų mums reikia susietame sąraše, susietas sąrašas sutaupo vietos atmintyje, be to, jį paprasta įterpti ir ištrinti. Vienintelė vieta, kurią naudoja susietas sąrašas, yra saugoti žymeklį į kitą mazgą, o tai šiek tiek kainuoja.
Po to apžvelgsime įvairias operacijas, kurios gali būti atliekamos susietame sąraše.
kaip java paversti sveikąjį skaičių į eilutę
1) Įdėjimas
Susietas sąrašas išplečiamas jį papildant. Nors tai atrodo paprasta, atsižvelgiant į susieto sąrašo struktūrą, žinome, kad kiekvieną kartą, kai pridedamas duomenų elementas, turime pakeisti kitas ankstesnio ir kito naujojo pridėto elemento mazgų nuorodas.
Antrasis aspektas, apie kurį reikia galvoti, yra vieta, kur bus įterptas naujas duomenų elementas.
Yra trys vietos, kur duomenų elementą galima įtraukti į susietą sąrašą.
a. Pradedant nuo susieto sąrašo
Žemiau yra sujungtas skaičių 2->4->6->8->10 sąrašas. Galvutė, nukreipianti į 2 mazgą, dabar nurodys 1 mazgą, o kita 1 mazgo rodyklė turės 2 mazgo atminties adresą, kaip parodyta toliau pateiktoje iliustracijoje, jei įtrauksime naują mazgą 1 kaip pirmąjį mazgą sąraše. .
kibirkšties pamoka
Dėl to naujas susietas sąrašas yra 1->2->4->6->8->10.
b. Po nurodyto Mazgo
Šiuo atveju mums suteikiamas mazgas ir už jo turime pridėti naują mazgą. Susietas sąrašas atrodys taip, jei mazgas f bus pridėtas prie susieto sąrašo a->b->c->d->e po mazgo c:
Todėl patikriname, ar nurodytas mazgas yra aukščiau esančioje diagramoje. Jei jis yra, sukuriamas naujas mazgas f. Po to kitą mazgo c žymeklį nukreipiame į visiškai naują mazgą f. Kitas mazgo f rodyklė dabar rodo mazgą d.
c. Paskutinis susietojo sąrašo elementas
Trečiuoju atveju į susieto sąrašo pabaigą įtraukiamas naujas mazgas. Atsižvelkite į toliau pateiktą susietą sąrašą: a->b->c->d->e, pabaigoje pridedant mazgą f. Pridėjus mazgą, susietas sąrašas pasirodys taip.
latekso stalas
Dėl to sukonstruojame naują mazgą f. Tada uodegos rodyklė, vedanti į nulį, yra nukreipta į f, o kita mazgo f rodyklė nukreipta į nulį. Žemiau esančioje programavimo kalboje sugeneravome visų trijų tipų įterpimo funkcijas.
Susietas sąrašas gali būti deklaruojamas kaip struktūra arba kaip klasė C++. Susietas sąrašas, paskelbtas kaip struktūra, yra klasikinis C stiliaus teiginys. Susietas sąrašas naudojamas kaip klasė šiuolaikiniame C++, daugiausia naudojant standartinę šablonų biblioteką.
Struktūra buvo naudojama šioje programoje, kad būtų galima deklaruoti ir generuoti susietą sąrašą. Jos nariai bus duomenys ir rodyklė į kitą elementą.
C++ programa:
#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) Ištrynimas
Panašiai kaip ir įterpiant, norint ištrinti mazgą iš susieto sąrašo, reikia daug taškų, iš kurių mazgas gali būti pašalintas. Galime atsitiktinai pašalinti susieto sąrašo pirmąjį, paskutinį arba k-ąjį mazgą. Turime teisingai atnaujinti kitą žymeklį ir visas kitas susieto sąrašo nuorodas, kad ištrynus susietą sąrašą išliktų.
Šiame C++ diegime turime du ištrynimo būdus: ištrinkite pradinį sąrašo mazgą ir ištrinkite paskutinį sąrašo mazgą. Pradedame įtraukdami mazgus prie sąrašo pradžios. Sąrašo turinys rodomas po kiekvieno papildymo ir ištrynimo.
C++ programa:
#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> Mazgų skaičius
Naršydami susietą sąrašą, galima atlikti mazgų skaičiavimo procesą. Taikant ankstesnį metodą, matėme, kad jei mums reikia įterpti / ištrinti mazgą arba rodyti susieto sąrašo turinį, turime pereiti susietą sąrašą nuo pat pradžių.
Nustačius skaitiklį ir padidinus, taip pat perėjus kiekvieną mazgą, bus pateiktas mazgų skaičius susietame sąraše.
Masyvo ir susieto sąrašo skirtumai:
| Masyvas | Susietas sąrašas |
|---|---|
| Masyvai turi apibrėžtą dydį. | Susieto sąrašo dydis yra kintamas. |
| Sunku įterpti naują elementą. | Įterpimas ir ištrynimas yra paprastesnis. |
| Prieiga leidžiama atsitiktinai. | Neįmanoma atsitiktinės prieigos. |
| Elementai yra santykinai arti arba gretimi. | Elementai nėra gretimi. |
| Toliau nurodytai žymekliui papildomos vietos nereikia. | Šiai žymekliui reikia papildomos atminties. |
Funkcionalumas
Kadangi susieti sąrašai ir masyvai yra linijinės duomenų struktūros, kuriose yra objektai, jie gali būti naudojami panašiai daugumoje programų.
Toliau pateikiami keli susietų sąrašų programų pavyzdžiai:
sąrašas surūšiuotas java
- Skaičius ir eiles galima įdiegti naudojant susietus sąrašus.
- Kai mums reikia išreikšti grafikus kaip gretimų sąrašus, galime naudoti susietą sąrašą, kad juos įgyvendintume.
- Taip pat galime naudoti susietą sąrašą, kad būtų įtrauktas matematinis daugianomas.
- Maišos atveju naudojami susieti sąrašai segmentams įgyvendinti.
- Kai programai reikalingas dinaminis atminties paskirstymas, galime naudoti susietą sąrašą, nes susieti sąrašai šiuo atveju yra efektyvesni.
Išvada
Susieti sąrašai yra duomenų struktūros, naudojamos duomenų elementams laikyti linijine, bet negretima forma. Susietą sąrašą sudaro mazgai su dviem komponentais. Pirmąjį komponentą sudaro duomenys, o antroje pusėje yra rodyklė, kurioje saugomas kito sąrašo nario atminties adresas.
Kaip ženklas, kad susietas sąrašas baigėsi, paskutinis sąrašo elementas turi kitą žymeklį į NULL. Galva yra pirmasis sąrašo elementas. Susietas sąrašas leidžia atlikti įvairius veiksmus, tokius kaip įterpimas, trynimas, perėjimas ir pan. Dinaminiam atminties paskirstymui pirmenybė teikiama susietiems sąrašams, o ne masyvams.
Susietus sąrašus sunku atspausdinti arba perskaityti, nes negalime atsitiktinai pasiekti elementų, kaip masyvų. Palyginti su masyvais, įterpimo ir ištrynimo procedūros yra pigesnės.
Šioje pamokoje sužinojome viską, ką reikia žinoti apie linijinius susietus sąrašus. Susieti sąrašai taip pat gali būti dvigubai susieti arba žiediniai. Būsimuose vadovėliuose mes išsamiai išnagrinėsime šiuos sąrašus.