Programmazione · concetti · strutture dati

Cos'è una lista concatenata?

Una lista concatenata (linked list) è una struttura dati che memorizza una sequenza di valori come una catena di nodi. Ogni nodo contiene due cose: un valore e un puntatore (un riferimento) al nodo successivo della catena. I nodi non sono disposti uno accanto all'altro in un unico blocco di memoria come lo sono gli elementi di un array; invece ognuno punta semplicemente a dove si trova il successivo. Segui i puntatori dal primo nodo, la testa, e potrai percorrere l'intera sequenza un anello alla volta.

Come è costruita la catena

Pensala come una caccia al tesoro in cui ogni indizio ti dice dove trovare l'indizio successivo. La lista mantiene un riferimento al nodo di testa. Il puntatore di quel nodo porta al secondo nodo, il cui puntatore porta al terzo, e così via finché il puntatore di un nodo è vuoto (spesso chiamato null o None), il che segna la fine della lista.

[ valore | successivo ] -> [ valore | successivo ] -> [ valore | null ]

Poiché le connessioni sono solo puntatori, i nodi possono trovarsi ovunque in memoria. Per far crescere la lista, allochi un nuovo nodo e imposti un puntatore verso di esso; nient'altro deve spostarsi.

Semplice vs doppiamente concatenata

Esistono due forme comuni, e la differenza sta in quanti puntatori porta ogni nodo:

• Lista concatenata semplice: ogni nodo punta solo al nodo successivo. Puoi andare avanti nella lista ma non indietro, e paghi un solo puntatore per nodo.
• Lista doppiamente concatenata: ogni nodo punta sia al nodo successivo sia a quello precedente. Questo permette di percorrerla in entrambe le direzioni e rende più facili alcune eliminazioni, al costo di un puntatore aggiuntivo per nodo.

Lista concatenata vs array

Il modo più chiaro per capire una lista concatenata è metterla accanto a un array, perché fanno compromessi opposti. Un array memorizza i suoi elementi in un blocco contiguo con un indice, quindi può saltare a qualsiasi posizione all'istante. Una lista concatenata vi rinuncia in cambio di modifiche poco costose alle estremità.

• Accesso casuale. Un array legge qualsiasi elemento tramite il suo indice in O(1). Una lista concatenata non ha indice: per raggiungere il decimo nodo devi partire dalla testa e seguire nove puntatori, quindi l'accesso è O(n).
• Inserimento e cancellazione. Se hai già un riferimento al nodo giusto, una lista concatenata può inserire o rimuovere lì ricollegando un paio di puntatori, un'operazione O(1) - senza spostare gli altri elementi. In un array, inserire o cancellare in mezzo significa spostare gli elementi successivi, il che è O(n).
• Memoria e cache. Un array raggruppa i suoi valori, il che è favorevole alla cache della CPU. Una lista concatenata disperde i suoi nodi e memorizza un puntatore aggiuntivo per nodo, quindi usa più memoria per elemento e tende ad avere una località della cache peggiore.

Nessuna delle due è "migliore"; si adattano a lavori diversi. Se hai bisogno di accessi rapidi per posizione, di solito vince un array (o un array dinamico come una list o un vector). Se i tuoi dati cambiano molto di dimensione e soprattutto aggiungi o rimuovi alle estremità, una lista concatenata può andare bene. Per un ripasso su come questi costi vengono descritti, vedi la nostra guida alla notazione Big O.

Le complessità, onestamente

Ecco i costi standard per una lista concatenata, con l'avvertenza che conta sempre:

• Accesso e ricerca: O(n). Non c'è un indice, quindi trovare un valore significa percorrere la catena dalla testa.
• Inserimento e cancellazione: O(1) quando hai già un riferimento al nodo (per esempio, proprio in testa). Se devi prima trovare il punto, quella ricerca è O(n), e il totale riflette entrambe le parti.

Quella condizione "quando hai il nodo" è la parte che spesso viene tralasciata. Inserire in testa a una lista concatenata semplice è davvero tempo costante; inserire dopo un valore che devi ancora localizzare non lo è.

Dove si usano le liste concatenate

Le liste concatenate sono più un mattone di base che un contenitore di tutti i giorni. Sono un modo naturale per implementare una pila (stack) o una coda (queue), poiché queste aggiungono e rimuovono solo alle estremità. Si adattano a situazioni in cui la dimensione della collezione cambia molto e non hai bisogno di un accesso rapido per posizione. Alcune strutture usano nodi concatenati internamente; per esempio, un modo comune di gestire le collisioni in una hash table è concatenare insieme le voci in collisione in una piccola lista concatenata per bucket.

I compromessi

• Nessun accesso casuale. Raggiungere una posizione arbitraria costa O(n) perché segui i puntatori dalla testa; non c'è un indice con cui saltare.
• Memoria aggiuntiva per elemento. Ogni nodo memorizza almeno un puntatore (due per una lista doppiamente concatenata) oltre al suo valore.
• Località della cache più debole. Nodi dispersi sono meno favorevoli alla cache di un array contiguo, il che può rendere l'attraversamento più lento nella pratica anche quando il Big O è lo stesso.
• Modifiche poco costose a un nodo noto. Il vantaggio: inserire o rimuovere a un nodo che già possiedi è O(1), senza spostare il resto dei dati.

FAQ

Qual è la differenza tra una lista concatenata e un array? Un array memorizza gli elementi in un blocco contiguo con un indice, quindi legge qualsiasi posizione in O(1) ma spostare elementi per inserire o cancellare in mezzo costa O(n). Una lista concatenata memorizza nodi separati uniti da puntatori, quindi non ha accesso casuale (O(n) per raggiungere una posizione) ma può inserire o cancellare a un nodo noto in O(1).

Perché accedere a un elemento è O(n)? Perché una lista concatenata non ha indice. Per raggiungere l'n-esimo nodo parti dalla testa e segui la catena di puntatori n volte, quindi il costo cresce con la posizione che vuoi.

Qual è la differenza tra semplice e doppiamente concatenata? In una lista concatenata semplice ogni nodo punta solo al nodo successivo, quindi puoi muoverti solo in avanti. In una lista doppiamente concatenata ogni nodo punta anche al nodo precedente, quindi puoi muoverti in entrambe le direzioni, al costo di un puntatore aggiuntivo per nodo.

Quando dovrei usare una lista concatenata? Quando la dimensione della collezione cambia molto e aggiungi o rimuovi soprattutto alle estremità, o come struttura portante di una pila o di una coda. Se hai bisogno di un accesso rapido per posizione, un array è di solito la scelta migliore.

Guide correlate: hash table, notazione Big O, ricorsione.