Array contro elenco collegato

Perché qualcuno dovrebbe voler usare una lista collegata su un array?

Codificare una lista concatenata è, senza dubbio, un po ‘più di lavoro rispetto all’utilizzo di un array e ci si potrebbe chiedere cosa giustificerebbe lo sforzo aggiuntivo.

Penso che l’inserimento di nuovi elementi sia banale in una lista collegata, ma è un compito importante in un array. Ci sono altri vantaggi nell’usare un elenco collegato per memorizzare un insieme di dati anziché archiviarlo in un array?

Questa domanda non è un duplicato di questa domanda perché l’altra domanda si rivolge specificamente a una particolare class Java mentre questa domanda riguarda le strutture di dati generali.

  • È più facile memorizzare dati di dimensioni diverse in un elenco collegato. Un array presuppone che ogni elemento abbia esattamente la stessa dimensione.
  • Come hai detto, è più facile per una lista collegata crescere organicamente. Le dimensioni di un array devono essere conosciute in anticipo o ricreate quando deve crescere.
  • Mischiare una lista collegata è solo questione di cambiare cosa punta a cosa. Mischiare un array è più complicato e / o richiede più memoria.
  • Finché le tue iterazioni avvengono tutte in un contesto “foreach”, non perdi nessuna prestazione in iterazione.

Un’altra buona ragione è che le liste concatenate si prestano bene a implementazioni multi-threaded efficienti. La ragione di ciò è che i cambiamenti tendono ad essere locali, influenzando solo un puntatore o due per l’inserimento e la rimozione in una parte localizzata della struttura dati. Quindi, puoi avere molti thread che lavorano sullo stesso elenco collegato. Inoltre, è ansible creare versioni senza blocco utilizzando operazioni di tipo CAS ed evitare del tutto blocchi pesanti.

Con un elenco collegato, gli iteratori possono anche attraversare l’elenco mentre si verificano modifiche. Nel caso ottimistico in cui le modifiche non si scontrano, gli iteratori possono continuare senza contesa.

Con un array, qualsiasi modifica che modifica la dimensione dell’array richiede probabilmente il blocco di una grande porzione dell’array e infatti, è raro che ciò avvenga senza un blocco globale sull’intero array, quindi le modifiche si fermano agli affari del mondo.

Wikipedia ha una sezione molto buona sulle differenze.

Gli elenchi collegati presentano numerosi vantaggi rispetto agli array. Gli elementi possono essere inseriti negli elenchi concatenati indefinitamente, mentre un array alla fine si riempie o deve essere ridimensionato, un’operazione costosa che potrebbe non essere nemmeno ansible se la memoria è frammentata. Allo stesso modo, una matrice dalla quale vengono rimossi molti elementi può diventare inutilmente vuota o ridurla.

D’altra parte, gli array consentono l’accesso casuale, mentre gli elenchi collegati consentono solo l’accesso sequenziale agli elementi. Gli elenchi collegati singolarmente, infatti, possono essere attraversati solo in una direzione. Questo rende gli elenchi collegati inadatti per le applicazioni in cui è utile cercare rapidamente un elemento tramite il suo indice, come ad esempio heapsort. L’accesso sequenziale agli array è anche più veloce rispetto agli elenchi collegati su molte macchine a causa della località di riferimento e delle cache di dati. Gli elenchi collegati non ricevono quasi alcun beneficio dalla cache.

Un altro svantaggio delle liste collegate è la memoria aggiuntiva necessaria per i riferimenti, che spesso li rende poco pratici per elenchi di elementi di dati di piccole dimensioni come caratteri o valori booleani. Può anche essere lento, e con un allocatore ingenuo, dispendioso, allocare memoria separatamente per ogni nuovo elemento, un problema generalmente risolto utilizzando i pool di memoria.

http://en.wikipedia.org/wiki/Linked_list

Ne aggiungerò un’altra: le liste possono fungere da strutture dati puramente funzionali .

