In quali circostanze sono utili le liste concatenate?

La maggior parte delle volte vedo persone che cercano di usare liste collegate, mi sembra una scelta scarsa (o molto scarsa). Forse sarebbe utile esplorare le circostanze in cui una lista collegata è o non è una buona scelta della struttura dei dati.

Idealmente, le risposte spiegherebbero i criteri da utilizzare nella selezione di una struttura di dati e quali strutture di dati potrebbero funzionare meglio in determinate circostanze.

Edit: Devo dire, sono molto impressionato non solo dal numero, ma dalla qualità delle risposte. Posso accettarne solo uno, ma ce ne sono altri due o tre che dovrei dire sarebbe valsa la pena accettare se qualcosa di un po ‘meglio non fosse stato lì. Solo una coppia (in particolare quella che ho finito per accettare) ha indicato situazioni in cui un elenco collegato ha fornito un vantaggio reale. Penso che Steve Jessop meriti una sorta di menzione d’onore per averne non solo una, ma tre diverse risposte, tutte cose che ho trovato piuttosto impressionanti. Naturalmente, anche se è stato pubblicato solo come commento, non come risposta, penso che il blog di Neil valga anche la pena di leggerlo – non solo informativo, ma anche piuttosto divertente.

Possono essere utili per strutture di dati concorrenti. (Esiste ora un esempio di utilizzo del mondo reale non simultaneo – che non sarebbe presente se @Neil non avesse menzionato FORTRAN. 😉

Ad esempio, ConcurrentDictionary in .NET 4.0 RC utilizza elenchi concatenati per concatenare gli elementi che hanno lo stesso bucket.

Anche la struttura dati sottostante per ConcurrentStack è un elenco collegato.

ConcurrentStack è una delle strutture dati che servono da fondamento per il nuovo Thread Pool , (in sostanza le “code” locali implementate come stack). (L’altra struttura principale di supporto è ConcurrentQueue .)

Il nuovo pool di thread, a sua volta, fornisce le basi per la pianificazione del lavoro della nuova libreria task parallela .

Quindi possono certamente essere utili – una lista collegata sta attualmente servendo come una delle principali strutture di supporto di almeno una nuova grande tecnologia.

(Un elenco collegato singolarmente rende una scelta vincente senza blocco – ma non senza aspettare – in questi casi, perché le operazioni principali possono essere eseguite con un singolo CAS (+ tentativi). In un moderno ambiente GC-d – come Java e .NET: il problema ABA può essere facilmente evitato: basta avvolgere gli elementi aggiunti nei nodes appena creati e non riutilizzarli, lasciare che il GC faccia il suo lavoro. La pagina sul problema ABA fornisce anche l’implementazione di un blocco stack libero – che funziona effettivamente in .Net (e Java) con un nodo (GC-ed) contenente gli elementi).

Edit : @Neil: in realtà, quello che hai menzionato su FORTRAN mi ha ricordato che lo stesso tipo di liste collegate può essere trovato nella struttura dei dati più utilizzata e abusata in .NET: il semplice Dictionary generico .NET Dictionary .

Non uno, ma molti elenchi collegati sono archiviati in un array.

  • Evita di fare molte piccole (de) allocazioni su inserti / eliminazioni.
  • Il caricamento iniziale della tabella hash è piuttosto veloce, perché l’array è riempito in sequenza (funziona molto bene con la cache della CPU).
  • Senza contare che una tabella hash concatenata è costosa in termini di memoria – e questo “trucco” taglia a metà “puntatore” su x64.

In sostanza, molte liste collegate sono archiviate in una matrice. (uno per ciascun bucket utilizzato). Una lista libera di nodes riutilizzabili è “intrecciata” tra di loro (se ci fossero eliminazioni). Un array viene allocato all’inizio / su rehash e i nodes delle catene sono mantenuti al suo interno. C’è anche un puntatore libero – un indice nell’array – che segue le eliminazioni. 😉 Quindi – ci crediate o no – la tecnica FORTRAN continua a vivere. (… e da nessun’altra parte, che in una delle strutture dati .NET più usate ;-).

Le liste collegate sono molto utili quando devi fare molti inserimenti e rimozioni, ma non troppa ricerca, su un elenco di lunghezza arbitraria (sconosciuta in fase di compilazione).

La suddivisione e l’unione (in modo bidirezionale) degli elenchi è molto efficiente.

È anche ansible combinare elenchi concatenati, ad esempio strutture ad albero possono essere implementate come elenchi concatenati “verticali” (relazioni genitore / figlio) che collegano insieme elenchi concatenati orizzontali (fratelli).

L’utilizzo di un elenco basato su array per questi scopi presenta gravi limitazioni:

  • L’aggiunta di un nuovo elemento significa che l’array deve essere riallocato (oppure è necessario allocare più spazio del necessario per consentire la crescita futura e ridurre il numero di riallocazioni)
  • La rimozione di oggetti lascia uno spazio sprecato o richiede una riallocazione
  • inserire oggetti ovunque tranne la fine comporta (possibilmente riallocando e) copiando molti dati di una posizione

Gli elenchi collegati sono molto flessibili: con la modifica di un puntatore, è ansible apportare modifiche enormi, in cui la stessa operazione sarebbe molto inefficiente in un elenco di array.

Le matrici sono le strutture dati a cui vengono generalmente confrontate le liste collegate.

Gli elenchi normalmente collegati sono utili quando è necessario apportare molte modifiche all’elenco stesso, mentre gli array si comportano meglio degli elenchi sull’accesso diretto agli elementi.

Ecco un elenco di operazioni che possono essere eseguite su elenchi e array, confrontati con il costo dell’operazione relativa (n = elenco / lunghezza dell’array):

  • Aggiungere un elemento:
    • sugli elenchi è sufficiente allocare memoria per il nuovo elemento e redirect i puntatori. O (1)
    • sugli array devi spostare la matrice. Sopra)
  • Rimozione di un elemento
    • sulle liste devi semplicemente redirect i puntatori. O (1).
    • sugli array si impiega O (n) tempo per spostare l’array se l’elemento da rimuovere non è il primo o l’ultimo elemento dell’array; altrimenti è ansible riposizionare semplicemente il puntatore all’inizio dell’array o ridurre la lunghezza dell’array
  • Ottenere un elemento in una posizione nota:
    • sulle liste devi percorrere la lista dal primo elemento all’elemento nella posizione specifica. Peggiore caso: O (n)
    • sugli array è ansible accedere immediatamente all’elemento. O (1)

