Lista collegata è una struttura dati lineare, in cui gli elementi non sono memorizzati in una posizione contigua, ma sono collegati tramite puntatori. La Lista Collegata forma una serie di nodi connessi, in cui ciascun nodo memorizza i dati e l'indirizzo del nodo successivo.

Struttura del nodo: Un nodo in un elenco collegato è generalmente costituito da due componenti:
Dati: Contiene il valore effettivo o i dati associati al nodo.
Puntatore successivo: Memorizza l'indirizzo di memoria (riferimento) del nodo successivo nella sequenza.
Testa e coda: Si accede all'elenco collegato tramite il nodo head, che punta al primo nodo dell'elenco. L'ultimo nodo nell'elenco punta a NULL o nullptr, indicando la fine dell'elenco. Questo nodo è noto come nodo di coda.

Perché è necessaria la struttura dei dati dell'elenco collegato?

Ecco alcuni vantaggi di un elenco collegato elencato di seguito, ti aiuterà a capire perché è necessario saperlo.

• Struttura dei dati dinamici: La dimensione della memoria può essere allocata o deallocata in fase di esecuzione in base all'operazione di inserimento o eliminazione.
• Facilità di inserimento/eliminazione: L'inserimento e l'eliminazione degli elementi sono più semplici degli array poiché non è necessario spostare gli elementi dopo l'inserimento e l'eliminazione, è necessario aggiornare solo l'indirizzo.
• Utilizzo efficiente della memoria: Come sappiamo la Linked List è una struttura dati dinamica la cui dimensione aumenta o diminuisce in base ai requisiti, quindi ciò evita lo spreco di memoria.
• Implementazione: È possibile implementare varie strutture dati avanzate utilizzando un elenco collegato come stack, coda, grafico, mappe hash, ecc.

Esempio:

In un sistema, se manteniamo un elenco ordinato di ID in un array id[] = [1000, 1010, 1050, 2000, 2040].

Se vogliamo inserire un nuovo ID 1005, allora per mantenere l'ordinamento, dobbiamo spostare tutti gli elementi dopo il 1000 (escluso 1000).

Anche la cancellazione è costosa con gli array finché non vengono utilizzate alcune tecniche speciali. Ad esempio, per eliminare 1010 in id[], tutto ciò che segue 1010 deve essere spostato a causa di ciò, viene svolto così tanto lavoro che influisce sull'efficienza del codice.

Tipi di elenchi collegati :

Esistono principalmente tre tipi di elenchi collegati:

1. Elenco con collegamento singolo
2. Doppia lista concatenata
3. Elenco collegato circolare

1. Elenco con collegamento singolo :

In un elenco collegato singolarmente, ciascun nodo contiene un riferimento al nodo successivo nella sequenza. L'attraversamento di un elenco collegato singolarmente viene eseguito in avanti.

Elenco con collegamento singolo

2. Elenco con doppio collegamento :

In un elenco doppiamente collegato, ogni nodo contiene riferimenti sia al nodo successivo che a quello precedente. Ciò consente l'attraversamento sia in avanti che all'indietro, ma richiede memoria aggiuntiva per il riferimento all'indietro.

Elenco con doppio collegamento

3. Elenco collegato circolare :

In una lista concatenata circolare, l'ultimo nodo punta al nodo principale, creando una struttura circolare. Può essere collegato singolarmente o doppiamente.

decodifica js base64

Elenco collegato circolare

Operazioni su liste concatenate

1. Inserimento : L'aggiunta di un nuovo nodo a un elenco collegato comporta la regolazione dei puntatori dei nodi esistenti per mantenere la sequenza corretta. L'inserimento può essere effettuato all'inizio, alla fine o in qualsiasi posizione all'interno dell'elenco
2. Cancellazione : La rimozione di un nodo da un elenco collegato richiede la regolazione dei puntatori dei nodi vicini per colmare il vuoto lasciato dal nodo eliminato. L'eliminazione può essere eseguita all'inizio, alla fine o in qualsiasi posizione all'interno dell'elenco.
3. Ricerca : La ricerca di un valore specifico in un elenco collegato implica l'attraversamento dell'elenco dal nodo principale fino a quando non viene trovato il valore o viene raggiunta la fine dell'elenco.

Analisi della complessità della lista collegata :

• Complessità temporale: O(n)
• Spazio ausiliario: O(n)

Vantaggi delle liste collegate

• Dimensione dinamica: Gli elenchi collegati possono crescere o ridursi dinamicamente, poiché l'allocazione della memoria viene eseguita in fase di esecuzione.
• Inserimento e cancellazione: Aggiungere o rimuovere elementi da un elenco collegato è efficiente, soprattutto per elenchi di grandi dimensioni.
• Flessibilità: Gli elenchi collegati possono essere facilmente riorganizzati e modificati senza richiedere un blocco di memoria contiguo.

Svantaggi delle liste collegate

• Accesso casuale: A differenza degli array, gli elenchi collegati non consentono l'accesso diretto agli elementi tramite indice. L'attraversamento è necessario per raggiungere un nodo specifico.
• Memoria aggiuntiva: Gli elenchi concatenati richiedono memoria aggiuntiva per memorizzare i puntatori, rispetto agli array.

Conclusione:

Gli elenchi collegati sono strutture dati versatili che forniscono un'allocazione dinamica della memoria e operazioni di inserimento ed eliminazione efficienti. Comprendere le basi degli elenchi collegati è essenziale per qualsiasi programmatore o appassionato di informatica. Con questa conoscenza, puoi implementare elenchi collegati per risolvere vari problemi ed espandere la tua comprensione delle strutture dati e degli algoritmi.