Ad esempio, puoi avere elenchi completamente diversi che condividono la stessa sezione finale

 a = (1 2 3 4, ....) b = (4 3 2 1 1 2 3 4 ...) c = (3 4 ...) 

vale a dire:

 b = 4 -> 3 -> 2 -> 1 -> a c = a.next.next 

senza dover copiare i dati puntati da a a b e c .

Questo è il motivo per cui sono così popolari nei linguaggi funzionali, che usano variabili immutabili – le operazioni di prepend e di tail possono avvenire liberamente senza dover copiare i dati originali – funzionalità molto importanti quando si tratta di dati immutabili.

L’unione di due elenchi concatenati (in particolare due elenchi collegati doppiamente) è molto più veloce dell’unione di due array (presupponendo che l’unione sia distruttiva). Il primo prende O (1), il secondo prende O (n).

EDIT: Per chiarire, intendevo “fondere” qui nel senso non ordinato, non come nell’unione di fusione. Forse “concatenare” sarebbe stata una parola migliore.

Inoltre, l’inserimento nel mezzo della lista è più facile – è anche molto più facile da cancellare dal centro di una lista collegata che da una matrice.

Ma francamente, non ho mai usato una lista collegata. Ogni volta che avevo bisogno di un inserimento e di una cancellazione rapidi, avevo anche bisogno di una rapida ricerca, quindi sono passato a un HashSet o un dizionario.

Prima di tutto, in C ++ le liste concatenate non dovrebbero essere molto più difficili da gestire rispetto a un array. È ansible utilizzare lo std :: list o l’ elenco dei puntatori boost per gli elenchi collegati. I problemi chiave con le liste collegate vs le matrici sono lo spazio extra richiesto per i puntatori e l’accesso casuale terribile. Dovresti usare una lista collegata se tu

  • non hai bisogno dell’accesso casuale ai dati
  • aggiungerai / eliminerai elementi, specialmente nel mezzo della lista

Un argomento ampiamente non apprezzato per ArrayList e contro LinkedList è che le liste di collegamento sono scomode durante il debug . Il tempo speso dagli sviluppatori di manutenzione per comprendere il programma, ad esempio per trovare bug, aumenta e IMHO a volte non giustifica i nanosecondi nei miglioramenti delle prestazioni o nei byte nel consumo di memoria nelle applicazioni aziendali. A volte (beh, ovviamente dipende dal tipo di applicazioni), è meglio sprecare pochi byte ma avere un’applicazione più manutenibile o più facile da capire.

Ad esempio, in un ambiente Java e utilizzando il debugger Eclipse, il debug di un ArrayList rivelerà una struttura molto semplice da comprendere:

 arrayList ArrayList elementData Object[] [0] Object "Foo" [1] Object "Foo" [2] Object "Foo" [3] Object "Foo" [4] Object "Foo" ... 

D’altra parte, guardare i contenuti di una LinkedList e trovare oggetti specifici diventa un incubo di clic Expand-The-Tree, per non parlare del sovraccarico cognitivo necessario per filtrare gli interni di LinkedList:

 linkedList LinkedList header LinkedList$Entry element E next LinkedList$Entry element E "Foo" next LinkedList$Entry element E "Foo" next LinkedList$Entry element E "Foo" next LinkedList$Entry previous LinkedList$Entry ... previous LinkedList$Entry previous LinkedList$Entry previous LinkedList$Entry 