Questo è un confronto a basso livello di queste due strutture di dati popolari e di base e si può vedere che le liste si comportano meglio in situazioni in cui è necessario apportare molte modifiche all’elenco (rimuovendo o aggiungendo elementi). D’altro canto, gli array si comportano meglio degli elenchi quando si accede direttamente agli elementi dell’array.

Dal punto di vista dell’allocazione della memoria, le liste sono migliori perché non è necessario avere tutti gli elementi uno accanto all’altro. D’altra parte c’è il (piccolo) sovraccarico di immagazzinare i puntatori all’elemento successivo (o anche al precedente).

Conoscere queste differenze è importante per gli sviluppatori per scegliere tra elenchi e array nelle loro implementazioni.

Si noti che questo è un confronto di liste e matrici. Ci sono buone soluzioni ai problemi qui riportati (ad esempio: SkipLists, Dynamic Arrays, ecc …). In questa risposta ho preso in considerazione la struttura di base dei dati che ogni programmatore dovrebbe conoscere.

L’elenco con collegamento singolo è una buona scelta per l’elenco libero in un allocatore di celle o in un pool di oggetti:

  1. Hai solo bisogno di una pila, quindi è sufficiente una lista collegata singolarmente.
  2. Tutto è già diviso in nodes. Non esiste un overhead di allocazione per un nodo di lista intrusivo, a condizione che le celle siano sufficientemente grandi da contenere un puntatore.
  3. Un vettore o un deque imporrebbe un sovraccarico di un puntatore per blocco. Questo è significativo dato che quando si crea l’heap per la prima volta tutte le celle sono libere, quindi è un costo iniziale. Nel peggiore dei casi, raddoppia il requisito di memoria per cella.

