ArrayList y lista enlazada
Haz las mismas operaciones con las dos listas y compara: la ArrayList desplaza elementos, la enlazada recorre nodos.
1// ArrayList: E[] datos; int size2public E get(int index) {3 if (index < 0 || index >= size)4 throw new IndexOutOfBoundsException();5 return datos[index]; // acceso directo: O(1)6}datos[3] = 40. Se calcula la dirección y se lee: da igual el índice.
Con la otra estructura, el mismo historial cuesta 10 saltos entre nodos.
| Operación | ArrayList | Enlazada |
|---|---|---|
| get(i) | O(1) | O(i) |
| add(e) al final | O(1) amortizado | O(1) con ultimo |
| add(0, e) | O(n) | O(1) |
| add(i, e) | O(n − i) | O(i) |
| remove(i) | O(n − i) | O(i) |
Una ArrayList guarda los elementos en un array contiguo: se accede a cualquier posición en O(1), pero insertar o borrar en medio obliga a desplazar todos los que van detrás. Cuando el array se llena, se crea otro del doble de capacidad y se copian los elementos.
Una lista enlazada simple guarda cada elemento en un nodo que apunta al siguiente. Insertar o borrar es cambiar un par de enlaces, pero para llegar a la posición i hay que recorrer i nodos desde el primero. Guardar también el último nodo hace que añadir al final sea O(1).
Haz el mismo historial de operaciones con las dos estructuras y compara el coste: la ArrayList cuenta copias de elementos y la enlazada, saltos entre nodos.
Una ArrayList de capacidad 4 tiene {10, 20, 30, 40}. ¿Qué pasa al hacer add(1, 15)?
- size + 1 = 5 > 4: no cabe. Se crea un array de capacidad 8 y se copian los 4 elementos.
- Se abre hueco en la posición 1 desplazando a la derecha 40, 30 y 20: 3 copias.
- datos[1] = 15 y size pasa a 5.
- En una lista enlazada bastaría con llegar al nodo 0 y cambiar dos enlaces.
{10, 15, 20, 30, 40}, con capacidad 8
Preguntas frecuentes
¿Por qué add al final de una ArrayList es O(1) si a veces hay que copiar todo?
Porque al doblar la capacidad las copias son cada vez más raras. Repartidas entre todas las inserciones salen a un número constante de copias por operación: es O(1) amortizado.
¿Cuándo es mejor una lista enlazada?
Cuando se inserta y se borra mucho al principio o en posiciones a las que ya se ha llegado con un iterador. Si se accede mucho por índice, la ArrayList es mucho más rápida.
¿Para qué sirve guardar el último nodo?
Para añadir al final sin recorrer la lista: ultimo.sig = nuevo. Sin ese puntero, add(e) sería O(n).
¿Por qué se pone a null la última casilla al borrar en la ArrayList?
Porque si no, el array seguiría apuntando al objeto aunque ya no forme parte de la lista, y el recolector de basura no podría liberarlo.