Confirmar LinkedList de Java "foreach" bucle

Question

buen día,

Puede alguien confirmar lo que se dijo en la parte inferior de este post java - iterating a linked list El mensaje menciona que se puede utilizar el para (char c: linkedlistofchars) sintaxis y todavía será O (n). Me gustaría pensar acceder a una lista que tiene este aspecto ...

a b c d e f 

sería ejecutar realmente empezar por el beggining de la lista enlazada durante cada iteración del bucle, así ...

a ab abc abcde abcdef 

haciendo que el tiempo de acceso no sea O (n).

¿Cómo funciona exactamente eso? Tiene sentido con una matriz y los operadores de la matriz, pero ¿cómo sabe la sintaxis de Java cómo iterar a través de una lista vinculada utilizando el foreach bucle en java?

Pensé que la estructura de datos LinkedList era solo una biblioteca adicional y no parte de la sintaxis del lenguaje central. (Me doy cuenta de que la clase LinkedList es estándar en Java)

Espero haberme explicado con suficiente claridad mi preocupación .... Gracias

Answer 1

En primer lugar, cualquier instancia de la clase que implemente Iterable se puede utilizar en un bucle foreach. La razón es que después de la compilación, for (Suit suit : suits) se convierte realmente en for (Iterator i = suits.iterator(); i.hasNext();). Ver this explanation para más detalles.

Y las colecciones implementan iteradores optimizados, específicos para la estructura de datos. Específicamente para LinkedList, el iterador mantiene un puntero al último objeto devuelto para permitir operaciones de tiempo constante next() y previous(). Por lo tanto, al iterar sobre una lista enlazada usando foreach-loop se obtendrá la complejidad del tiempo O (n). Puede ver el código fuente para más detalles.

Answer 2

El ejemplo de código en este enlace demonstrates the difference. El OP en ese enlace es incorrecto: la llamada al list.get(i) comenzará al principio de la lista cada vez y luego contará hasta que se alcance i, mientras que iterator.next() guardará su lugar en la lista, por lo que cada vez que se llame solo necesita leer el siguiente valor, no todos los valores entre 0 y n.