Struttura dei dati e algoritmi - Elenco collegato
Un elenco collegato è una sequenza di strutture di dati, che sono collegate tra loro tramite collegamenti.
L'elenco collegato è una sequenza di collegamenti che contiene elementi. Ogni collegamento contiene una connessione a un altro collegamento. L'elenco collegato è la seconda struttura di dati più utilizzata dopo l'array. Di seguito sono riportati i termini importanti per comprendere il concetto di elenco collegato.
Link - Ogni collegamento di un elenco collegato può memorizzare un dato chiamato elemento.
Next - Ogni collegamento di un elenco collegato contiene un collegamento al collegamento successivo denominato Avanti.
LinkedList - Un elenco collegato contiene il collegamento di connessione al primo collegamento denominato Primo.
Rappresentazione dell'elenco collegato
L'elenco collegato può essere visualizzato come una catena di nodi, in cui ogni nodo punta al nodo successivo.
Come per l'illustrazione sopra, di seguito sono riportati i punti importanti da considerare.
L'elenco collegato contiene un elemento di collegamento chiamato per primo.
Ogni collegamento contiene uno o più campi dati e un campo di collegamento chiamato successivo.
Ogni collegamento è collegato al collegamento successivo utilizzando il collegamento successivo.
L'ultimo collegamento contiene un collegamento come nullo per contrassegnare la fine dell'elenco.
Tipi di elenchi collegati
Di seguito sono riportati i vari tipi di elenchi collegati.
Simple Linked List - La navigazione degli elementi è solo in avanti.
Doubly Linked List - Gli elementi possono essere spostati avanti e indietro.
Circular Linked List - L'ultimo elemento contiene il collegamento del primo elemento come successivo e il primo elemento ha un collegamento all'ultimo elemento come precedente.
Operazioni di base
Di seguito sono riportate le operazioni di base supportate da un elenco.
Insertion - Aggiunge un elemento all'inizio dell'elenco.
Deletion - Elimina un elemento all'inizio della lista.
Display - Visualizza l'elenco completo.
Search - Cerca un elemento utilizzando la chiave data.
Delete - Elimina un elemento utilizzando la chiave data.
Operazione di inserimento
L'aggiunta di un nuovo nodo nell'elenco collegato è un'attività in più fasi. Lo impareremo con i diagrammi qui. Per prima cosa, crea un nodo usando la stessa struttura e trova la posizione in cui deve essere inserito.
Immagina di inserire un nodo B (NewNode), tra A (LeftNode) e C(RightNode). Quindi punta B. accanto a C -
NewNode.next −> RightNode;Dovrebbe assomigliare a questo -
Ora, il nodo successivo a sinistra dovrebbe puntare al nuovo nodo.
LeftNode.next −> NewNode;
Questo metterà il nuovo nodo al centro dei due. Il nuovo elenco dovrebbe apparire così:
Passaggi simili dovrebbero essere eseguiti se il nodo viene inserito all'inizio dell'elenco. Durante l'inserimento alla fine, il penultimo nodo della lista dovrebbe puntare al nuovo nodo e il nuovo nodo punterà a NULL.
Operazione di cancellazione
L'eliminazione è anche un processo in più fasi. Impareremo con la rappresentazione pittorica. In primo luogo, individuare il nodo di destinazione da rimuovere, utilizzando algoritmi di ricerca.
Il nodo sinistro (precedente) del nodo di destinazione ora dovrebbe puntare al nodo successivo del nodo di destinazione -
LeftNode.next −> TargetNode.next;
Ciò rimuoverà il collegamento che puntava al nodo di destinazione. Ora, utilizzando il codice seguente, rimuoveremo ciò a cui punta il nodo di destinazione.
TargetNode.next −> NULL;
Dobbiamo utilizzare il nodo eliminato. Possiamo tenerlo in memoria altrimenti possiamo semplicemente rilasciare la memoria e cancellare completamente il nodo di destinazione.
Operazione inversa
Questa operazione è completa. Dobbiamo fare in modo che l'ultimo nodo sia puntato dal nodo principale e invertire l'intero elenco collegato.
Per prima cosa, arriviamo alla fine della lista. Dovrebbe puntare a NULL. Ora, indicheremo il suo nodo precedente -
Dobbiamo assicurarci che l'ultimo nodo non sia l'ultimo nodo. Quindi avremo un nodo temporaneo, che assomiglia al nodo head che punta all'ultimo nodo. Ora, faremo in modo che tutti i nodi del lato sinistro puntino ai loro nodi precedenti uno per uno.
Ad eccezione del nodo (primo nodo) puntato dal nodo principale, tutti i nodi dovrebbero puntare al loro predecessore, rendendoli il loro nuovo successore. Il primo nodo punterà a NULL.
Faremo in modo che il nodo head punti al nuovo primo nodo utilizzando il nodo temporaneo.
L'elenco collegato è ora invertito. Per vedere l'implementazione dell'elenco collegato nel linguaggio di programmazione C, fare clic qui .