UN lista collegata è una sorta di struttura dati dinamica lineare che utilizziamo per memorizzare elementi di dati. Gli array sono anche un tipo di struttura dati lineare in cui gli elementi dati sono archiviati in blocchi di memoria continui.
A differenza degli array, l'elenco collegato non necessita di memorizzare elementi di dati in aree o blocchi di memoria contigui.
UN lista collegata è composto da elementi noti come 'Nodi' divisi in due parti. Il primo componente è la parte in cui memorizziamo i dati effettivi, mentre il secondo è la parte in cui memorizziamo il puntatore al nodo successivo. Questo tipo di struttura è conosciuta come ' elenco collegato singolarmente .'
Elenco collegato in C++
Questo tutorial esaminerà in modo approfondito l'elenco collegato singolarmente.
fare mentre Java
La struttura di un elenco collegato singolarmente è illustrata nel diagramma seguente
- Come abbiamo visto nella parte precedente, il primo nodo della lista concatenata è noto come 'testa', mentre l'ultimo nodo è chiamato 'coda'. Poiché nell'ultimo nodo non è specificato alcun indirizzo di memoria, il nodo finale dell'elenco collegato avrà un puntatore successivo nullo.
- Poiché ogni nodo include un puntatore al nodo successivo, non è necessario che gli elementi dati nell'elenco collegato siano conservati in posizioni contigue. I nodi possono essere dispersi nella memoria. Poiché ogni nodo ha l'indirizzo di quello successivo, possiamo accedere ai nodi quando vogliamo.
- Possiamo aggiungere e rimuovere rapidamente elementi di dati dall'elenco connesso. Di conseguenza, l'elenco collegato può aumentare o contrarsi dinamicamente. L'elenco collegato non ha una quantità massima di elementi dati che può contenere. Di conseguenza, possiamo aggiungere tutti i dati che desideriamo all'elenco collegato purché sia disponibile RAM.
- Poiché non dobbiamo specificare in anticipo quanti elementi abbiamo bisogno nell'elenco collegato, l'elenco collegato consente di risparmiare spazio in memoria oltre ad essere semplice da inserire ed eliminare. L'unico spazio utilizzato da un elenco collegato è memorizzare il puntatore al nodo successivo, il che aggiunge un certo costo.
Successivamente esamineremo le varie operazioni che possono essere eseguite su un elenco collegato.
1) Inserimento
L'elenco collegato viene espanso dall'azione di aggiunta ad esso. Anche se sembrerebbe semplice, data la struttura della lista concatenata, sappiamo che ogni volta che si aggiunge un dato, dobbiamo cambiare i puntatori successivi del nodo precedente e successivo del nuovo dato che abbiamo aggiunto.
Dove verrà inserito il nuovo dato è il secondo aspetto a cui pensare.
Esistono tre posizioni in cui è possibile aggiungere un elemento dati all'elenco collegato.
UN. A cominciare dall'elenco collegato
Di seguito è riportato un elenco collegato dei numeri 2->4->6->8->10. La testa che punta al nodo 2 ora punterà al nodo 1 e il successivo puntatore del nodo 1 avrà l'indirizzo di memoria del nodo 2, come mostrato nell'illustrazione seguente, se aggiungiamo un nuovo nodo 1 come primo nodo nell'elenco .
Oracle SQL non è uguale
Di conseguenza, il nuovo elenco collegato è 1->2->4->6->8->10.
B. Dopo il dato Node
In questo caso, ci viene assegnato un nodo e dobbiamo aggiungerne un nuovo dietro. La lista concatenata apparirà come segue se il nodo f viene aggiunto alla lista concatenata a->b->c->d->e dopo il nodo c:
Controlliamo quindi se il nodo specificato è presente nello schema sopra. Se è presente, viene creato un nuovo nodo f. Successivamente, puntiamo il puntatore successivo del nodo c al nuovissimo nodo f. Il puntatore successivo del nodo f ora punta al nodo d.
C. L'ultimo elemento della Lista collegata
Nel terzo caso, viene aggiunto un nuovo nodo alla fine dell'elenco collegato. Si tenga conto della seguente lista concatenata: a->b->c->d->e, con l'aggiunta del nodo f alla fine. Dopo aver aggiunto il nodo, l'elenco collegato apparirà così.
prova a prendere il blocco Java
Di conseguenza, costruiamo un nuovo nodo f. Il puntatore della coda che porta a null viene quindi puntato a f, e il puntatore successivo del nodo f è puntato a null. Nel linguaggio di programmazione riportato di seguito, abbiamo generato tutti e tre i tipi di funzioni di inserimento.
Una lista concatenata può essere dichiarata come struttura o come classe in C++. Una lista concatenata dichiarata come struttura è una classica istruzione in stile C. Un elenco collegato viene utilizzato come classe nel moderno C++, principalmente quando si utilizza la libreria di modelli standard.
La struttura è stata utilizzata nella seguente applicazione per dichiarare e generare un elenco collegato. I suoi membri saranno dati e un puntatore all'elemento successivo.
Programma 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) Cancellazione
Similmente all'inserimento, l'eliminazione di un nodo da una lista concatenata richiede molti punti dai quali il nodo potrebbe essere eliminato. Possiamo rimuovere il primo, l'ultimo o il kesimo nodo dell'elenco collegato in modo casuale. Dobbiamo aggiornare correttamente il puntatore successivo e tutti gli altri puntatori dell'elenco collegato per mantenere l'elenco collegato dopo l'eliminazione.
Nella seguente implementazione C++ sono disponibili due metodi di eliminazione: eliminazione del nodo iniziale dell'elenco ed eliminazione dell'ultimo nodo dell'elenco. Iniziamo aggiungendo i nodi in testa all'elenco. Il contenuto dell'elenco viene quindi visualizzato dopo ogni aggiunta ed eliminazione.
Programma C++:
kajal aggarwal
#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> Conteggio dei nodi
Mentre si attraversa l'elenco collegato, è possibile eseguire il processo di conteggio del numero di nodi. Nell'approccio precedente, abbiamo visto che se volessimo inserire/eliminare un nodo o visualizzare il contenuto della lista concatenata, dovevamo percorrere la lista concatenata dall'inizio.
L'impostazione di un contatore e l'incremento così come attraversiamo ciascun nodo ci fornirà il numero di nodi nell'elenco collegato.
Differenze tra array ed elenco collegato:
| Vettore | Lista collegata |
|---|---|
| Gli array hanno una dimensione definita. | La dimensione dell'elenco collegato è variabile. |
| L'inserimento di un nuovo elemento è difficile. | L'inserimento e la cancellazione sono più semplici. |
| L'accesso è consentito in modo casuale. | Non è possibile alcun accesso casuale. |
| Gli elementi sono relativamente vicini o contigui. | Gli elementi non sono contigui. |
| Non è richiesto spazio aggiuntivo per il puntatore seguente. | Il seguente puntatore richiede memoria aggiuntiva. |
Funzionalità
Poiché gli elenchi collegati e gli array sono entrambi strutture dati lineari che contengono oggetti, possono essere utilizzati in modi simili per la maggior parte delle applicazioni.
Di seguito sono riportati alcuni esempi di applicazioni di elenchi collegati:
- Stack e code possono essere implementati utilizzando elenchi collegati.
- Quando dobbiamo esprimere i grafici come liste di adiacenza, possiamo utilizzare una lista concatenata per implementarli.
- Possiamo anche utilizzare una lista concatenata per contenere un polinomio matematico.
- Nel caso dell'hashing, per implementare i bucket vengono utilizzate liste collegate.
- Quando un programma richiede un'allocazione dinamica della memoria, possiamo utilizzare un elenco collegato perché in questo caso gli elenchi collegati sono più efficienti.
Conclusione
Gli elenchi collegati sono strutture di dati utilizzate per contenere elementi di dati in una forma lineare ma non contigua. Una lista collegata è composta da nodi con due componenti ciascuno. Il primo componente è costituito da dati, mentre la seconda metà ha un puntatore che memorizza l'indirizzo di memoria del membro successivo della lista.
altera aggiungi colonna Oracle
Come segno che l'elenco collegato è terminato, l'ultimo elemento dell'elenco ha il puntatore successivo impostato su NULL. Il Capo è il primo elemento della lista. L'elenco collegato consente una varietà di azioni come l'inserimento, l'eliminazione, l'attraversamento e così via. Gli elenchi collegati sono preferiti rispetto agli array per l'allocazione dinamica della memoria.
Gli elenchi collegati sono difficili da stampare o attraversare perché non possiamo accedere agli elementi in modo casuale come gli array. Rispetto agli array, le procedure di inserimento-eliminazione sono meno costose.
In questo tutorial abbiamo imparato tutto quello che c'è da sapere sugli elenchi concatenati lineari. Gli elenchi collegati possono anche essere doppiamente collegati o circolari. Nei nostri prossimi tutorial, esamineremo questi elenchi in dettaglio.