Quali sono gli esempi reali di quando devono essere utilizzati gli elenchi collegati?

Question

Un altro programmatore ha affermato di non aver trovato un caso d'uso per l'utilizzo di una struttura di dati dell'elenco collegato in qualsiasi software professionale nella sua carriera. Non riuscivo a pensare a nessun buon esempio in cima alla mia testa. È principalmente uno sviluppatore C# e Java

Qualcuno può dare qualche esempio in cui questa era la struttura dati corretta per risolvere un particolare problema del mondo reale?

correlati:What is a practical, real world example of the Linked List?

Answer 1

Un esempio del mondo reale sarebbe una coda FIFO. Un semplice elenco basato su array è piuttosto negativo per questo perché è necessario aggiungere a una estremità e rimuovere dall'altra parte, e una di queste operazioni sarà O (n) con un elenco basato su array (a meno che non si aggiunga una logica aggiuntiva a funziona con un indice di inizio e fine), mentre entrambi sono O (1) con un elenco collegato senza sforzi aggiuntivi.

Answer 2

pile e code sono esempi di liste collegate.

Answer 3

Per problemi in cui il numero di nodi massimi è vincolato a 100 o inferiore o così, le liste collegate sono una soluzione ragionevole. Lo stesso può essere vero per cose come bubble sort e altre cose che si pensa siano subottimali.

Answer 4

Le liste collegate offrono numerosi vantaggi rispetto alle strutture di dati comparabili come gli array statici o in espansione dinamica.

1. LinkedLists dose non richiedono blocchi contigui di memoria e quindi possono aiutare a ridurre la frammentazione della memoria
2. LinkedLists supportano efficiente rimozione di elementi (array dinamici solito forzare un cambiamento di tutti gli elementi).
3. LinkedLists supportano efficiente aggiunta di elementi (matrici dinamiche possono causare una ridistribuzione + copiare se un particolare add supera la capacità di corrente)

Qualunque luogo dove questi vantaggi sarebbero notevolmente utile per un programma (e la svantaggi di una LinkedList erano trascurabili) sarebbe un posto dove usare una LinkedList.

Answer 5

Come sottolinea daustin777, le liste concatenate sono tutte intorno a te e potresti persino non saperlo. Ma la praticità della questione è che consentono di eseguire alcune operazioni piuttosto semplici con relativa facilità e flessibilità. Ad esempio, non per ordinare, basta scambiare i puntatori in giro. Hai bisogno di inserire o rimuovere in luoghi arbitrari? Inserisci o rimuovi i tuoi puntatori all'interno dell'elenco. Necessario per iterare avanti e indietro ... lista collegata. Pur non essendo precisamente un esempio di business, spero che questo ti chiarisca abbastanza per applicarlo al tuo caso aziendale reale.

Answer 6

Un immutabile elenco collegato è una struttura molto preziosa, dal momento che è possibile "condividere la struttura" con altre liste con la stessa coda. La maggior parte dei linguaggi funzionali include un tipo di lista collegata immutabile come una delle loro strutture dati fondamentali, e questi tipi sono usati dappertutto.

Answer 7

lista pro collegati:

• stoccaggio dinamico annulla frammentazione
• inserimento/rimozione rapida
• accesso rapido al primo elemento (e termina se bidirezionale implementato)
• efficiente utilizzo della memoria

Lista collegata contro:

• lenta traslazione

Fuori dalla mia testa, mi piacerebbe implementare pile, code e messagepumps usando liste concatenate. Implementerei anche un datatree usando elenchi concatenati multi-riferimento per l'inserimento/rimozione veloce.

Answer 8

pile e code sono molto chiari esempi di liste collegate, ma come altri già li hanno già detto mi piacerebbe aggiungere qualche altro esempio: negozi

DOM nodi come le liste concatenate. Un campione javascript semplice che è davvero la stessa in tutte le lingue:

for (var node = parent.firstChild; node != null; node = node.nextSibling) { 
    // .. 
} 

immagino che uno sviluppatore Java ha incontrato XML ad un certo punto.

