Liste collegate in Python: tutorial con esempi

Una lista collegata è una struttura dati che svolge un ruolo cruciale nell’organizzazione e nella gestione dei dati. Contiene una serie di nodi memorizzati in posizioni casuali in memoria, consentendo una gestione efficiente della memoria. Ogni nodo in una lista collegata contiene due componenti principali: la parte dei dati e un riferimento al nodo successivo nella sequenza.

Se a prima vista questo concetto ti sembra complesso, niente panico!

Lo scomporremo ai fondamentali per spiegare cosa sono le liste collegate, perché le usiamo e i vantaggi unici che offrono.

Perché usare le liste collegate?

Le liste collegate sono state create per superare vari svantaggi legati alla memorizzazione dei dati in liste e array tradizionali, come descritto di seguito:

Facilità di inserimento e cancellazione

Nelle liste, inserire o eliminare un elemento in una posizione diversa dalla fine richiede lo spostamento di tutti gli elementi successivi in un'altra posizione. Questo processo ha una complessità temporale di O(n) e può degradare significativamente le prestazioni, soprattutto all’aumentare della dimensione della lista. Se non hai ancora familiarità con il funzionamento delle liste o con la loro implementazione, puoi leggere il nostro tutorial sulle liste in Python.

Le liste collegate, invece, funzionano in modo diverso. Memorizzano gli elementi in varie posizioni non contigue in memoria e li collegano tramite puntatori ai nodi successivi. Questa struttura consente alle liste collegate di aggiungere o rimuovere elementi in qualsiasi posizione semplicemente modificando i collegamenti per includere un nuovo elemento o saltare quello eliminato.

Una volta che hai un riferimento diretto al nodo nel punto di inserimento o eliminazione, l’operazione in sé è O(1). Tuttavia, trovare quella posizione richiede comunque una traversata O(n), quindi il vantaggio O(1) si applica solo quando hai già un puntatore al nodo rilevante (ad esempio quando lavori sulla testa della lista).

Dimensione dinamica

Le liste Python sono array dinamici, il che significa che offrono la flessibilità di modificarne la dimensione.

Tuttavia, questo processo implica una serie di operazioni complesse, tra cui riallocare l’array in un nuovo blocco di memoria più grande. Tale riallocazione è inefficiente poiché gli elementi vengono copiati in un nuovo blocco, potenzialmente allocando più spazio del necessario nell’immediato.

Al contrario, le liste collegate possono crescere e ridursi dinamicamente senza bisogno di riallocazione o ridimensionamento. Questo le rende una scelta preferibile per attività che richiedono elevata flessibilità.

Efficienza della memoria

Le liste allocano la memoria per tutti i loro elementi in un blocco contiguo. Se una lista deve crescere oltre la sua dimensione iniziale, deve allocare un nuovo blocco contiguo più grande di memoria e poi copiare tutti gli elementi esistenti in questo nuovo blocco. Questo processo è dispendioso in termini di tempo e inefficiente, specialmente per liste grandi. D’altro canto, se la dimensione iniziale della lista è sovrastimata, la memoria inutilizzata viene sprecata.

Al contrario, le liste collegate allocano la memoria per ciascun elemento separatamente. Questa struttura porta a un migliore utilizzo della memoria, poiché la memoria per i nuovi elementi può essere allocata man mano che vengono aggiunti.

Quando dovresti usare le liste collegate?

Sebbene le liste collegate offrano alcuni vantaggi rispetto a liste e array tradizionali, come dimensione dinamica ed efficienza della memoria, presentano anche dei limiti. Poiché per ogni elemento devono essere memorizzati dei puntatori per fare riferimento al nodo successivo, l’uso di memoria per elemento è più elevato con le liste collegate. Inoltre, questa struttura dati non consente l’accesso diretto ai dati. L’accesso a un elemento richiede una traversata sequenziale dall’inizio della lista, con una complessità di ricerca O(n).

La scelta tra usare una lista collegata o un array dipende dalle esigenze specifiche dell’applicazione. Le liste collegate sono più utili quando:

• Devi inserire ed eliminare molti elementi frequentemente
• La dimensione dei dati è imprevedibile o soggetta a cambiamenti frequenti
• L’accesso diretto agli elementi non è un requisito
• Il dataset contiene elementi o strutture di grandi dimensioni

Tipi di liste collegate

Esistono tre tipi di liste collegate, ognuna con vantaggi unici per diversi scenari. Questi tipi sono:

Liste semplicemente collegate (singly-linked)

Lista semplicemente collegata

Una lista semplicemente collegata è il tipo più semplice di lista collegata, in cui ogni nodo contiene alcuni dati e un riferimento al nodo successivo nella sequenza. Può essere attraversata in una sola direzione: dalla testa (il primo nodo) alla coda (l’ultimo nodo).

Ogni nodo in una lista semplicemente collegata è tipicamente composto da due parti:

• Dati: le informazioni effettive memorizzate nel nodo.
• Puntatore al successivo: un riferimento al nodo successivo. Il puntatore al successivo dell’ultimo nodo è solitamente impostato a null.

Poiché queste strutture dati possono essere attraversate in una sola direzione, accedere a un elemento specifico per valore o indice richiede di partire dalla testa e muoversi sequenzialmente attraverso i nodi fino a trovare quello desiderato. Questa operazione ha complessità temporale O(n), risultando meno efficiente per liste grandi.

Inserire ed eliminare un nodo all’inizio di una lista semplicemente collegata è molto efficiente, con complessità O(1). Tuttavia, inserimenti ed eliminazioni nel mezzo o alla fine richiedono di attraversare la lista fino a quel punto, portando a una complessità O(n).

Il design delle liste semplicemente collegate le rende una struttura dati utile quando si eseguono operazioni che avvengono all’inizio della lista.

Liste doppiamente collegate (doubly-linked)

Lista doppiamente collegata

Uno svantaggio delle liste semplicemente collegate è che possiamo attraversarle solo in una direzione e non possiamo tornare indietro al nodo precedente se necessario. Questo vincolo limita la possibilità di eseguire operazioni che richiedono navigazione bidirezionale.

Le liste doppiamente collegate risolvono questo problema incorporando un puntatore aggiuntivo in ogni nodo, garantendo che la lista possa essere attraversata in entrambe le direzioni. Ogni nodo in una lista doppiamente collegata contiene tre elementi: i dati, un puntatore al nodo successivo e un puntatore al nodo precedente.

Liste collegate circolari

Lista collegata circolare

Le liste collegate circolari sono una forma specializzata di lista collegata in cui l’ultimo nodo punta di nuovo al primo nodo, creando una struttura circolare. Questo significa che, a differenza delle liste semplici e doppie viste finora, la lista collegata circolare non termina; invece, si ripete in loop.

La natura ciclica delle liste collegate circolari le rende ideali per scenari che devono essere percorsi continuamente in ciclo, come giochi da tavolo che tornano dall’ultimo giocatore al primo, o in algoritmi informatici come lo scheduling round-robin.

Riepilogo delle complessità temporali

È utile vedere a colpo d’occhio come le liste collegate si confrontano con le liste Python:

La conclusione principale: le liste collegate vincono su inserimenti ed eliminazioni in testa (O(1)), ma perdono su tutto il resto. Se non stai aggiungendo o rimuovendo elementi frequentemente all’inizio della tua struttura dati, probabilmente una normale lista Python è la scelta migliore.

Come creare una lista collegata in Python

Ora che abbiamo capito cosa sono le liste collegate, perché le usiamo e le loro varianti, passiamo a implementare queste strutture dati in Python. Il notebook per questo tutorial è disponibile anche in questo workbook DataLab; se ne crei una copia puoi modificare ed eseguire il codice. È un’ottima opzione se riscontri problemi nell’eseguire il codice in autonomia!

Inizializzare un nodo

Come abbiamo visto, un nodo è un elemento della lista collegata che memorizza dati e un riferimento al nodo successivo nella sequenza. Ecco come puoi definire un nodo in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return f"Node({self.data})"

