Muchas veces recorremos un array (por ejemplo arr[3] {2,3,1}) con el siguiente bucle

for (int i=0; i<3; i ++) {
  arr[i] ... // procesamiento del elemento
}

Esta es la forma correcta de acceder a los elementos de un array (acceso por indice), ya que en un array los elementos están guardados de forma continua en la memoria:

nuestro array ‘arr’ tiene 3 elementos los cuales son {2,3,1}, nuestra variable ‘arr’ guarda la posicion de el primer elemento de nuestro array, es decir guarda la posicion de 2 en nuestro ejemplo y nada más, luego para acceder a cada valor del array realiza una operación matemática para obtener la ubicación de memoria del elemento deseado:

cuando yo llamo arr[2], esto debería retornar 1, y la forma en que lo hace es la siguiente:

Sabemos que nuestra matriz es de elementos int y que cada int ocupa 4 bytes (en general) en memoria, nuestro primer elemento es un 2 que es un int por lo que ocupa 4 bytes, el segundo elemento (el 3) ocupa los 4 bytes siguientes y asi …
Dijimos que ‘arr’ guarda la posicion del primer elemento, más especificamente guarda la posicion de memoria del primer byte de este elemento. Resumamos:

• nuestra array ‘arr’ guarda valores int de 4 bytes c/u
• nuestro array ‘arr’ guarda la posicion de memoria donde se encuentra el primer byte del primer elemento de nuestro array (el 2), que digamos es una posición que simbolizamos por ‘f’.
• nuestro array ‘arr’ no sabe nada más. ¿ como accede a los demas elementos? veamos:

Cuando queremos llamar al elemento por el indice 2, se hace lo siguietne:

*(f + 2*sizeof(int))

obs: sizeof(int) es 4

lo que hace el compilador es que a partir del primer byte si se quiere dirigir al tercer elemento (indice 2) lo que hace es a la primera posicion del array se suma 2 veces el tamaño de un elemento int, es decir salta de la primera posicion a la posicion donde debería estar el elemento que deseamos. Esto calculo de posiciones de memoria ocurre dentro del compilador para obtener el elemento deseado en un array.

Esto hace que cuando llamamos a arr[2], como por arte de magia obtengamos el valor int 3, esto (dado que la multiplicacion se puede considerar elemental, o de tiempo acotado por una constante, para números no muy grandes) esto nos da una velocidad de O(1) para obtener cualquier elemento que deseamos en un array.

Esto es posible en array porque como dijimos sus elementos se almacenan en ubicaciones CONTIGUAS de memoria, si esto no fuera así no podriamos acceder tan facilmente al elemento que deseamos.

Con las listas todo esto es diferente, ya que las listas no tienen sus elementos en la memoria de foma continua sino que estan en ubicaciones aleatorias de memoria las cuales estan unidas unas a otras por punteros. Arr fuera una lista como una lista enlazada o doblemente enlazada etc, para acceder a arr[2] tenemos que saber que arr contiene el primer nodo o elemento de nuestra lista, para ir al segundo debo dirigirme al elemento puntero al siguiente elemento y asi luego al tercero que es el elemento que quiero, si luego quiero acceder al elemento arr[1] tendria otra vez desde el primer nodo o elemento dirigirme al nodo siguiente el cual seria el segundo elemento y el que deseamos.

La complejidad de acceso por indice en una lista es lineal O(n) mientras que en un array es constante O(1), esto es simplemente por que en una lista no puedes ‘saltar’ directamente con una operacion matematica a la posicion de elemento deseado sino que tienes que de forma obligatoria recorrer comenzando del primer nodo y dirigirte al nodo siguiente n-1 veces si quieres el elemento de indice n.

¿Que pasa si queremos recorrer una lista? Si interamos hacerlo de la forma en como recorrimos un array:

for (int i=0; i<3; i ++) {
  arr[i] ... // procesamiento del elemento
}

El resultado es un recorrido MUY ineficiente que quiza para una lista de 3 elementos no se nota pero mientras más elementos tenga la lista más lenta se vuelve el algorimo, si nos fijamos en la complejidad en tiempo de este algoritmo seria: O((n-1)*(n)/2) = O (n^2)

OBS: La complejidad para recorrer con el algoritmo anterior para un Array seria O(1 * n) = O(n) es decir lineal

Una complidad cuadratica (LENTA) para recorrer una lista, hay una forma de mejorar esto, que es el titulo de este post, los ITERADORES.

Con un iterador el recorrido de la lista puede ser tan eficiente como el recorride en un array. Basicamente funciona asi:

SIN ITERADOR

Para recorrer una lista obtenemos el primer elemento de forma sencilla
Luego:
Obtener el segundo: obtenemos el primero y nos dirigimos a su puntero siguiente
Obtener el tercero: obtenemos el primero y nos dirigimos a su puntero siguiente y luego nos dirigimos a su puntero siguiente (del 2do elemento)

CON ITERADOR

Creamos un variable puntero: «ptr_actual» y la inicializamos con la posicion de memoria donde esta el primer elemento.
Para recorrer una lista obtenemos el primer elemento de forma sencilla con ptr_actual
Luego:

Obtener el segundo:
1° obtenemos ptr_actual y nos dirigimos a su puntero siguiente
2° actualizamos el valor de ptr_actual con la posicion de memoria del segundo valor.

Obtener el tercero:
1° obtenemos ptr_actual y nos dirigimos a su puntero siguiente
2° actualizamos el valor de ptr_actual con la posicion de memoria del segundo valor.

Este recorrido en una lista por iterador también se conoce como los ciclos FOR EACH y aumentan la eficiencia de O(n^2) a O(n) para recorrer una lista. En un post posterior se verá la implementan de iteradores tanto en Java como C++