Gli alberi sono un altro buon esempio di elenchi concatenati, anche se non sono semplici di una dimensione. Qualcuno che ha fatto un sacco di sviluppo java ha probabilmente incontrato TreeMaps e TreeSet.

L'intera discussione mi sembra un po 'sciocca. Le liste collegate sono una struttura di dati fondamentale che viene utilizzata ovunque. L'unica ragione per cui si potrebbe pensare che lui/lei non li abbia mai incontrati è che non devi davvero preoccuparti dell'implementazione delle strutture dati nei linguaggi di alto livello di oggi, ma ovviamente sono ancora lì.

Answer 9

Si verificano sempre, ovunque un oggetto ha una proprietà che punta a un altro oggetto dello stesso tipo. Nel CLR, le eccezioni formano un elenco collegato, a causa della proprietà InnerException.

Answer 10

Come già detto, le liste collegate sono molto utili quando è necessario inserire ed eliminare elementi.

Ad esempio, per facilitare il debug della gestione della memoria nel mio codice, ho recentemente implementato una lista di collegamenti tra tutti i miei oggetti conteggio di refrenza in modo che alla fine del programma (quando i rifrattori dovessero aver tutti azzerato e cancellato gli oggetti) potrei vedere esattamente ciò che rimaneva ancora, risultando utile nella mia capacità di trovare un singolo oggetto alla radice del problema.

CPython implementa qualcosa di simile con una lista di collegamenti massiccia tra quasi tutti quando è costruita con il debug.

Answer 11

Le liste collegate intrusive sono bestie interessanti per lo sviluppo del gioco.Ad esempio, è pratica piuttosto comune per avere un singly- invadente o doppiamente-linked "render" lista:

 
class Renderable /* or class Object, whatever */ 
{ 
    // ... 
    Renderable * m_pNext; 
    Renderable * m_pPrev; // or not, if singly-linked 
    // ... 
} 

Come Renderables entrano in e fuori l'esistenza possono registrarsi con questa lista - senza causare alcuna memoria allocazione. Se la loro profondità di rendering o priorità è cambiata, possono rimuovere e reinserire se stessi, ecc.

Quando arriva il momento di eseguire il rendering, tutto ciò che devi fare è trovare il capo dell'elenco e passare attraverso, chiamando il metodo appropriato!

(Esistono, naturalmente, molte varianti su questo tema, con più elenchi separati, ecc. E non è necessario avere un elenco intrusivo per fare in modo che funzioni, ma trovo gli intrusi interessanti.)

Answer 12

Gli elenchi collegati (paired with a hashtable) sono veramente utili per LRU Caches.

Ogni Get ha bisogno di eseguire il bump di un nodo nella parte anteriore dell'elenco, un'operazione che è davvero economica con gli elenchi collegati.

Answer 13

Rispondendo al tag "Strutture dati", ad un livello basso come l'assemblaggio, le liste concatenate sono un modo ideale per memorizzare elenchi di lunghezza variabile di altre strutture di dati. Non esiste un sovraccarico per mantenere la lunghezza o la fine dell'elenco e non è necessario per gli elementi dell'elenco di dimensioni fisse. L'ultimo motivo si applica anche ai linguaggi di livello superiore.

Answer 14

Come forse il migliore esempio del mondo reale in .Net considera lo MultiCastDelegate.

Gli elenchi collegati implementati in questo modo, in cui l'aspetto dell'elenco concatenamento viene eseguito direttamente nel tipo anziché come contenitore separato, può essere estremamente potente ed efficiente. Vengono comunque con una varietà di compromessi.
Uno ovvio è la duplicazione del codice, è necessario cuocere questa logica in ciascun tipo. Tecniche come l'estensione di una classe base che fornisce il puntatore sono disordinate (si perde una forte digitazione senza generici) e spesso inaccettabili dal punto di vista delle prestazioni.
Un altro è che si è limitati a un'implementazione per tipo. Non è possibile creare una struttura singolarmente collegata in una doppia collegata senza inserire un campo aggiuntivo in ogni istanza e aggiornando tutto il codice pertinente.

Answer 15

