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 della 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 specifici che offrono.

Perché le liste collegate?

Le liste collegate sono state create per superare vari svantaggi legati all’archiviazione 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 di spostare tutti gli elementi successivi in una posizione diversa. Questo processo ha complessità temporale O(n) e può degradare notevolmente le prestazioni, soprattutto man mano che la lista cresce. 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 di memoria e li connettono 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 cancellazione, 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 possiedi già un puntatore al nodo rilevante (ad esempio quando lavori sulla testa della lista).

Dimensione dinamica

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

Tuttavia, questo processo comporta 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 di memoria contiguo più grande e poi copiare tutti gli elementi esistenti in questo nuovo blocco. Questo processo è dispendioso in tempo e inefficiente, soprattutto per liste di grandi dimensioni. D’altra parte, se la dimensione iniziale della lista è sovrastimata, la memoria inutilizzata viene sprecata.

Al contrario, le liste collegate allocano la memoria per ogni 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 i puntatori al nodo successivo, l’uso di memoria per elemento è più alto con le liste collegate. Inoltre, questa struttura dati non consente l’accesso diretto ai dati. Accedere a un elemento richiede una traversata sequenziale dall’inizio della lista, con complessità temporale di ricerca O(n).

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

• Devi inserire ed eliminare spesso molti elementi
• La dimensione dei dati è imprevedibile o soggetta a frequenti cambiamenti
• 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 specifici per scenari diversi. 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 dei 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, l’accesso a un elemento specifico per valore o indice richiede di partire dalla testa e muoversi sequenzialmente tra 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, l’inserimento e la cancellazione 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 al nodo precedente se necessario. Questo vincolo limita la possibilità di eseguire operazioni che richiedono una navigazione bidirezionale.

Le liste doppiamente collegate risolvono questo problema incorporando un puntatore aggiuntivo all’interno di 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, creando una struttura circolare. Questo significa che, a differenza delle liste semplici e doppie viste finora, la lista circolare non termina; invece, fa un loop.

La natura ciclica delle liste collegate circolari le rende ideali per scenari che devono essere percorsi continuamente, 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 di Python:

Il punto chiave: le liste collegate vincono su inserimenti ed eliminazioni in testa (O(1)), ma perdono su tutto il resto. Se non stai aggiungendo o rimuovendo spesso elementi all’inizio della tua struttura dati, una normale lista Python è probabilmente 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 nella 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 l’informazione effettiva che il nodo deve contenere. L’attributo “next” rappresenta l’indirizzo del nodo successivo. Attualmente è impostato a None, a significare che non è collegato ad alcun altro nodo nella lista. Man mano che aggiungeremo 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 che specifichi. Il puntatore “next” di questo nuovo nodo è impostato sull’attuale testa della lista, il che posiziona questo nodo 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 comprendere 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 al nodo attualmente ultimo nella lista. Vediamo come funziona in pratica:

    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, assegna il nuovo nodo come testa di quella lista. Altrimenti, attraversa la lista per trovare l’ultimo nodo e imposta il puntatore di quest’ultimo sul nuovo nodo.

Ora dobbiamo includere questo metodo nella nostra classe LinkedList e usarlo per aggiungere una parola alla fine della lista. Per farlo, modifica la 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 cambiare il suo puntatore “next” 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 suo nodo successivo 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 recupero di un valore specifico nella lista collegata. Per farlo, il metodo dovrebbe partire dalla testa della lista e iterare attraverso ogni 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 includendo 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 in prima posizione. 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 di data science. Le liste collegate vengono usate per sviluppare file system, costruire hash table 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.

Impara strutture dati e algoritmi

Imparare altre strutture dati, come alberi, stack e code, è una naturale evoluzione della comprensione delle 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 i binary search tree, ad esempio, estendono il concetto di liste collegate in una forma gerarchica, consentendo a ogni nodo di connettersi 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à in questi concetti in maggior dettaglio. Per prima cosa imparerai strutture dati come stack, alberi, tabelle hash, code e grafi. Progredendo nel corso, acquisirai comprensione di algoritmi di ricerca e ordinamento, che ti aiuteranno a diventare un programmatore e un problem-solver più efficiente.

Esplorare concetti avanzati di liste collegate

In questo tutorial abbiamo implementato liste semplicemente collegate, coprendo operazioni come inserimento, eliminazione e traversata.

Puoi fare un passo oltre imparando l’implementazione di liste doppiamente collegate e circolari. Le skip list sono un’altra estensione delle liste collegate che consentono ricerche più veloci facilitando un accesso più rapido agli elementi.

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

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