Listas enlazadas: simples y dobles
Elementos dispersos, conectados por punteros.
La apuesta contraria a la del array.
El intercambio
- Sin aritmética de direcciones → el acceso por índice es O(n)
- Insertar / borrar en un nodo que ya tienes → O(1), nada se mueve
- Insertar al frente, agregar al final (con tail) → O(1)
- Doblemente enlazada: puntero prev → borrado por nodo en O(1), recorrer hacia atrás
El acceso es un recorrido
No puedes brincar hacia adelante — sigues next, un salto a la vez.
Nueve saltos para llegar a un valor cerca del final.
Distintas estructuras ganan distintas ops
Al frente: ganan enlazada/deque. Por índice: gana el array (~1300× en n=4000).
Usa la correcta
- Array por default — memoria contigua, amigable con el cache
deque cuando necesites extremos baratos en O(1)- Estructuras enlazadas debajo de colas, LRU caches, adyacencia de grafos
Conclusión
El array gana el índice y el cache.
La lista enlazada gana los extremos y las posiciones que ya tienes.
Sigue: acotar las operaciones a los extremos baratos → stacks y queues.