Ho scritto un'estensione BIOS (fondamentalmente un driver di periferica per un BIOS, scritta in assembly) per un controller host USB. - Implementare una struttura di dati apparentemente astratta di alto livello come una lista collegata in assemblea non è così difficile come sembra. - Il controller ha gestito le richieste di I/O per tastiera e disco utilizzando un elenco collegato di pacchetti nella memoria principale. Ho mantenuto un pool di pacchetti gratuiti in un'altra lista collegata. L'esecuzione dell'I/O consisteva essenzialmente nell'acquisizione di un pacchetto gratuito dall'inizio della lista gratuita, nella configurazione del pacchetto, nell'aggiunta del pacchetto all'elenco dei dispositivi e nella riaggiunta del pacchetto all'inizio del pool libero al termine dell'I/O. Gli elenchi collegati sono velocissimi per spostarsi su oggetti come questo, specialmente quando gli oggetti sono grandi, poiché gli oggetti non devono spostarsi. Solo i loro indicatori devono essere aggiornati.

Una coda basata su array avrebbe richiesto:

• utilizzando un inizio/fine puntatore indice, che è veloce, ma richiede che fissa il dimensione della coda in modo che il produttore deve aspettare quando la coda del consumatore è pieno e bloccando la coda, mentre l'intero pacchetto è piena se non v'è più di un produttore
• spostando tutti gli elementi in coda ogni volta che si inserisce/rimuovere, che è lento per oggetti di grandi dimensioni

liste Quindi, collegate sono un bel modo per implementare a n coda arbitrariamente lunga di tipo first-in-first-out di oggetti di grandi dimensioni.

Un'altra cosa da fare attenzione è che per gli oggetti piccoli o dove si allocano oggetti da un heap convenzionale invece di un pool gratuito personalizzato, gli array possono essere più veloci perché la copia non è così lenta se non viene eseguita spesso, e l'allocazione ripetuta dall'heap che una lista collegata richiederebbe ogni volta che viene aggiunto un nuovo elemento è lenta.

Ovviamente, è possibile simulare e misurare il proprio scenario particolare con un codice di prova throwaway per trovare la risposta. Mi piace eseguire cicli qualche milione di volte con elenchi e array collegati, con oggetti piccoli e grandi e tempo per quanto tempo ciascuno impiega in tempo reale. A volte sarai sorpreso.

Answer 16

lista collegata è la struttura essenziale di dati per Dancing Links, che è la tecnica utilizzata per implementare in modo efficiente Algorithm X, che è un algoritmo di backtracking per trovare tutte le soluzioni per la NP-completo exact cover problema, a cui molti problemi difficili sono naturalmente riducibili a .

Answer 17

Se posso rispondere a questa domanda in modo leggermente diverso rispetto ad altri, ultimamente ho utilizzato elenchi collegati per organizzare elenchi di musica. Gli elenchi forniscono un modo eccellente per archiviare e ordinare la musica per artista, canzone, album, persino valutazioni o durata della canzone. Il mio è una lista doppiamente collegata, ma potrei vedere che è applicabile anche con un elenco collegato singolarmente. Anche le liste della spesa si adatterebbero, e se sei un DOC come mia madre, puoi facilmente organizzarle per essere il corridoio ei cibi surgelati!

Se includiamo stack e code, l'ovvio per le code è una coda di stampa o una playlist di musica (le liste in qualsiasi senso sono ovviamente buone).

Answer 18

Alcuni esempi di elenco singolo collegato.

1. Annulla il pulsante di qualsiasi applicazione come Microsoft Word, Paint, ecc. Un elenco di stati collegati.
2. Navigazione GPS: un elenco collegato di dati mappa. Viaggiare da origine a destinazione è un esempio di attraversamento di tutti i nodi. Il reinstradamento di da un GPS è un esempio delle operazioni di aggiunta e rimozione dei dati della mappa.

Alcuni esempi di doppio elenco collegato.

1. del browser Avanti e Pulsante Precedente: una lista concatenata di URL Microsoft
2. Immagine del Viewer Avanti e Button precedente: una lista concatenata di immagini
3. Annulla e il pulsante di Photoshop, una lista concatenata di stati Redo.