Per quanto ne so, il concetto di una lista concatenata è un insieme di oggetti collegati tra loro avendo un attributo "successivo" e talvolta "precedente" per attraversare gli oggetti.In che modo LinkedList funziona internamente in Java?
ho notato in Java, è possibile creare un oggetto LinkedList ... ma trattarlo come un array/lista/sequenza utilizzando gli stessi metodi, come .add(), .get(), ecc
Quindi, LinkedList è internamente una sequenza di tipo array?
Quindi, LinkedList è internamente una sequenza di tipo array?
No. E 'una serie di istanze di una classe annidata privato Entry, che ha next, previous e element riferimenti. Nota che potresti averlo scoperto da solo guardando il codice sorgente, che viene fornito con JDK.
Il motivo per cui questa struttura interna non è esposta è che impedisce che la struttura si corrompa e ad es. contenente un ciclo. E l'accesso uniforme tramite le interfacce List e Deque consente l'utilizzo polimorfico.
+1: L'elenco che è internamente una sequenza di tipo array è chiamato ArrayList. ;) –
-1: Dipende dalla tua abilità di programmazione, immagino. Dall'articolo di Wikipedia su Linked List: "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." - FYI, i pool di memoria sono gli array che i professionisti utilizzano per memorizzare internamente elenchi collegati. Sono anche noti come allocatori di slab. –
@Anthony: vendetta downvote, eh? Farsene una ragione. Professionisti qualificati non entrano in Internet a causa del livello su cui una domanda dovrebbe essere risolta. –
È possibile implementare un oggetto che funziona come un array, utilizzando un elenco collegato. Rispetto agli array, alcune operazioni saranno più veloci e alcune saranno più lente. Ad esempio, chiamare get() per un elemento vicino alla fine potrebbe essere molto più lento con un elenco collegato che con un array. Ma è ancora possibile.
D'altra parte, l'eliminazione di un elemento dal centro di un elenco collegato sarà più veloce dell'operazione corrispondente eseguita utilizzando gli array.
LinkedList è una catena di entità in cui ogni entità conosce il prossimo, , quindi l'operazione (indice) richiede l'iterazione su questa catena con contatore. Ma questa lista ottimizzata per l'aggiunta e l'eliminazione per posizione (nel caso in cui ho bisogno di mettere l'elemento all'interno dell'elenco o eliminare l'elemento dall'elenco dei collegamenti intermedi è meglio)
Non proprio. L'elenco collegato è fornito dalla raccolta e con una buona progettazione è possibile creare una doppia lista concatenata. Ora non è come una matrice perché questi oggetti non hanno indici e non sono elementi all'interno del contenitore, ad esempio la lista. Quindi definisci il prossimo e il precedente e stabilisci quale sarà la prossima mossa. Hanno tutti gli stessi metodi perché di nuovo sono raccolte come ho detto.
Internamente utilizzerà quello che viene chiamato un "allocatore di slab" - questo è fondamentalmente un elenco collegato di piccoli array. Ogni volta che aggiungi un oggetto, controlla se c'è spazio nella lastra e, in caso affermativo, mette lì l'oggetto. Altrimenti, assegna una nuova lastra e pone l'oggetto nel primo elemento della lastra.
Questa tecnica riduce al minimo le spese generali di allocazione della memoria - se si aggiunge un sacco di elementi da una lista collegata, che sarebbe un sacco di piccole allocazioni di memoria che prendono un sacco di tempo, e le allocators lastra minimizzare che
Questo è semplicemente sbagliato. Java non è C++. Piccole allocazioni sono veloci. Di conseguenza, l'implementazione dell'API non utilizza trucchi per evitarlo. –
@MichaelBorgwardt Dove pensi che la JVM abbia la memoria per ogni oggetto che assegna? Pensi che la JVM stia chiamando malloc() ogni volta? I garbage collector lavorano con la memoria in lastre. Per favore spiega come pensi che Java stia allocando memoria per liste collegate senza lastre di memoria. –
@MichaelBorgwardt Dalla documentazione sulla JVM di IBM: "Queste sezioni sono in genere implementate come contigui blocchi di memoria nativa che sono sotto il controllo del gestore della memoria Java (che include il garbage collector)." –
come noto elenco collegato è come quello che hai detto nel primo paragrafo. ogni oggetto ha due riferimenti, chiamati precedenti e successivi. a differenza di un array che funziona in sequenza (in C è memorizzato esattamente in sequenza. Penso che java faccia solo lo stesso, ecco perché non possiamo ridimensionare un array), elenca i lavori facendo riferimento. quindi logicamente funziona più lentamente di quanto faccia l'array.
Un LinkedList in Java funziona esattamente come ci si aspetterebbe che faccia. Se si utilizzano le Collezioni ufficiali LinkedList, sarà effettivamente un un gruppo di oggetti connessi tra loro avendo un 'successivo' e talvolta 'precedente'.
E sì, ha un metodo get(int index) che è sorprendente, perché non sarebbe molto efficiente come si avrebbe bisogno di cominciare dall'inizio e contare il vostro senso l'elenco per trovare l'esimo ingresso index e questo non è quello che LinkedLists è sono bravi a Il motivo è che esiste perché LinkedList implementa l'interfaccia List. Questo è qualcosa che puoi con TUTTE le liste.
Tuttavia, probabilmente si cercherà di evitare l'utilizzo di LinkedList quando la maggior parte del proprio accesso ad esso avviene tramite il metodo get(int index) in quanto sarebbe chiaramente il più inefficiente. Forse sarebbe meglio usare uno ArrayList.
Se si desidera vedere l'implementazione, cercare il codice sorgente di 'java.util.LinkedList' che si può trovare nel file' src.zip' nella directory di installazione JDK. – Jesper
Oppure guarda la fonte: http://www.docjar.com/html/api/java/util/LinkedList.java.html –
Potresti essere interessato al mio [Vita interna di LinkedList in java] (http: // tutorial. volodial.blogspot.com/2013/05/internal-life-of-linkedlist-in-java.html). –