A povezan seznam je neke vrste linearna dinamična podatkovna struktura, ki jo uporabljamo za shranjevanje podatkovnih elementov. Nizi so tudi vrsta linearne podatkovne strukture, kjer so podatkovni elementi shranjeni v neprekinjenih pomnilniških blokih.
Za razliko od nizov, povezanemu seznamu ni treba shranjevati podatkovnih elementov v sosednjih pomnilniških regijah ali blokih.
A povezan seznam je sestavljen iz elementov, znanih kot 'vozlišča', ki so razdeljeni na dva dela. Prva komponenta je del, kjer shranimo dejanske podatke, druga pa del, kjer shranimo kazalec na naslednje vozlišče. Ta vrsta strukture je znana kot ' enojno povezan seznam .'
Povezan seznam v C++
Ta vadnica bo podrobno obravnavala posamezno povezan seznam.
Struktura enojno povezanega seznama je prikazana v spodnjem diagramu
- Kot smo videli v zgornjem delu, je prvo vozlišče povezanega seznama znano kot 'glava', medtem ko se zadnje vozlišče imenuje 'rep'. Ker v zadnjem vozlišču ni določen pomnilniški naslov, bo imelo končno vozlišče povezanega seznama ničelni naslednji kazalec.
- Ker vsako vozlišče vključuje kazalec na naslednje vozlišče, podatkovnih elementov na povezanem seznamu ni treba obdržati na sosednjih lokacijah. Vozlišča so lahko razpršena po celotnem pomnilniku. Ker ima vsako vozlišče naslov tistega za njim, lahko dostopamo do vozlišč, kadar koli želimo.
- Hitro lahko dodajamo in odstranjujemo podatke s povezanega seznama. Posledično se lahko povezani seznam dinamično poveča ali skrči. Povezani seznam nima največje količine podatkov, ki jih lahko vsebuje. Posledično lahko na povezani seznam dodamo poljubno število podatkovnih elementov, če je na voljo RAM.
- Ker nam ni treba vnaprej določiti, koliko elementov potrebujemo na povezanem seznamu, povezani seznam prihrani prostor v pomnilniku poleg tega, da ga je preprosto vstaviti in izbrisati. Edini prostor, ki ga uporablja povezani seznam, je shranjevanje kazalca na naslednje vozlišče, kar doda nekaj stroškov.
Nato bomo preučili različne operacije, ki jih je mogoče izvesti na povezanem seznamu.
1) Vstavljanje
Povezani seznam se razširi z dejanjem dodajanja nanj. Čeprav se zdi preprosto, glede na strukturo povezanega seznama vemo, da moramo vsakič, ko dodamo podatkovno postavko, spremeniti naslednje kazalce prejšnjega in naslednjega vozlišča nove postavke, ki smo jo dodali.
Drugi vidik, o katerem je treba razmisliti, je, kam bo vstavljena nova podatkovna postavka.
Obstajajo tri mesta, kjer lahko dodate podatkovno postavko na povezani seznam.
a. Začenši s povezanim seznamom
Spodaj je povezan seznam števil 2->4->6->8->10. Glava, ki kaže na vozlišče 2, bo zdaj kazala na vozlišče 1, naslednji kazalec vozlišča 1 pa bo imel pomnilniški naslov vozlišča 2, kot je prikazano na spodnji sliki, če dodamo novo vozlišče 1 kot prvo vozlišče na seznamu .
Posledično je novi povezani seznam 1->2->4->6->8->10.
b. Po danem vozlišču
V tem primeru nam je dano vozlišče in za njim moramo dodati novo vozlišče. Povezani seznam bo izgledal takole, če je vozlišče f dodano povezanemu seznamu a->b->c->d->e za vozliščem c:
Zato preverimo, ali je navedeno vozlišče prisotno v zgornjem diagramu. Če je prisoten, se ustvari novo vozlišče f. Po tem usmerimo naslednji kazalec vozlišča c na popolnoma novo vozlišče f. Naslednji kazalec vozlišča f zdaj kaže na vozlišče d.
c. Zadnji element povezanega seznama
V tretjem primeru se novo vozlišče doda na konec povezanega seznama. Upoštevajte spodnji povezani seznam: a->b->c->d->e, z dodatkom vozlišča f na koncu. Po dodajanju vozlišča bo povezan seznam prikazan takole.
Kot rezultat, zgradimo novo vozlišče f. Kazalec repa, ki vodi do ničle, je nato usmerjen na f, naslednji kazalec vozlišča f pa je usmerjen na ničlo. V spodnjem programskem jeziku smo ustvarili vse tri vrste funkcij vstavljanja.
Povezani seznam je mogoče deklarirati kot strukturo ali kot razred v C++. Povezan seznam, deklariran kot struktura, je klasična izjava v slogu C. Povezani seznam se uporablja kot razred v sodobnem C++, predvsem pri uporabi standardne knjižnice predlog.
Struktura je bila uporabljena v naslednji aplikaciji za deklaracijo in ustvarjanje povezanega seznama. Njegovi člani bodo podatki in kazalec na naslednji element.
Program C++:
#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) Izbris
Podobno kot pri vstavljanju brisanje vozlišča s povezanega seznama zahteva veliko točk, iz katerih bi lahko vozlišče odstranili. Naključno lahko odstranimo prvo, zadnje ali k-to vozlišče povezanega seznama. Pravilno moramo posodobiti naslednji kazalec in vse druge kazalce povezanega seznama, da ohranimo povezani seznam po izbrisu.
V naslednji izvedbi C++ imamo dve metodi brisanja: brisanje začetnega vozlišča seznama in brisanje zadnjega vozlišča seznama. Začnemo z dodajanjem vozlišč na glavo seznama. Vsebina seznama se nato prikaže po vsakem dodajanju in brisanju.
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> Število vozlišč
Med prečkanjem povezanega seznama je mogoče izvesti postopek štetja števila vozlišč. V prejšnjem pristopu smo videli, da smo morali, če smo morali vstaviti/izbrisati vozlišče ali prikazati vsebino povezanega seznama, prečkati povezani seznam od začetka.
Z nastavitvijo števca in povečevanjem ter prečkanjem vsakega vozlišča bomo dobili število vozlišč na povezanem seznamu.
zasebna proti javni java
Razlike med nizom in povezanim seznamom:
| Array | Povezan seznam |
|---|---|
| Nizi imajo določeno velikost. | Velikost povezanega seznama je spremenljiva. |
| Vstavljanje novega elementa je težko. | Vstavljanje in brisanje sta enostavnejša. |
| Dostop je dovoljen naključno. | Naključni dostop ni mogoč. |
| Elementi so relativno blizu ali sosednji. | Elementi niso sosednji. |
| Za naslednji kazalec ni potreben dodaten prostor. | Naslednji kazalec zahteva dodaten pomnilnik. |
Funkcionalnost
Ker so povezani seznami in polja tako linearne podatkovne strukture, ki vsebujejo predmete, jih je mogoče uporabiti na podoben način za večino aplikacij.
Sledi nekaj primerov aplikacij povezanih seznamov:
- Sklade in čakalne vrste je mogoče implementirati z uporabo povezanih seznamov.
- Ko moramo grafe izraziti kot sezname sosednosti, lahko za njihovo implementacijo uporabimo povezan seznam.
- Za matematični polinom lahko uporabimo tudi povezan seznam.
- V primeru zgoščevanja se za implementacijo veder uporabljajo povezani seznami.
- Ko program zahteva dinamično dodelitev pomnilnika, lahko uporabimo povezani seznam, ker so povezani seznami v tem primeru učinkovitejši.
Zaključek
Povezani seznami so podatkovne strukture, ki se uporabljajo za shranjevanje podatkovnih elementov v linearni, vendar nesosednji obliki. Povezani seznam je sestavljen iz vozlišč z dvema komponentama. Prva komponenta je sestavljena iz podatkov, medtem ko ima druga polovica kazalec, ki shrani pomnilniški naslov naslednjega člana seznama.
Kot znak, da se je povezani seznam končal, ima zadnji element na seznamu naslednji kazalec nastavljen na NULL. Glava je prvi element na seznamu. Povezani seznam omogoča različna dejanja, kot so vstavljanje, brisanje, prečkanje itd. Povezani seznami imajo prednost pred nizi za dinamično dodeljevanje pomnilnika.
Povezane sezname je težko natisniti ali prečkati, ker do elementov ne moremo dostopati naključno, kot do nizov. V primerjavi z nizi so postopki vstavljanja-brisanja cenejši.
V tej vadnici smo izvedeli vse, kar je treba vedeti o linearno povezanih seznamih. Povezani seznami so lahko tudi dvojno povezani ali krožni. V naših prihodnjih vadnicah bomo te sezname podrobno preučili.