Il codice sopra inizializza un nodo eseguendo due azioni principali: all’attributo "data" del nodo viene assegnato un valore che rappresenta le informazioni effettive che il nodo deve contenere. L’attributo "next" rappresenta l’indirizzo del nodo successivo. Attualmente è impostato su None, a indicare che non è collegato ad alcun altro nodo della lista. Man mano che aggiungiamo nuovi nodi alla lista collegata, questo attributo verrà aggiornato per puntare al nodo successivo.

Creare una classe per la lista collegata

Successivamente, dobbiamo creare la classe della lista collegata. Questa incapsulerà tutte le operazioni per gestire i nodi, come inserimento e rimozione. Inizieremo inizializzando la lista collegata:

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None

Impostando self.head a None, stiamo dichiarando che la lista collegata è inizialmente vuota e non ci sono nodi a cui puntare. Procederemo ora a popolare la lista inserendo nuovi nodi.

Inserire un nuovo nodo all’inizio di una lista collegata

All’interno della classe LinkedList, aggiungeremo un metodo per creare un nuovo nodo e posizionarlo all’inizio della lista:

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node

Ogni volta che chiami il metodo sopra, viene creato un nuovo nodo con i dati specificati. Il puntatore al successivo di questo nuovo nodo viene impostato sull’attuale testa della lista, il che lo posiziona davanti ai nodi esistenti. Infine, il nodo appena creato diventa la testa della lista.

Ora popoleremo questa lista collegata con una serie di parole per capire meglio come funziona l’operazione di inserimento. Per farlo, creiamo prima un metodo pensato per attraversare e stampare il contenuto della lista:

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line

Il metodo sopra stamperà il contenuto della nostra lista collegata. Procediamo ora a usare i metodi che abbiamo definito per popolare la lista con una serie di parole: “the quick brown fox”.

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()

Le righe di codice sopra dovrebbero produrre il seguente output:

"the quick brown fox"

Inserire un nuovo nodo alla fine di una lista collegata

Ora creeremo un metodo chiamato insertAtEnd all’interno della classe LinkedList, per creare un nuovo nodo alla fine della lista. Se la lista è vuota, il nuovo nodo diventerà la testa della lista. Altrimenti, verrà aggiunto in coda all’attuale ultimo nodo della lista. Vediamo in pratica come funziona:

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

Il metodo sopra inizia creando un nuovo nodo. Quindi verifica se la lista è vuota e, in tal caso, il nuovo nodo viene assegnato come testa di quella lista. In caso contrario, attraversa la lista per trovare l’ultimo nodo e imposta il puntatore di quest’ultimo verso il nuovo nodo.

Dobbiamo ora includere questo metodo nella nostra classe LinkedList e usarlo per aggiungere una parola alla fine della nostra lista. Per farlo, modifica la tua funzione main in questo modo:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()

Nota che abbiamo semplicemente chiamato il metodo insertAtEnd per stampare la parola “jumps” alla fine della lista. Il codice sopra dovrebbe produrre il seguente output:

"the quick brown fox jumps"

Eliminare un nodo dall’inizio di una lista collegata

Eliminare il primo nodo di una lista collegata è semplice, poiché comporta semplicemente il puntare la testa della lista al secondo nodo. In questo modo, il primo nodo non farà più parte della lista. Per farlo, includi il seguente metodo nella classe LinkedList:

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head

Eliminare un nodo dalla fine di una lista collegata

Per eliminare l’ultimo nodo di una lista collegata, dobbiamo attraversare la lista per trovare il penultimo nodo e impostare il suo puntatore successivo a None. In questo modo, l’ultimo nodo non farà più parte della lista. Copia e incolla il seguente metodo nella tua classe LinkedList per farlo:

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None

Il metodo sopra verifica innanzitutto se la lista collegata è vuota, restituendo un messaggio all’utente in tal caso. Altrimenti, se la lista contiene un solo nodo, quel nodo viene rimosso. Per liste con più nodi, il metodo individua il penultimo nodo e aggiorna il riferimento al successivo impostandolo a None.

