È possibile utilizzare un elenco collegato quando si desidera inserire e eliminare a buon mercato gli elementi e quando non è importante che gli elementi non siano gli uni accanto agli altri in memoria.
Questo è molto astratto e vorrei una spiegazione concreta del perché un elenco collegato dovrebbe essere usato piuttosto che un array. Non ho molta esperienza con la programmazione, quindi non ho avuto molta (o nessuna) esperienza del mondo reale.
Ecco qualcosa in parte tra un esempio e un'analogia. Hai alcune commissioni da fare, quindi prendi un pezzo di carta e scrivi:
Quindi ti ricordi che devi anche comprare francobolli. A causa della geografia della tua città, devi farlo dopo la banca. Potresti copiare l'intero elenco su un nuovo foglio di carta:
oppure potresti scrivere su quello che hai:
Come hai pensato ad altre commissioni, potresti scriverle in fondo alla lista, ma con le frecce che ti ricordano in che ordine farle. Questa è una lista collegata. È più veloce e più facile che copiare l'intera lista ogni volta che aggiungi qualcosa.
Quindi il tuo cellulare squilla mentre sei in banca "hey, ho preso i francobolli, non ne raccolgo più". Devi solo rimuovere STAMPS dalla lista, non riscriverne uno completamente nuovo senza STAMPS.
Ora potresti effettivamente implementare un elenco di commissioni nel codice (magari un'app che metta in ordine le commissioni in base alla tua geografia) e c'è una ragionevole possibilità che tu utilizzi effettivamente un elenco collegato per quello nel codice. Si desidera aggiungere e rimuovere molti articoli, questioni relative all'ordine, ma non si desidera ricopiare l'intero elenco dopo ogni inserimento o eliminazione.
Lo "stack di chiamate" in linguaggio C è implementato come elenco collegato in x86 (e la maggior parte delle altre) API binarie.
Cioè, la chiamata in procedura in linguaggio C segue una disciplina first-in, last-out. Il risultato dell'esecuzione di chiamate di funzione (eventualmente ricorsive) viene definito "stack di chiamate", o talvolta anche solo "stack".
L'istruzione CALL x86 finisce con l'impiantare un elenco collegato usando lo "stack di chiamate". Un'istruzione CALL spinge il contenuto del registro% EIP, l'indirizzo dell'istruzione dopo il CALL sulla memoria dello stack. Il prologo chiamato-fuction spinge il contenuto del registro% EBP, l'indirizzo più basso delle variabili locali nella functio di chiamata, sulla memoria dello stack. Quindi il prologo della funzione chiamata imposta% EBP sulla base dello stack della funzione corrente.
Ciò significa che% EBP è un puntatore a una posizione di memoria che contiene l'indirizzo del valore% EBP della funzione chiamante. Non è altro che una lista concatenata, implementata parzialmente in hardware tramite CALL .
Per quanto riguarda ciò che è utile, è il modo in cui le CPU x86 implementano le chiamate alle funzioni, in particolare le chiamate alle funzioni in cui la funzione ha la propria copia degli argomenti e le variabili locali della funzione. Ogni chiamata di funzione invia alcune informazioni sullo "stack di chiamate" che consente alla CPU di riprendere da dove era stata interrotta nella funzione di chiamata, senza interferenze dalla funzione chiamata o dalla funzione di chiamata.
Un elenco collegato può essere utilizzato per implementare una coda di messaggi.
Una coda di messaggi è una struttura in cui vengono archiviate le informazioni sugli eventi per l'elaborazione successiva. Ad esempio, quando l'utente preme un tasto o sposta il mouse, questo è un evento. Un'applicazione potrebbe essere occupata nel momento in cui si verifica l'evento, quindi non ci si può aspettare che elabori l'evento nel momento esatto in cui si verifica. Quindi, l'evento viene inserito in una coda di messaggi, (informazioni su quale tasto è stato premuto, o dove è stato spostato il mouse) e quando l'applicazione ha un po 'di tempo da perdere, controlla la coda dei messaggi, recupera gli eventi da esso e processa loro. (Questo accade in un lasso di tempo di millisecondi, quindi non è evidente.)
Dallo scenario di utilizzo che ho appena descritto, dovrebbe essere ovvio che non ci interessa mai avere accesso casuale agli eventi memorizzati nella coda dei messaggi; ci interessa solo essere in grado di archiviare messaggi e recuperarli. Quindi, ha senso usare un elenco collegato, che fornisce un tempo di inserimento / rimozione ottimale.
(Si prega di non entrare nel gioco per indicare che una coda di messaggi è probabile, o più probabile, o quasi altrettanto probabile, da implementare usando una lista circolare di array, che è un dettaglio tecnico, e ha una limitazione: tu è possibile memorizzare solo un numero limitato di messaggi.)
Leggi altre domande sui tag data-structures linked-list