A lista legată este un fel de structură de date dinamică liniară pe care o folosim pentru a stoca elemente de date. Matricele sunt, de asemenea, un tip de structură de date liniară în care elementele de date sunt stocate în blocuri de memorie continue.
Spre deosebire de matrice, lista legată nu trebuie să stocheze elemente de date în regiuni sau blocuri de memorie contigue.
A lista legată este compus din elemente cunoscute sub numele de „Noduri” care sunt împărțite în două părți. Prima componentă este partea în care stocăm datele reale, iar a doua este o parte în care stocăm indicatorul către următorul nod. Acest tip de structură este cunoscut sub numele de „ listă legată individual .'
Lista legată în C++
Acest tutorial va parcurge în profunzime lista legată individual.
Structura unei liste cu legături unice este ilustrată în diagrama de mai jos
- După cum am văzut în partea de mai sus, primul nod al listei legate este cunoscut sub numele de „cap”, în timp ce ultimul nod este numit „coada”. Pentru că nu este specificată nicio adresă de memorie în ultimul nod, nodul final al listei legate va avea un indicator nul următor.
- Deoarece fiecare nod include un pointer către următorul nod, elementele de date din lista legată nu trebuie să fie păstrate în locații învecinate. Nodurile pot fi dispersate în memorie. Deoarece fiecare nod are adresa celui de după el, putem accesa nodurile oricând dorim.
- Putem adăuga și elimina rapid elemente de date din lista conectată. Ca rezultat, lista legată poate crește sau se poate contracta dinamic. Lista legată nu are un număr maxim de elemente de date pe care le poate conține. Ca rezultat, putem adăuga oricâte elemente de date dorim în lista legată, atâta timp cât există RAM disponibilă.
- Deoarece nu trebuie să specificăm în prealabil de câte articole avem nevoie în lista legată, lista legată economisește spațiu de memorie pe lângă faptul că este ușor de inserat și șters. Singurul spațiu folosit de o listă legată este stocarea indicatorului către următorul nod, ceea ce adaugă un anumit cost.
În continuare, vom trece peste diferitele operațiuni care pot fi efectuate pe o listă legată.
1) Inserare
Lista legată este extinsă prin acțiunea de a adăuga la ea. Deși ar părea simplu, având în vedere structura listei legate, știm că de fiecare dată când se adaugă un element de date, trebuie să schimbăm următorii pointeri ai nodurilor precedente și următoare ale noului element pe care l-am adăugat.
Unde va fi introdus noul element de date este al doilea aspect la care trebuie să vă gândiți.
instalați maven
Există trei locuri în care un element de date poate fi adăugat la lista legată.
A. Începând cu lista legată
Mai jos este o listă conectată a numerelor 2->4->6->8->10. Capul care indică spre nodul 2 va indica acum către nodul 1, iar următorul pointer al nodului 1 va avea adresa de memorie a nodului 2, așa cum se arată în ilustrația de mai jos, dacă adăugăm un nou nod 1 ca primul nod din listă. .
Ca rezultat, noua listă legată este 1->2->4->6->8->10.
descărcare xvideoservicethief ubuntu 14.04
b. După Nodul dat
În acest caz, ni se oferă un nod și trebuie să adăugăm un nou nod în spatele lui. Lista legată va arăta după cum urmează dacă nodul f este adăugat la lista legată a->b->c->d->e după nodul c:
Prin urmare, verificăm dacă nodul specificat este prezent în diagrama de mai sus. Dacă este prezent, se creează un nou nod f. După aceea, îndreptăm următorul pointer al nodului c către nodul f. Următorul indicator al nodului f indică acum către nodul d.
c. Ultimul articol al listei conectate
În al treilea caz, un nou nod este adăugat la sfârșitul listei legate. Luați în considerare lista legată de mai jos: a->b->c->d->e, cu adăugarea nodului f la sfârșit. După adăugarea nodului, lista legată va apărea astfel.
Ca rezultat, construim un nou nod f. Indicatorul de coadă care duce la null este apoi indicat spre f, iar următorul pointer al nodului f este indicat spre null. În limbajul de programare de mai jos, am generat toate cele trei tipuri de funcții de inserare.
O listă legată poate fi declarată ca structură sau ca clasă în C++. O listă legată declarată ca structură este o declarație clasică în stil C. O listă legată este folosită ca o clasă în C++ modern, în principal atunci când se utilizează biblioteca standard de șabloane.
Structura a fost folosită în următoarea aplicație pentru a declara și genera o listă legată. Membrii săi vor fi date și un pointer către următorul element.
Programul 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) Ștergere
Similar cu inserarea, ștergerea unui nod dintr-o listă legată necesită multe puncte din care nodul ar putea fi eliminat. Putem elimina la întâmplare primul, ultimul sau k-lea nod al listei legate. Trebuie să actualizăm corect următorul pointer și toți ceilalți pointeri de listă legată pentru a menține lista legată după ștergere.
În următoarea implementare C++, avem două metode de ștergere: ștergerea nodului inițial al listei și ștergerea ultimului nod al listei. Începem prin a adăuga noduri în capul listei. Conținutul listei este apoi afișat după fiecare adăugare și ștergere.
Programul 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> Număr de noduri
În timpul parcurgerii listei legate, procesul de numărare a numărului de noduri poate fi efectuat. În abordarea anterioară, am văzut că dacă trebuie să inserăm/ștergem un nod sau să afișăm conținutul listei legate, trebuia să parcurgem lista legată de la început.
Setarea unui contor și creșterea, precum și prin parcurgerea fiecărui nod, ne va furniza numărul de noduri din lista legată.
java parse string la int
Diferențele dintre Array și Lista Linked:
| Matrice | Lista legată |
|---|---|
| Matricele au o dimensiune definită. | Mărimea listei legate este variabilă. |
| Introducerea unui nou element este dificilă. | Inserarea și ștergerea sunt mai simple. |
| Accesul este permis la întâmplare. | Nu este posibil acces aleatoriu. |
| Elementele sunt relativ apropiate sau învecinate. | Elementele nu sunt învecinate. |
| Nu este nevoie de încăpere suplimentară pentru următorul indicator. | Următorul indicator necesită memorie suplimentară. |
Funcționalitate
Deoarece listele și matricele legate sunt ambele structuri de date liniare care dețin obiecte, ele pot fi utilizate în moduri similare pentru majoritatea aplicațiilor.
Următoarele sunt câteva exemple de aplicații cu liste legate:
- Stivele și cozile pot fi implementate folosind liste legate.
- Când trebuie să exprimăm grafice ca liste de adiacență, putem folosi o listă legată pentru a le implementa.
- De asemenea, putem folosi o listă legată pentru a conține un polinom matematic.
- În cazul hashing-ului, listele legate sunt folosite pentru a implementa gălețile.
- Când un program necesită alocarea dinamică a memoriei, putem utiliza o listă legată, deoarece listele legate sunt mai eficiente în acest caz.
Concluzie
Listele legate sunt structuri de date utilizate pentru a păstra elementele de date într-o formă liniară, dar necontigue. O listă legată este alcătuită din noduri cu două componente fiecare. Prima componentă este formată din date, în timp ce a doua jumătate are un pointer care stochează adresa de memorie a următorului membru al listei.
Ca semn că lista legată s-a încheiat, ultimul element din listă are următorul indicator setat la NULL. Capul este primul element de pe listă. Lista legată permite o varietate de acțiuni, cum ar fi inserarea, ștergerea, traversarea și așa mai departe. Listele legate sunt favorizate față de matrice pentru alocarea dinamică a memoriei.
Listele legate sunt greu de imprimat sau de parcurs, deoarece nu putem accesa elementele la întâmplare, precum matricele. În comparație cu matricele, procedurile de inserare-ștergere sunt mai puțin costisitoare.
În acest tutorial, am învățat tot ce trebuie să știți despre listele legate liniare. Listele legate pot fi, de asemenea, dublu legate sau circulare. În tutorialele noastre viitoare, vom parcurge aceste liste în detaliu.