La lista doppiamente collegata è una buona scelta per definire l’ordinamento di una hashmap che definisce anche un ordine sugli elementi (LinkedHashMap in Java), specialmente se ordinati per ultimo accesso:

  1. Più memoria di sovraccarico rispetto a un vettore o una deque associati (2 puntatori anziché 1), ma è meglio inserire / rimuovere le prestazioni.
  2. Nessun sovraccarico di allocazione, poiché è comunque necessario un nodo per una voce di hash.
  3. La località di riferimento non è un problema aggiuntivo rispetto a un vettore o un deque di puntatori, dal momento che dovresti tirare in memoria ogni object in entrambi i casi.

Certo, puoi discutere se una cache LRU sia una buona idea, in primo luogo rispetto a qualcosa di più sofisticato e accordabile, ma se ne hai una, questa è un’implementazione abbastanza decente. Non si desidera eseguire un delete-from-middle-and-add-to-end su un vettore o un deque ad ogni accesso in lettura, ma lo spostamento di un nodo verso la coda è generalmente soddisfacente.

Sono utili quando hai bisogno di push, pop e rotazione ad alta velocità, e non ti importa dell’indicizzazione di O (n).

Gli elenchi collegati singolarmente sono l’ovvia implementazione del tipo di dati “elenco” comune nei linguaggi di programmazione funzionale:

  1. L’aggiunta alla testa è veloce, e (append (list x) (L)) e (append (list y) (L)) possono condividere quasi tutti i loro dati. Non è necessario il copy-on-write in una lingua senza scritture. I programmatori funzionali sanno come trarne vantaggio.
  2. L’aggiunta alla coda è sfortunatamente lenta, ma lo sarebbe anche qualsiasi altra implementazione.

In confronto, un vettore o una deque sarebbero in genere lenti da aggiungere alle due estremità, richiedendo (almeno nel mio esempio di due distinte appendici) che una copia sia presa dell’intero elenco (vettore), o del blocco indice e del blocco dati essere aggiunto a (deque). In realtà, potrebbe esserci qualcosa da dire lì per deque su grandi liste che hanno bisogno di aggiungere alla coda per qualche ragione, non sono abbastanza informato sulla programmazione funzionale da giudicare.

Gli elenchi collegati sono una delle scelte naturali quando non puoi controllare dove sono archiviati i tuoi dati, ma devi comunque ottenere in qualche modo da un object all’altro.

Ad esempio, quando si implementa il tracciamento della memoria in C ++ (nuova / eliminazione della sostituzione), è necessario disporre di una struttura di dati di controllo che tenga traccia di quali puntatori sono stati liberati e che è necessario implementare completamente. L’alternativa è di classificare e aggiungere un elenco collegato all’inizio di ogni blocco di dati.

Poiché sai sempre immediatamente, dove sei nella lista quando viene chiamato delete, puoi facilmente rinunciare alla memoria in O (1). Anche l’aggiunta di una nuova porzione che è stata appena malloced è in O (1). Camminare sulla lista è molto raramente necessario in questo caso, quindi il costo O (n) non è un problema qui (camminare su una struttura è O (n) in ogni caso).

Dalla mia esperienza, implementando matrici sparse e cumuli di Fibonacci. Gli elenchi collegati ti offrono un maggiore controllo sulla struttura generale di tali strutture di dati. Anche se non sono sicuro che le matrici sparse possano essere implementate al meglio usando liste collegate – probabilmente c’è un modo migliore, ma ha davvero aiutato ad imparare i dettagli di matrici sparse usando gli elenchi collegati in CS undergrade 🙂

Un esempio di buon utilizzo per una lista collegata è dove gli elementi della lista sono molto grandi cioè. abbastanza grande che solo uno o due possono essere contenuti nella cache della CPU allo stesso tempo. A questo punto il vantaggio che i contenitori a blocchi contigui come vettori o array per l’iterazione sono più o meno annullati, e un vantaggio in termini di prestazioni potrebbe essere ansible se molti inserimenti e rimozioni si verificano in tempo reale.

