Fenómeno

Insertar en medio sin mover nada

Un editor de texto guarda cada línea de un documento enorme. Cuando insertas una línea en medio, con un array habría que correr todas las líneas de abajo: cientos de miles de copias.

Hay otra forma: que cada línea sepa dónde está la siguiente. Insertar sería cambiar unas pocas indicaciones, sin mover nada.

Piensa antes de seguir: si cada línea solo sabe dónde está la siguiente, ¿qué operación se vuelve más cara que en el array?