Per me è così,

  1. Accesso

    • Gli elenchi collegati consentono solo l’accesso sequenziale agli elementi. Quindi la complessità algoritmica è l’ordine di O (n)
    • Le matrici consentono l’accesso casuale ai suoi elementi e quindi la complessità è l’ordine di O (1)
  2. Conservazione

    • Gli elenchi collegati richiedono una memoria aggiuntiva per i riferimenti. Ciò li rende poco pratici per elenchi di elementi di dati di piccole dimensioni come caratteri o valori booleani.
    • Gli array non hanno bisogno di una memoria aggiuntiva per puntare al prossimo elemento di dati. È ansible accedere a ciascun elemento tramite indici.
  3. Dimensione

    • La dimensione degli elenchi collegati è dynamic per natura.
    • La dimensione dell’array è limitata alla dichiarazione.
  4. Inserzione / delezione

    • Gli elementi possono essere inseriti e cancellati negli elenchi collegati a tempo indeterminato.
    • L’inserimento / la cancellazione dei valori negli array sono molto costosi. Richiede la riallocazione della memoria.

Due cose:

Codificare una lista collegata è, senza dubbio, un po ‘più di lavoro rispetto all’utilizzo di un array e si chiedeva cosa avrebbe giustificato lo sforzo aggiuntivo.

Non scrivere mai una lista collegata quando usi C ++. Basta usare l’STL. Quanto sia difficile da implementare non dovrebbe mai essere un motivo per scegliere una struttura dati rispetto ad un’altra perché la maggior parte è già implementata là fuori.

Per quanto riguarda le differenze effettive tra un array e un elenco collegato, la cosa importante per me è come pianifichi di utilizzare la struttura. Userò il termine vector poiché è il termine per un array ridimensionabile in C ++.

L’indicizzazione in un elenco collegato è lenta perché devi attraversare l’elenco per raggiungere l’indice dato, mentre un vettore è contiguo in memoria e puoi arrivarci utilizzando la matematica del puntatore.

L’aggiunta alla fine o all’inizio di una lista concatenata è facile, dal momento che devi solo aggiornare un link, dove in un vettore potresti dover ridimensionare e copiare i contenuti.

Rimozione di un elemento da un elenco è facile, dal momento che devi solo rompere un paio di link e quindi collegarli di nuovo insieme. La rimozione di un elemento da un vettore può essere più veloce o più lenta, a seconda se ti interessa dell’ordine. Scambiare l’ultimo elemento in cima alla voce che si desidera rimuovere è più veloce, mentre spostare tutto dopo di esso è più lento ma mantiene l’ordine.

Eric Lippert ha recentemente pubblicato un post su uno dei motivi per cui gli array dovrebbero essere usati in modo conservativo.

Inserimento e rimozione rapidi sono infatti i migliori argomenti per le liste collegate. Se la tua struttura cresce in modo dinamico e non è richiesto l’accesso costante a qualsiasi elemento (come stack e code dinamici), le liste collegate sono una buona scelta.

Ecco una rapida: la rimozione degli articoli è più veloce.

La lista collegata è particolarmente utile quando la collezione è in costante crescita e contrazione. Ad esempio, è difficile immaginare di provare a implementare una coda (aggiungi alla fine, rimuovila dal lato anteriore) usando un array – trascorrerai tutto il tuo tempo spostando le cose verso il basso. D’altra parte, è banale con una lista collegata.

A parte l’aggiunta e la rimozione dal centro dell’elenco, mi piacciono di più gli elenchi collegati perché possono crescere e rimpicciolirsi in modo dinamico.

Nessuno mai più codifica la propria lista collegata. Sarebbe sciocco. La premessa che l’utilizzo di un elenco collegato richiede più codice è semplicemente sbagliato.

