A llista enllaçada és una mena d'estructura de dades dinàmiques lineals que utilitzem per emmagatzemar elements de dades. Les matrius també són un tipus d'estructura de dades lineal on els elements de dades s'emmagatzemen en blocs de memòria continus.
A diferència de les matrius, la llista enllaçada no necessita emmagatzemar elements de dades en regions o blocs de memòria contigües.
A llista enllaçada està compost per elements coneguts com a 'Nodes' que es divideixen en dues parts. El primer component és la part on emmagatzemem les dades reals, i el segon és una part on emmagatzemem el punter al següent node. Aquest tipus d'estructura es coneix com a ' llista enllaçada individualment .'
Llista enllaçada en C++
Aquest tutorial repassarà en profunditat la llista enllaçada individualment.
L'estructura d'una llista enllaçada individualment s'il·lustra al diagrama següent
- Com hem vist a la part anterior, el primer node de la llista enllaçada es coneix com a 'cap', mentre que l'últim node s'anomena 'cua'. Perquè no s'especifica cap adreça de memòria a l'últim node, el node final de la llista enllaçada tindrà un punter següent nul.
- Com que cada node inclou un punter al següent node, els elements de dades de la llista enllaçada no cal que es conserven en ubicacions contigües. Els nodes poden estar dispersos per tota la memòria. Com que cada node té l'adreça del següent, podem accedir als nodes quan vulguem.
- Podem afegir i eliminar ràpidament elements de dades de la llista connectada. Com a resultat, la llista enllaçada pot augmentar o contraure dinàmicament. La llista enllaçada no té la quantitat màxima d'elements de dades que pot contenir. Com a resultat, podem afegir tants elements de dades com vulguem a la llista enllaçada sempre que hi hagi RAM disponible.
- Com que no hem d'especificar quants elements necessitem a la llista enllaçada per endavant, la llista enllaçada estalvia espai de memòria a més de ser fàcil d'inserir i eliminar. L'únic espai utilitzat per una llista enllaçada és emmagatzemar el punter al següent node, cosa que afegeix un cost.
A continuació, repassarem les diferents operacions que es poden realitzar en una llista enllaçada.
1) Inserció
La llista enllaçada s'amplia amb l'acció d'afegir-hi. Encara que sembli senzill, donada l'estructura de la llista enllaçada, sabem que cada vegada que s'afegeix una dada, hem de canviar els següents punters dels nodes anterior i següent del nou element que hem afegit.
On s'inserirà el nou element de dades és el segon aspecte a pensar.
Hi ha tres llocs on es pot afegir un element de dades a la llista enllaçada.
a. Començant per la llista enllaçada
A continuació es mostra una llista connectada dels números 2->4->6->8->10. El cap que apunta al node 2 ara apuntarà al node 1, i el següent punter del node 1 tindrà l'adreça de memòria del node 2, tal com es mostra a la il·lustració següent, si afegim un nou node 1 com a primer node de la llista. .
Com a resultat, la nova llista enllaçada és 1->2->4->6->8->10.
b. Després del node donat
En aquest cas, se'ns dóna un node i hem d'afegir un nou node darrere. La llista enllaçada semblarà de la següent manera si el node f s'afegeix a la llista enllaçada a->b->c->d->e després del node c:
json des de l'objecte java
Per tant, comprovem si el node especificat està present al diagrama anterior. Si està present, es crea un nou node f. Després d'això, apuntem el següent punter del node c al nou node f. El següent punter del node f apunta ara al node d.
c. L'últim element de la llista enllaçada
En el tercer cas, s'afegeix un nou node al final de la llista enllaçada. Tingueu en compte la llista enllaçada següent: a->b->c->d->e, amb l'addició del node f al final. Després d'afegir el node, la llista enllaçada apareixerà així.
Com a resultat, construïm un nou node f. El punter de cua que porta a null s'apunta a f, i el punter següent del node f apunta a nul. Al llenguatge de programació següent, hem generat els tres tipus de funcions d'inserció.
Una llista enllaçada es pot declarar com a estructura o com a classe en C++. Una llista enllaçada declarada com a estructura és una declaració clàssica d'estil C. Una llista enllaçada s'utilitza com a classe en C++ modern, principalment quan s'utilitza la biblioteca de plantilles estàndard.
L'estructura es va utilitzar a l'aplicació següent per declarar i generar una llista enllaçada. Els seus membres seran dades i un punter a l'element següent.
Programa 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) Eliminació
De manera similar a la inserció, la supressió d'un node d'una llista enllaçada requereix molts punts des dels quals es podria eliminar el node. Podem eliminar el primer, l'últim o el kè node de la llista enllaçada a l'atzar. Hem d'actualitzar correctament el punter següent i tots els altres punters de llista enllaçada per tal de mantenir la llista enllaçada després de la supressió.
A la següent implementació de C++, tenim dos mètodes d'eliminació: suprimir el node inicial de la llista i suprimir l'últim node de la llista. Comencem afegint nodes al capçal de la llista. Després de cada addició i eliminació, es mostra el contingut de la llista.
Programa 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> Recompte de nodes
Mentre travessa la llista enllaçada, es pot dur a terme el procés de recompte del nombre de nodes. En l'enfocament anterior, vam veure que si necessitàvem inserir/suprimir un node o mostrar el contingut de la llista enllaçada, havíem de recórrer la llista enllaçada des del principi.
Establir un comptador i augmentar així com travessem cada node ens proporcionarà el nombre de nodes de la llista enllaçada.
Diferències entre la matriu i la llista enllaçada:
| Matriu | Llista enllaçada |
|---|---|
| Les matrius tenen una mida definida. | La mida de la llista enllaçada és variable. |
| Inserir un element nou és difícil. | La inserció i la supressió són més senzilles. |
| Es permet l'accés a l'atzar. | No hi ha accés aleatori possible. |
| Els elements són relativament propers o contigus. | Els elements no són contigus. |
| No cal cap espai addicional per al punter següent. | El punter següent requereix memòria addicional. |
Funcionalitat
Com que les llistes i les matrius enllaçades són estructures de dades lineals que contenen objectes, es poden utilitzar de manera similar per a la majoria d'aplicacions.
A continuació es mostren alguns exemples d'aplicacions de llistes enllaçades:
- Les piles i les cues es poden implementar mitjançant llistes enllaçades.
- Quan necessitem expressar gràfics com a llistes d'adjacència, podem utilitzar una llista enllaçada per implementar-los.
- També podem utilitzar una llista enllaçada per contenir un polinomi matemàtic.
- En el cas del hash, s'utilitzen llistes enllaçades per implementar els cubs.
- Quan un programa requereix una assignació de memòria dinàmica, podem utilitzar una llista enllaçada perquè les llistes enllaçades són més eficients en aquest cas.
Conclusió
Les llistes enllaçades són estructures de dades que s'utilitzen per mantenir els elements de dades d'una forma lineal però no contigua. Una llista enllaçada està formada per nodes amb dos components cadascun. El primer component està format per dades, mentre que la segona meitat té un punter que emmagatzema l'adreça de memòria del següent membre de la llista.
Com a senyal que la llista enllaçada ha acabat, l'últim element de la llista té el seu punter següent establert a NULL. El cap és el primer element de la llista. La llista enllaçada permet una varietat d'accions com ara la inserció, la supressió, el recorregut, etc. Les llistes enllaçades es prefereixen sobre les matrius per a l'assignació de memòria dinàmica.
Les llistes enllaçades són difícils d'imprimir o recórrer perquè no podem accedir als elements de manera aleatòria com les matrius. En comparació amb les matrius, els procediments d'inserció i supressió són menys costosos.
En aquest tutorial, hem après tot el que cal saber sobre les llistes enllaçades lineals. Les llistes enllaçades també poden ser doblement enllaçades o circulars. En els nostres propers tutorials, repassarem aquestes llistes amb detall.