Considera che una lista collegata potrebbe essere molto utile in un’implementazione di stile di Domain Driven Design di un sistema che include parti che si intrecciano con la ripetizione.

Un esempio che viene in mente potrebbe essere se si dovesse modellare una catena sospesa. Se volevi sapere qual era la tensione su ogni particolare link, la tua interfaccia potrebbe includere un getter per il peso “apparente”. L’implementazione del quale includerebbe un link che chiede il suo prossimo link per il suo peso apparente, quindi aggiungendo il proprio peso al risultato. In questo modo, l’intera lunghezza fino alla fine verrebbe valutata con una singola chiamata dal client della catena.

Essendo un sostenitore del codice che legge come il linguaggio naturale, mi piace come questo permetterebbe al programmatore di chiedere a un link a catena quanto peso sta portando. Mantiene anche la preoccupazione di calcolare questi figli di proprietà entro i confini dell’implementazione del collegamento, eliminando la necessità di un servizio di calcolo del peso della catena “.

Uno dei casi più utili che trovo per le liste collegate che lavorano in campi critici per le prestazioni come l’elaborazione di mesh e immagini, motori fisici e raytracing è quando l’uso di liste collegate migliora la localizzazione di riferimento e riduce l’allocazione dell’heap e talvolta riduce anche l’uso della memoria rispetto a le semplici alternative.

Ora questo può sembrare un ossimoro completo che le liste concatenate potrebbero fare tutto ciò poiché sono famigerate per fare spesso il contrario, ma hanno una proprietà unica in quanto ogni nodo di lista ha una dimensione fissa e requisiti di allineamento che possiamo sfruttare per consentire devono essere archiviati in modo contiguo e rimossi in tempo costante in modi che le cose di dimensioni variabili non possono.

Di conseguenza, prendiamo un caso in cui vogliamo fare l’equivalente analogico di memorizzare una sequenza di lunghezza variabile che contiene un milione di sottosequenze di lunghezza variabile nidificate. Un esempio concreto è una mesh indicizzata che memorizza un milione di poligoni (alcuni triangoli, alcuni quadrupli, alcuni pentagoni, alcuni esagoni, ecc.) Ea volte i poligoni vengono rimossi da qualsiasi punto della mesh e talvolta i poligoni vengono ricostruiti per inserire un vertice in un poligono esistente o rimuovi uno. In tal caso, se immagazziniamo un milione di minuscoli std::vectors vector, allora finiremo per affrontare un’allocazione dell’heap per ogni singolo vettore e anche un uso potenzialmente esplosivo della memoria. Un milione di piccoli SmallVectors potrebbe non soffrire di questo problema tanto nei casi più comuni, ma il loro buffer preallocato che non è allocabile separatamente all’heap potrebbe comunque causare un uso esplosivo della memoria.

Il problema qui è che un milione di istanze di std::vector proverebbero a memorizzare un milione di cose a lunghezza variabile. Le cose di lunghezza variabile tendono a desiderare un’allocazione dell’heap poiché non possono essere memorizzate in modo efficace in modo contiguo e rimosse in tempo costante (almeno in modo semplice senza un allocatore molto complesso) se non memorizzassero il loro contenuto altrove nell’heap.

