Conferma Java ListaLinkata "foreach" loop

Question

Good Day,

Qualcuno può confermare quanto è stato detto in fondo a questo post java - iterating a linked list Il post afferma che è possibile utilizzare il per (char c: linkedlistofchars) sintassi e sarà ancora O (n). Penserei l'accesso a un elenco che assomiglia a questo ...

a b c d e f 

sarebbe effettivamente funzionare iniziare al beggining della lista collegata ad ogni iterazione del ciclo for, come questo ...

a ab abc abcde abcdef 

causando il tempo di accesso non deve essere O (n).

Come funziona esattamente? Ha senso con un array e con gli operatori dell'array, ma come fa la sintassi java a sapere come iterare attraverso un elenco collegato usando il ciclo foreach in java?

Pensavo che la struttura di dati LinkedList fosse solo una libreria aggiuntiva e non parte della sintassi del linguaggio principale. (Mi rendo conto che la classe LinkedList è standard in java)

Spero ho spiegato la mia preoccupazione in modo sufficientemente chiaro .... Grazie

Answer 1

Prima di tutto, qualsiasi istanza di classe che implementa Iterable può essere utilizzata in un ciclo foreach. Il motivo è che dopo la compilazione, for (Suit suit : suits) diventa effettivamente for (Iterator i = suits.iterator(); i.hasNext();). Vedi this explanation per maggiori dettagli.

E le raccolte implementano iteratori ottimizzati, specifici per la struttura dei dati. In particolare su LinkedList, l'iteratore mantiene un puntatore all'ultimo oggetto restituito per consentire il tempo costante next() e le operazioni previous(). Pertanto, l'iterazione su una lista collegata usando il ciclo foreach sarà una complessità di tempo O (n). Puoi guardare il codice sorgente per maggiori dettagli.

Answer 2

L'esempio di codice a questo link demonstrates the difference. L'OP a quel collegamento è errato: chiamare list.get(i) inizierà all'inizio della lista ogni volta e quindi conterebbe fino al raggiungimento di i, mentre un iterator.next() salverà il tuo posto nell'elenco, quindi ogni volta che viene chiamato, deve solo leggere il valore successivo, non tutti i valori compresi tra 0 e n.