Skip to main content

Abrir el simulador

Las dos listas en Java paso a paso: capacidad, desplazamientos, recorrido de nodos y coste.
En Java, ArrayList y LinkedList implementan la misma interfaz List: tienen las mismas operaciones y dan los mismos resultados. Pero por dentro son completamente distintas, y eso hace que unas operaciones sean instantáneas en una y lentas en la otra. Hacer el mismo historial con las dos es la mejor forma de verlo.

​
Lo que vas a aprender

  • Cómo se guarda una ArrayList: array, capacidad y tamaño.
  • Qué pasa al llenarse: el redimensionado.
  • Cómo se guarda una lista enlazada: nodos y referencias.
  • El coste de get, add y remove en cada una.
  • Qué es el coste amortizado.

​
Cómo se usa el simulador

  • Elige ArrayList o Lista enlazada.
  • Escribe un valor y un índice y lanza operaciones: add(valor), add(índice, valor), get(índice), remove(índice) o Vaciar.
  • Elige la capacidad inicial de la ArrayList (1 – 8).
  • Avanza la animación paso a paso con ⏮, ◀, ↺ Repetir, ▶ y ⏭, mientras se resalta la línea del código Java.
  • El panel cuenta las copias (ArrayList) o los saltos entre nodos (enlazada) de cada operación y de todo el historial, y compara con la otra estructura.

​
Fundamentos teóricos

​
ArrayList

Guarda los elementos en un array contiguo E[] datos con un contador size:
  • get(i): calcula la posición y lee. O(1)O(1).
  • add(e) al final: si cabe, escribe en datos[size]. O(1)O(1).
  • add(i, e) o remove(i) en medio: hay que desplazar todos los elementos de detrás. O(n)O(n).
  • Si se llena, crea un array del doble de capacidad y copia todos los elementos.

​
Coste amortizado

Duplicar la capacidad hace que las copias sean cada vez más raras. Con nn inserciones al final, el total de copias es menor que 2n2n: O(1)O(1) amortizado por inserción, aunque alguna concreta cueste O(n)O(n).

​
Lista enlazada

Cada elemento va en un nodo con una referencia al siguiente:
  • get(i): hay que recorrer ii nodos desde el primero. O(n)O(n).
  • add(0, e) o remove(0): cambiar un par de enlaces. O(1)O(1).
  • add(e) al final: O(1)O(1) si se guarda una referencia al último nodo.
  • Insertar en medio: llegar a la posición es O(n)O(n), aunque el cambio de enlaces sea O(1)O(1).

​
Comparativa

​
Ejemplos resueltos

Ejemplo 1 · add(1, 15) en una ArrayList llena

Capacidad 4 con {10, 20, 30, 40}.
  1. No cabe: se crea un array de capacidad 8 y se copian 4 elementos.
  2. Se desplazan 40, 30 y 20 una posición: 3 copias.
  3. datos[1] = 15, size = 5.
Resultado: {10, 15, 20, 30, 40}. En una lista enlazada bastaría llegar al nodo 0 y cambiar dos enlaces.
Partiendo de capacidad 1 e insertando 16 elementos al final, se redimensiona al insertar el 2.º, el 3.º, el 5.º y el 9.º elemento, con 1+2+4+8=151 + 2 + 4 + 8 = 15 copias en total, menos que 2⋅162 \cdot 16.
get(3) en una lista de 5 nodos: 3 saltos desde el primero. En la ArrayList, un acceso directo.

​
Experimenta con el simulador

1

Redimensionar

Con capacidad inicial 1, haz varios add al final y cuenta las copias en cada uno.
2

Al principio

Haz varios add(0, x) en las dos listas y compara el coste total.
3

Acceso por índice

Haz get de la última posición en las dos. ¿Cuál cuesta más?

​
Errores frecuentes

  • Pensar que la lista enlazada es siempre más rápida para insertar: llegar a la posición cuesta O(n)O(n).
  • Confundir capacidad y tamaño de una ArrayList.
  • Recorrer una LinkedList con get(i) en un bucle: O(n2)O(n^2). Hay que usar un iterador.

​
Herramientas relacionadas

Tablas hash

Búsqueda en O(1) de media.

Estructuras de datos

Pila, cola y árbol.

Memoria y punteros en C

Nodos enlazados en C.
Última modificación el 6 de octubre de 2026