Usi elenchi collegati, elenchi collegati doppiamente e così via, nella programmazione aziendale?

Question

Le strutture dati come le liste collegate sono puramente accademiche per la programmazione reale o le utilizzate davvero? Sono cose che sono coperte dai generici in modo che non sia necessario costruirle (presumendo che il tuo linguaggio abbia generici)? Non sto discutendo sull'importanza di capire quello che sono, solo il loro uso al di fuori del mondo accademico. Chiedo da un web front-end, prospettiva del database back-end. Sono sicuro che qualcuno da qualche parte costruisce questi. Sto chiedendo dal mio contesto.

Grazie.

MODIFICA: Sono generici in modo che non sia necessario creare elenchi collegati e simili?

Answer 1

Dipenderà dalla lingua e dai framework che si stanno utilizzando. La maggior parte delle lingue e degli schemi moderni non ti faranno reinventare queste ruote. Invece, forniranno cose come List<T> o HashTable.

EDIT:

Abbiamo probabilmente usare liste collegate per tutto il tempo, ma non ce ne accorgiamo. Non dobbiamo scrivere le implementazioni delle liste collegate da soli, perché i framework che usiamo li hanno già scritti per noi.

Si potrebbe anche essere confuso su "generici". Potresti riferirti a elenchi generici come List<T>. Questo è identico all'elenco di classi non generiche, ma dove l'elemento è sempre di tipo T. Probabilmente è implementato come una lista collegata, ma non ci dobbiamo preoccupare di questo.

Inoltre, non dobbiamo preoccuparci dell'allocazione della memoria fisica, di come funzionano gli interrupt o di come creare un file system. Abbiamo sistemi operativi per farlo per noi. Ma a scuola si può insegnare che l'informazione è la stessa.

Answer 2

Certamente. Molte implementazioni "Elenco" nei linguaggi moderni sono in realtà liste concatenate, talvolta in combinazione con matrici o tabelle hash per l'accesso diretto (per indice anziché per iterazione).

Gli elenchi collegati (in particolare le liste a doppio collegamento) sono molto comunemente utilizzati nelle strutture di dati "reali".

Avrei il coraggio di dire che ogni linguaggio comune ha un'implementazione predefinita dell'elenco collegato, sia come lingua primitiva, libreria di modelli nativi (ad esempio C++), libreria nativa (ad es. Java) o implementazione di terze parti (probabilmente aperta -fonte).

Detto questo, diverse volte in passato ho scritto da solo l'implementazione di un elenco collegato da zero durante la creazione di codice di infrastruttura per strutture di dati complesse. A volte è una buona idea avere il pieno controllo dell'implementazione, e talvolta è necessario aggiungere una "svolta" alla classica implementazione per soddisfare i requisiti specifici. Non c'è giusto o sbagliato quando si tratta di codificare la propria implementazione, purché si comprendano le alternative e i trade-off. Nella maggior parte dei casi, e certamente in linguaggi molto moderni come C#, lo eviterei.

Un altro punto è quando è necessario utilizzare elenchi o array/vettori o tabelle hash. Dalla tua domanda capisco che sei a conoscenza dei compromessi qui, quindi non ne parlerò troppo, ma fondamentalmente, se il tuo uso principale sta attraversando gli elenchi per ordine, e la dimensione dell'elenco può variare in modo significativo, un elenco potrebbe essere un'opzione praticabile Un'altra considerazione è il tipo di inserimento. Se un caso d'uso comune è "inserendo nel mezzo", gli elenchi hanno un vantaggio significativo sugli array/vettori.Posso andare avanti, ma questa informazione è nei classici libri di CS :)

Precisazione: la mia risposta è indipendente dal linguaggio e non si riferisce specificamente a Generics che a mio avviso ha un'implementazione di lista collegata.

Answer 3

Sono anni che sviluppo la linea di applicazioni aziendali (.NET) e posso solo pensare a un'istanza in cui ho utilizzato l'elenco collegato e anche in quel caso non ho dovuto creare l'oggetto.

Questa è stata solo la mia esperienza.

Answer 4

Direi che dipende dall'utilizzo, in alcuni casi sono più veloci dei tipici contenitori ad accesso casuale.

Inoltre, penso che siano utilizzati da alcune librerie come un tipo di raccolta sottostante, quindi quello che potrebbe sembrare un elenco non collegato potrebbe effettivamente essere uno sotto.

