Lista doppiamente concatenata nelle strutture dati e negli algoritmi

Doppiamente concatenata

Il concetto di lista collegata viene comunemente utilizzato nel mondo reale. Quando usiamo Spotify per riprodurre la prossima canzone in coda, entra in azione il concetto di lista collegata singola che abbiamo imparato. Ma cosa possiamo fare per riprodurre la canzone precedente in coda?

In questo blog, capiremo un altro concetto associato alle strutture dati, che è una lista collegata bidirezionale. Discuteremo anche la sua implementazione utilizzando C e le applicazioni in tempo reale.

Cos’è una lista collegata bidirezionale?

Una lista collegata è un tipo di struttura dati lineare che include nodi collegati in modo sequenziale. Il nodo contiene tre campi, ovvero i dati memorizzati a quell’indirizzo di riferimento e i due puntatori che puntano ai nodi consecutivi sia a sinistra che a destra del nodo di riferimento.

Il puntatore al nodo sinistro memorizza l’indirizzo di memoria del nodo precedente nella sequenza, mentre il nodo destro memorizza l’indirizzo di memoria del nodo successivo. Qui utilizziamo l’allocazione dinamica della memoria invece di array in modo che la dimensione della memoria possa essere allocata o dealloccata durante l’esecuzione in base alle operazioni eseguite.

• Un approccio di apprendimento automatico per prevedere lo stato di metilazione di MGMT nei pazienti affetti da glioblastoma
• Paper sulle Graph Attention Networks spiegato con illustrazioni e implementazione in PyTorch
• VoAGI News, 26 luglio Formazione gratuita sull’IA generativa da Google • Guida per principianti all’ingegneria dei dati • GPT-Engineer il tuo nuovo assistente di codifica IA

In questo esempio, la testa punta al primo nodo. Il puntatore sinistro del nodo di riferimento memorizza NULL, e lo stesso accade nel caso del puntatore destro dell’ultimo nodo.

Per eseguire operazioni su questo esempio, possiamo modificarlo ulteriormente di conseguenza.

Implementazione della lista collegata bidirezionale

1. Inserire il nodo all’inizio

Per soddisfare la precedente operazione, creare innanzitutto un nodo e allocare memoria utilizzando la memoria dinamica. Puntare la testa al nuovo nodo e memorizzare i valori NULL sia nei nodi sinistro che destro.

2. Eliminare il nodo all’inizio

Per eliminare il nodo dall’inizio, dobbiamo memorizzare il valore del nodo destro dell’indirizzo di riferimento nella testa e liberare il primo nodo.

3. Inserire il nodo alla fine

Per aggiungere il nodo alla fine, dobbiamo attraversare fino alla fine e puntare l’ultimo nodo al nuovo nodo di riferimento e viceversa.

4. Eliminare il nodo alla fine

Per eliminare un nodo alla fine, dobbiamo attraversare la lista e raggiungere la fine. Utilizzeremo un puntatore che punta all’ultimo nodo precedente. Quindi liberiamo l’ultimo nodo.

Ora che abbiamo capito le operazioni di base, passiamo all’implementazione di una lista collegata bidirezionale utilizzando C.

Questo codice ti darà l’output desiderato di:

Ti sei mai chiesto come vengono sviluppati questi giochi multiplayer, in cui i giocatori ottengono possibilità su loop ripetuti? Questo significa che l’ultimo giocatore è collegato nuovamente al primo giocatore per formare un loop.

Per rendere ciò possibile, arriviamo ad un altro concetto legato alle liste collegate. Una lista collegata circolare è utile in tali casi.

Lista collegata circolare

Nella lista collegata circolare, l’ultimo nodo della lista contiene un puntatore al primo nodo della lista. Sia le liste collegate bidirezionali che quelle semplici possono utilizzare questo concetto.

L’unica differenza che questa lista ha rispetto alle altre due è che il puntatore destro dell’ultimo nodo punta al primo nodo, e il nodo di testa punta sempre al primo nodo stesso.

Conclusioni

A mio parere, il concetto di lista collegata è molto importante e utile durante la risoluzione di problemi complessi. Le liste collegate bidirezionali e le liste collegate circolari vanno di pari passo nel percorso di diverse situazioni. Spero che tu abbia apprezzato la lettura di questo blog. Ti prego di mettere mi piace e commentare le tue opinioni sull’argomento di oggi. Buon apprendimento!

Controlla i miei blog precedenti sulle strutture dati, integrazione di sistema utilizzando API:

• Stack nelle strutture dati
• Coda nelle strutture dati e negli algoritmi
• Lista collegata nelle strutture dati e negli algoritmi
• Creazione di una specifica API basata su RAML utilizzando la piattaforma MuleSoft
• Pubblicazione di un’API su Anypoint Exchange utilizzando la piattaforma MuleSoft