In questi giorni, la creazione di un elenco collegato è solo un esercizio per gli studenti in modo che possano comprendere il concetto. Invece, tutti usano un elenco precostruito. In C ++, basato sulla descrizione nella nostra domanda, probabilmente significherebbe un vettore stl ( #include ).

Pertanto, la scelta di una lista collegata rispetto a una matrice è interamente basata sulla valutazione delle diverse caratteristiche di ciascuna struttura in relazione alle esigenze della tua app. Il superamento dell’ulteriore carico di programmazione dovrebbe avere un impatto zero sulla decisione.

È davvero una questione di efficienza, il sovraccarico per inserire, rimuovere o spostare (dove non si sta semplicemente scambiando) elementi all’interno di una lista collegata è minimo, cioè l’operazione stessa è O (1), versi O (n) per una matrice. Questo può fare una differenza significativa se stai operando pesantemente su un elenco di dati. Hai scelto i tuoi tipi di dati in base a come opererai su di essi e scegli il più efficiente per l’algoritmo che stai utilizzando.

Gli array hanno senso dove si conoscerà il numero esatto di articoli e dove la ricerca per indice ha senso. Ad esempio, se volessi memorizzare lo stato esatto del mio output video in un determinato momento senza compressione, probabilmente utilizzerei un array di dimensioni [1024] [768]. Questo mi fornirà esattamente ciò di cui ho bisogno, e una lista sarebbe molto, molto più lenta per ottenere il valore di un dato pixel. Nei luoghi in cui un array non ha senso ci sono generalmente tipi di dati migliori di un elenco per trattare efficacemente i dati.

Array Vs Elenco collegato:

  1. L’allocazione della memoria delle matrici fallirà a volte a causa della memoria frammentata.
  2. La memorizzazione nella cache è migliore negli array poiché tutti gli elementi sono allocati nello spazio di memoria contiguo.
  3. La codifica è più complessa degli array.
  4. Nessun limite di dimensione sull’Elenco collegato, a differenza degli array
  5. Inserimento / Cancellazione è più veloce nella lista collegata e l’accesso è più veloce negli array.
  6. Elenco collegato meglio dal punto di vista multi-threading.

Poiché le matrici sono di natura statica, quindi tutte le operazioni come l’allocazione della memoria si verificano solo al momento della compilazione. Quindi il processore deve mettere meno sforzo al suo runtime.

Supponiamo che tu abbia un set ordinato, che vuoi anche modificare aggiungendo e rimuovendo elementi. Inoltre, è necessario saper conservare un riferimento a un elemento in modo tale da poter ottenere in seguito un elemento precedente o successivo. Ad esempio, un elenco di cose da fare o un insieme di paragrafi in un libro.

Innanzitutto dovremmo notare che se si desidera conservare riferimenti ad oggetti esterni al set stesso, è probabile che si finisca con l’archiviare i puntatori nell’array, anziché memorizzare gli oggetti stessi. Altrimenti non sarà ansible inserire nell’array: se gli oggetti sono incorporati nell’array, si sposteranno durante gli inserimenti e tutti i puntatori a essi non saranno più validi. Lo stesso vale per gli indici di array.

Il tuo primo problema, come hai notato tu stesso, è l’inserimento – l’elenco collegato consente l’inserimento in O (1), ma un array generalmente richiede O (n). Questo problema può essere parzialmente superato – è ansible creare una struttura di dati che fornisce un’interfaccia di accesso ordinale simile a una matrice in cui sia la lettura che la scrittura sono, nella peggiore delle ipotesi, logaritmiche.

Il tuo secondo, e più grave problema, è che dato un elemento che trova il prossimo elemento è O (n). Se il set non è stato modificato, è ansible mantenere l’indice dell’elemento come riferimento anziché il puntatore, rendendo quindi find-next un’operazione O (1), ma poiché è tutto ciò che si ha è un puntatore all’object stesso e in nessun modo per determinare il suo indice corrente nell’array diverso dalla scansione dell’intero “array”. Questo è un problema insormontabile per gli array, anche se è ansible ottimizzare gli inserimenti, non c’è nulla che tu possa fare per ottimizzare l’operazione di tipo find-next.

In un array hai il privilegio di accedere a qualsiasi elemento nel tempo O (1). Quindi è adatto per operazioni come la ricerca binaria Ordinamento rapido, ecc. La lista collegata, d’altra parte, è adatta per la cancellazione di inserzioni come è in O (1). Entrambi hanno vantaggi e svantaggi e preferire uno rispetto all’altro si riduce a ciò che si desidera implementare.

– La più grande domanda è che possiamo avere un ibrido di entrambi. Qualcosa di simile a ciò che Python e Perl implementano come elenchi.

Lista collegata

È più preferibile quando si parla di inserimento! Fondamentalmente ciò che fa è che si tratta del puntatore

1 -> 3 -> 4

Inserisci (2)

1 …….. 3 …… 4
….. 2

Finalmente

1 -> 2 -> 3 -> 4

Una freccia dai 2 punti in 3 e la freccia di 1 punti in 2

Semplice!

Ma da matrice

| 1 | 3 | 4 |

Inserisci (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

Bene chiunque può visualizzare la differenza! Solo per 4 indici stiamo facendo 3 passi

Cosa succede se la lunghezza dell’array è di un milione? La matrice è efficiente? La risposta è no! 🙂

La stessa cosa vale per la cancellazione! Nella lista collegata possiamo semplicemente usare il puntatore e annullare l’elemento e successivamente nella class dell’object! Ma per array, dobbiamo eseguire shiftLeft ()

Spero possa aiutare! 🙂

L’elenco collegato è più di un sovraccarico da mantenere rispetto alla matrice, richiede inoltre una memoria aggiuntiva per la memorizzazione di tutti questi punti. Ma ci sono alcune cose che non possono fare. In molti casi, supponiamo di volere una matrice di lunghezza 10 ^ 9, ma non è ansible ottenerla perché deve trovarsi una posizione di memoria continua. La lista collegata potrebbe essere un salvatore qui.

Supponiamo di voler memorizzare più cose con i dati, quindi possono essere facilmente estesi nella lista collegata.

I contenitori STL di solito hanno l’implementazione della lista collegata dietro la scena.

Differenza tra ArrayList e LinkedList

ArrayList e LinkedList implementano entrambe l’interfaccia List e mantengono l’ordine di inserimento. Entrambe sono classi non sincronizzate. Ma ci sono molte differenze tra le classi ArrayList e LinkedList fornite di seguito.

Lista di array –

  1. ArrayList utilizza internamente una matrice dynamic per memorizzare gli elementi .

  2. La manipolazione con ArrayList è lenta perché utilizza internamente array. Se qualche elemento viene rimosso dall’array, tutti i bit vengono spostati in memoria.

  3. ArrayList class ArrayList può fungere da elenco solo perché implementa solo la List .
  4. ArrayList è migliore per l’archiviazione e l’accesso ai dati.

Lista collegata –

  1. LinkedList utilizza internamente una lista doppiamente collegata per memorizzare gli elementi .

  2. La manipolazione con LinkedList è più veloce di ArrayList perché utilizza una lista doppiamente collegata, quindi non è necessario alcun cambio di bit in memoria.

  3. LinkedList class LinkedList può fungere da elenco e da accodare sia perché implementa le interfacce List e Deque.

  4. LinkedList è migliore per la manipolazione dei dati.

L’unico motivo per usare la lista collegata è che inserire l’elemento è facile (rimuovendo anche).

Disadvatige potrebbe essere che i puntatori occupano molto spazio.

E a proposito di questa codifica è più difficile: di solito non hai bisogno della lista collegata al codice (o solo una volta) sono inclusi in AWL e non è così complicato se devi ancora farlo.

penso anche che la lista dei collegamenti sia migliore degli array. perché facciamo il traversamento nella lista dei collegamenti ma non negli array

A seconda della lingua, alcuni di questi svantaggi e vantaggi potrebbero essere considerati:

Linguaggio di programmazione C : quando si utilizza una lista concatenata (tipicamente attraverso i puntatori di struttura), è necessario prestare particolare attenzione a non perdere memoria. Come accennato in precedenza, le liste concatenate sono facili da mescolare, perché tutti stavano facendo sta cambiando i puntatori, ma ci ricorderemo di liberare tutto?

Java : Java ha un garbage collector automatico, quindi la perdita di memoria non sarà un problema, ma nascosto dal programmatore di alto livello sono i dettagli di implementazione di cosa sia una lista collegata. Metodi come la rimozione di un nodo dal centro della lista sono più complicati di una procedura di quanto alcuni utenti del linguaggio si aspettino che sia.

Perché una lista collegata su un array? Bene come alcuni hanno già detto, maggiore velocità di inserzioni e cancellazioni.

Ma forse non dobbiamo vivere con i limiti di entrambi, e ottenere il meglio da entrambi, allo stesso tempo … eh?

Per le eliminazioni di array, è ansible utilizzare un byte ‘Deleted’, per rappresentare il fatto che una riga è stata cancellata, quindi riorganizzare la matrice non è più necessaria. Per alleviare l’onere degli inserimenti o modificare rapidamente i dati, utilizzare un elenco collegato. Quindi, quando ti riferisci a loro, cerca prima la logica, poi l’altra. Quindi, usarli in combinazione ti dà il meglio di entrambi.

Se si dispone di un array molto grande, è ansible combinarlo con un altro array molto più piccolo o elenco collegato dove il più piccolo contiene 20, 50, 100 elementi utilizzati più di recente. Se quello necessario non è nella lista o nell’array linkato più brevi, si passa all’array di grandi dimensioni. Se si trova lì, è ansible aggiungerlo alla lista / matrice collegata più piccola presumendo che “le cose usate più di recente siano più facili da riutilizzare” (e sì, probabilmente facendo scontrare l’elemento utilizzato meno di recente dalla lista). Il che è vero in molti casi e ha risolto un problema che ho dovuto affrontare in un modulo di controllo delle autorizzazioni di sicurezza .ASP, con facilità, eleganza e velocità impressionante.

Mentre molti di voi hanno toccato l’argomento principale della lista collegata vs array, la maggior parte dei confronti è il modo in cui uno è migliore / peggiore dell’altro.Eg. puoi fare un accesso casuale alla matrice ma non ansible nella lista collegata e in altri. Tuttavia, questo presuppone che elenchi di collegamenti e array vengano applicati in un’applicazione simile. Tuttavia, una risposta corretta dovrebbe essere come la lista di collegamenti sarebbe preferibile su array e viceversa in una particolare distribuzione dell’applicazione. Supponiamo che vogliate implementare un’applicazione dizionario, cosa usereste? Array: mmm consentirebbe un facile recupero tramite ricerca binaria e altre ricerche .. ma pensiamo a come la lista dei collegamenti può essere migliore … Vuoi cercare “Blob” nel dizionario. Avrebbe senso avere una lista di collegamenti di A-> B-> C-> D —-> Z e poi ogni elemento di lista che punta anche a una matrice o un’altra lista di tutte le parole che iniziano con quella lettera ..

 A -> B -> C -> ...Z | | | | | [Cat, Cave] | [Banana, Blob] [Adam, Apple] 

Ora l’approccio sopra è migliore o una serie piatta di [Adamo, Mela, Banana, Blob, Gatto, Caverna]? Sarebbe ansible anche con array? Quindi un importante vantaggio della lista di collegamenti è che si può avere un elemento non solo puntando all’elemento successivo ma anche ad un altro elenco di collegamenti / array / heap / o qualsiasi altra posizione di memoria. La matrice è una memoria contigua piatta suddivisa in blocchi di dimensioni dell’elemento che verrà memorizzato. L’elenco dei collegamenti invece è costituito da blocchi di unità di memoria non contigue (può essere di qualsiasi dimensione e può contenere qualsiasi cosa) e punta a ciascuna di esse altro come vuoi tu. Allo stesso modo, diciamo che stai realizzando un’unità USB. Ora desideri che i file vengano salvati come qualsiasi array o elenco di link? Penso che tu abbia l’idea di cosa sto indicando 🙂