> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

# ArrayList y lista enlazada en Java: cómo funcionan y cuánto cuesta cada operación

> ArrayList frente a lista enlazada en Java paso a paso: array contiguo con capacidad y redimensionado, nodos enlazados, coste de get, add y remove, coste amortizado y cuándo usar cada una.

<Card title="Abrir el simulador" icon="flask" href="https://simulab.es/programacion/listas">
  Las dos listas en Java paso a paso: capacidad, desplazamientos, recorrido de nodos y coste.
</Card>

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)$**.
* `add(e)` al final: si cabe, escribe en `datos[size]`. **$O(1)$**.
* `add(i, e)` o `remove(i)` en medio: hay que **desplazar** todos los elementos de detrás. **$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 $n$ inserciones al final, el total de copias es menor que $2n$: **$O(1)$ amortizado** por inserción, aunque alguna concreta cueste $O(n)$.

### Lista enlazada

Cada elemento va en un **nodo** con una referencia al siguiente:

```java theme={null}
class Nodo<E> { E dato; Nodo<E> sig; }
```

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

### Comparativa

| Operación | ArrayList | Lista enlazada |
| - | - | - |
| get(i) | $O(1)$ | $O(n)$ |
| add al final | $O(1)$ amortizado | $O(1)$ con referencia al último |
| add/remove al principio | $O(n)$ | $O(1)$ |
| add/remove en medio | $O(n)$ (desplazar) | $O(n)$ (llegar) |
| Memoria | Compacta, con huecos libres | Un nodo y una referencia por elemento |

## Ejemplos resueltos

<AccordionGroup>
  <Accordion title="Ejemplo 1 · add(1, 15) en una ArrayList llena" defaultOpen>
    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.
  </Accordion>

  <Accordion title="Ejemplo 2 · Copias por duplicar">
    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 = 15$ copias en total, menos que $2 \cdot 16$.
  </Accordion>

  <Accordion title="Ejemplo 3 · get en la enlazada">
    `get(3)` en una lista de 5 nodos: 3 saltos desde el primero. En la ArrayList, un acceso directo.
  </Accordion>
</AccordionGroup>

## Experimenta con el simulador

<Steps>
  <Step title="Redimensionar">
    Con capacidad inicial 1, haz varios add al final y cuenta las copias en cada uno.
  </Step>

  <Step title="Al principio">
    Haz varios `add(0, x)` en las dos listas y compara el coste total.
  </Step>

  <Step title="Acceso por índice">
    Haz `get` de la última posición en las dos. ¿Cuál cuesta más?
  </Step>
</Steps>

## Errores frecuentes

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

## Herramientas relacionadas

<CardGroup cols={3}>
  <Card title="Tablas hash" icon="hashtag" href="/programacion/java/tablas-hash">
    Búsqueda en O(1) de media.
  </Card>

  <Card title="Estructuras de datos" icon="layer-group" href="/programacion/algoritmos/estructuras-datos">
    Pila, cola y árbol.
  </Card>

  <Card title="Memoria y punteros en C" icon="memory" href="/programacion/c/punteros">
    Nodos enlazados en C.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.