Se, invece, lo facciamo:

 struct FaceVertex { // Points to next vertex in polygon or -1 // if we're at the end of the polygon. int next; ... }; struct Polygon { // Points to first vertex in polygon. int first_vertex; ... }; struct Mesh { // Stores all the face vertices for all polygons. std::vector fvs; // Stores all the polygons. std::vector polys; }; 

… quindi abbiamo ridotto drasticamente il numero di allocazioni dell’heap e di errori di cache. Invece di richiedere un’allocazione dell’heap e potenziali errori di cache obbligatori per ogni singolo poligono a cui accediamo, ora richiediamo solo l’allocazione dell’heap quando uno dei due vettori memorizzati nell’intera mesh supera la loro capacità (un costo ammortizzato). E mentre il passo per passare da un vertice all’altro potrebbe ancora causare la sua condivisione di errori di cache, è ancora spesso inferiore a se ogni singolo poligono memorizza una matrice dynamic separata poiché i nodes sono archiviati in modo contiguo e c’è una probabilità che un vertice vicino possa si può accedere prima dello sfratto (specialmente considerando che molti poligoni aggiungeranno i loro vertici tutto in una volta, il che rende la parte del leone dei vertici del poligono perfettamente contigua).

Ecco un altro esempio:

inserisci la descrizione dell'immagine qui

… dove le celle della griglia vengono utilizzate per accelerare la collisione tra particelle e particelle, diciamo per 16 milioni di particelle che si muovono su ogni singolo fotogramma. Nell’esempio della griglia di particelle, usando liste collegate possiamo spostare una particella da una cella di griglia a un’altra semplicemente cambiando 3 indici. Cancellare da un vettore e tornare a un altro può essere molto più costoso e introdurre più allocazioni di heap. Le liste collegate riducono anche la memoria di una cella fino a 32-bit. Un vettore, a seconda dell’implementazione, può preallocare la sua matrice dynamic al punto in cui può richiedere 32 byte per un vettore vuoto. Se abbiamo circa un milione di celle della griglia, questa è una differenza.

… ed è qui che trovo gli elenchi concatenati più utili in questi giorni, e trovo particolarmente utile la varietà “elenco collegato indicizzato”, poiché gli indici a 32 bit dimezzano i requisiti di memoria dei collegamenti su macchine a 64 bit e implicano che il i nodes sono memorizzati in modo contiguo in una matrice.

Spesso li combino anche con elenchi gratuiti indicizzati per consentire rimozioni e inserimenti costanti ovunque:

inserisci la descrizione dell'immagine qui

In tal caso, l’indice next punta al successivo indice libero se il nodo è stato rimosso o al successivo indice utilizzato se il nodo non è stato rimosso.

E questo è il caso d’uso numero 1 che trovo per le liste collegate in questi giorni. Quando vogliamo archiviare, diciamo, un milione di sotto-sequenze a lunghezza variabile facendo la media, ad esempio, di 4 elementi ciascuna (ma a volte con elementi che vengono rimossi e aggiunti a una di queste sottosequenze), l’elenco collegato ci consente di memorizzare 4 milioni nodes di lista collegati contigui invece di 1 milione di contenitori che sono allocati individualmente per ciascun heap: un vettore gigante, cioè non un milione di piccoli.

Ho usato elenchi concatenati (anche elenchi collegati doppiamente) in passato in un’applicazione C / C ++. Questo era precedente a .NET e persino a stl.

Probabilmente non userò una lista collegata ora in un linguaggio .NET perché tutto il codice di attraversamento di cui hai bisogno è fornito per te tramite i metodi di estensione Linq.

Ci sono due operazioni complementari che sono banalmente O (1) sulle liste e molto difficili da implementare in O (1) in altre strutture dati – rimuovendo e inserendo un elemento dalla posizione arbitraria, assumendo che sia necessario mantenere l’ordine degli elementi.

Le mappe hash possono ovviamente fare l’inserimento e la cancellazione in O (1), ma non è ansible eseguire iterazioni sugli elementi in ordine.

Dato il fatto sopra, la mappa di hash può essere combinata con un elenco collegato per creare una cache LRU elegante: una mappa che memorizza un numero fisso di coppie chiave-valore e rilascia la chiave meno recente per far spazio a quelle nuove.

Le voci nella mappa di hash devono avere dei puntatori ai nodes della lista collegata. Quando si accede alla mappa hash, il nodo dell’elenco collegato viene scollegato dalla sua posizione corrente e spostato all’inizio dell’elenco (O (1), yay per gli elenchi collegati!). Quando è necessario rimuovere l’elemento utilizzato meno di recente, è necessario eliminare quello dalla coda dell’elenco (di nuovo O (1) assumendo che si mantenga il puntatore al nodo di coda) insieme alla relativa voce di mappa hash (quindi backlink da l’elenco per la mappa di hash è necessario).