arrays - singly - Array contro elenco collegato




singly linked list implementation (20)

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 classe Java mentre questa domanda riguarda le strutture di dati generali.


È 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.


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.


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.

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 post un post su uno dei motivi per cui gli array dovrebbero essere usati in modo conservativo.


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.


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.


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.


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 STL e non è così complicato se devi ancora farlo.


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.


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 classe dell'oggetto! Ma per array, dobbiamo eseguire shiftLeft ()

Spero possa aiutare! :)


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 possibile 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 possibile 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 :)


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 <vector> ).

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.


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. È possibile accedere a ciascun elemento tramite indici.
  3. Dimensione

    • La dimensione degli elenchi collegati è dinamica 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.

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.


Prima di tutto, in C ++ le liste concatenate non dovrebbero essere molto più difficili da gestire rispetto a un array. È possibile 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<String>
  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<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

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, è possibile 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.


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


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 dinamica 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 classe 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 classe LinkedList può fungere da elenco e da accodare sia perché implementa le interfacce List e Deque.

  4. LinkedList è migliore per la manipolazione dei dati.





linked-list