Aggiorniamo ora la funzione main per eliminare elementi dall’inizio e dalla fine della lista collegata:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()

Il codice sopra stamperà la lista prima e dopo le eliminazioni, mostrando come funzionano le operazioni di inserimento ed eliminazione nelle liste collegate. Dovresti vedere il seguente output dopo l’esecuzione:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox

Cercare un valore specifico nella lista collegata

L’ultima operazione che impareremo in questo capitolo è il reperimento di un valore specifico nella lista collegata. Per farlo, il metodo dovrebbe iniziare dalla testa della lista e iterare attraverso ciascun nodo, verificando se i dati del nodo corrispondono al valore cercato. Ecco un’implementazione pratica di questa operazione:

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 

Per trovare valori specifici nella lista collegata che abbiamo creato, aggiorna la tua funzione main per includere il metodo di ricerca che abbiamo appena scritto:

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find

Il codice sopra produrrà il seguente output:

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list

La parola “quick” è stata trovata con successo nella lista collegata poiché esiste nella prima posizione della lista. Tuttavia, la parola “lazy” non fa parte della lista, motivo per cui non è stata trovata.

Considerazioni finali

Se sei arrivato fin qui, complimenti! Ora hai una solida comprensione dei principi di base delle liste collegate, inclusa la loro struttura, i tipi, come aggiungere e rimuovere elementi e come attraversarle.

Ma il viaggio non finisce qui. Le liste collegate sono solo l’inizio del mondo delle strutture dati e degli algoritmi. Ecco alcuni possibili prossimi passi per approfondire l’argomento:

Crea un tuo progetto

Immergiti nelle applicazioni pratiche delle liste collegate integrandole in un progetto di coding o data science. Le liste collegate sono usate per sviluppare file system, costruire tabelle hash e persino creare sistemi di navigazione GPS e giochi da tavolo. Per iniziare con i tuoi progetti, dai un’occhiata ai nostri progetti di data science guidati e gratuiti che ti insegnano a risolvere problemi reali in Python, R e SQL.

Scopri strutture dati e algoritmi

Imparare altre strutture dati, come alberi, stack e code, è un’evoluzione naturale a partire dalle liste collegate. Queste strutture si basano sui principi delle liste collegate, aiutandoti a risolvere in modo efficiente una gamma più ampia di problemi computazionali. Gli alberi e gli alberi binari di ricerca, ad esempio, estendono il concetto di liste collegate in una forma gerarchica, consentendo a ciascun nodo di collegarsi a più elementi nella struttura dati.

Se questi concetti ti suonano poco familiari, niente panico! Datacamp ha un intero corso su strutture dati e algoritmi in Python che ti guiderà attraverso questi concetti in maggior dettaglio. Imparerai prima strutture dati come stack, alberi, tabelle hash, code e grafi. Procedendo nel corso, acquisirai una comprensione degli algoritmi di ricerca e ordinamento, che ti aiuteranno a diventare un programmatore e un problem-solver più efficiente.

Esplorare concetti avanzati sulle liste collegate

In questo tutorial abbiamo implementato liste semplicemente collegate, trattando operazioni come inserimento, eliminazione e attraversamento.

Puoi fare un passo avanti imparando l’implementazione delle liste doppiamente e circolarmente collegate. Le skip list sono un’altra estensione delle liste collegate che consentono ricerche più rapide facilitando un accesso più veloce agli elementi.

Conoscere queste strutture dati avanzate porterà le tue capacità tecniche al livello successivo e migliorerà notevolmente le tue abilità di programmazione, preparandoti a sfide più complesse in campi come data science, sviluppo software e machine learning engineering.

Se desideri un’introduzione alla programmazione più adatta ai principianti prima di affrontare questi argomenti avanzati, esplora il nostro percorso di carriera Python Programmer. Offre una serie di corsi che ti insegneranno le basi del linguaggio.