¿Qué es una lista enlazada simple y cuándo la usarías?

Question

Accepted Answer

Una **lista enlazada simple** es una cadena de **nodos**, donde cada nodo contiene un valor y un puntero al **siguiente** nodo. A diferencia de un array, los nodos no son contiguos — pueden estar en cualquier lugar de la memoria, conectados mediante referencias.

## Estructura

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## Ejemplo

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Insert at head -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # point new node at old head
    return node          # new head

# Search -> O(n): must walk the chain
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## Complejidad

| Operación | Tiempo |
|---|---|
| Insertar/eliminar en la cabeza | O(1) |
| Acceso por índice | O(n) |
| Búsqueda | O(n) |

## Compensaciones

- **Fortalezas:** inserción/eliminación O(1) al frente; crecimiento sin reasignación; sin capacidad desperdiciada.
- **Debilidades:** sin acceso aleatorio; cada nodo tiene carga de puntero; mala localidad de caché (memoria dispersa).

## Por qué es importante

Las listas enlazadas brillan cuando frecuentemente añades o eliminas en los extremos y rara vez indexas en el medio — por ejemplo, como la columna vertebral de pilas, colas y listas de adyacencia.

Entender la manipulación de punteros aquí es fundamental para árboles, grafos y muchos problemas de entrevista.

Operación	Tiempo
Insertar/eliminar en la cabeza	O(1)
Acceso por índice	O(n)
Búsqueda	O(n)