Answer 5

In un'applicazione C/C++ che ho sviluppato nella mia ultima società, abbiamo utilizzato elenchi doppiamente collegati tutto il tempo. Erano essenziali per quello che stavamo facendo, ovvero la grafica 3D in tempo reale.

Answer 6

Sì, ci sono applicazioni del mondo reale che utilizzano la lista collegata, a volte devo mantenere una grande applicazione che fa molto uso di liste collegate.

E sì, le liste concatenate sono incluse in quasi tutte le librerie di classi da C++/STL a .net.

E vorrei invece utilizzare gli array.

Nel mondo reale le liste concatenate sono LENTRE a causa di cose come il paging e le dimensioni della cache della CPU (le liste collegate tendono a diffondere i dati e questo rende più probabile che sia necessario accedere ai dati da diverse aree di memoria e che sia molto più lento sui computer di oggi rispetto all'utilizzo di array che memorizzano tutti i dati in un'unica sequenza).

Google "località di riferimento" per ulteriori informazioni.

Answer 7

Non ho mai usato elenchi fatti a mano tranne che per i compiti a casa all'università.

Answer 8

Sì, tutti i tipi di strutture dati sono molto utili nello sviluppo quotidiano del software. Nella maggior parte delle lingue che conosco (C/C++/Python/Objective-C) ci sono framework che implementano tali strutture dati in modo da non dover reinventare la ruota.

E sì, le strutture dati non sono solo per gli accademici, sono molto utili e non si sarebbe in grado di scrivere software senza di loro (dipende da cosa si fa).

Si utilizzano le strutture dati in code di messaggi, mappe dati, tabelle hash, mantenendo i dati ordinati, accesso/rimozione/inserimento rapido e così via dipende da ciò che deve essere fatto.

Answer 9

Un elenco collegato singolarmente è l'unico modo per avere una lista immutabile efficiente in memoria che può essere composta per "mutarlo". Guarda come lo fa Erlang. Può essere leggermente più lento di un elenco supportato da array ma ha proprietà molto utili in implementazioni multithreaded e puramente funzionali.

Answer 10

Sì, lo so. Tutto dipende dalla situazione. Se non conserverò un sacco di dati al loro interno, o se l'applicazione specifica ha bisogno di una struttura FIFO, li userò senza ripensamenti perché sono veloci da implementare.

Tuttavia, nelle applicazioni per altri sviluppatori che conosco, ci sono volte in cui una lista collegata si adatterebbe perfettamente tranne che la scarsa localizzazione causa un sacco di errori di cache.

Answer 11

A seconda dell'utilizzo, una lista collegata potrebbe essere l'opzione migliore. Le eliminazioni dalla parte anteriore dell'elenco sono molto più veloci con un elenco collegato rispetto a un elenco di array.

In un programma Java che mantengo il profilo ho dimostrato che potrei aumentare le prestazioni passando da ArrayList a LinkedList per un elenco che aveva molte eliminazioni all'inizio.

Answer 12

Non riesco a immaginare molti programmi che non si occupano di elenchi. Nel momento in cui è necessario gestire più di 1 cosa, sono necessarie liste in tutte le forme e forme, poiché è necessario un luogo in cui archiviare queste cose. Tale elenco potrebbe essere un elenco univoco/doppiamente collegato, un array, un set, una tabella hash se è necessario indicizzare le cose in base a una chiave, una coda di priorità se è necessario ordinarla ecc.

In genere si memorizza queste liste in un sistema di database, ma da qualche parte è necessario recuperarle dal db, memorizzarle nell'applicazione e manipolarle, anche se è semplice recuperare un piccolo elenco di cose che si popolano in una casella combinata a discesa.

In questi giorni, in linguaggi come C#, Python, Java e molti altri, di solito si è lontani dal dover implementare le proprie liste. Questi linguaggi sono dotati di una grande quantità di astrazioni di contenitori in cui è possibile archiviare materiale. O tramite librerie standard o integrate nella lingua.

Sei ancora a vantaggio dell'apprendimento di questi argomenti, ad es. se stai lavorando con C# vorresti sapere come funziona una ArrayList, e se preferisci scegliere ArrayList o qualcos'altro a seconda della tua necessità di aggiungere/inserire/cercare/indice casuale tale elenco.