Reinventarlo

Insertar en orden: ¿array o lista?

Tienes que mantener ordenada una colección de 100 000 números a la que llegan números nuevos. Cada número nuevo hay que buscarlo (recorriendo hasta su sitio) e insertarlo.

Con la lista, buscar recorre nodos dispersos y enlazar es O(1).
Con el array, buscar recorre valores contiguos (o búsqueda binaria) e insertar desplaza valores contiguos.

Mantienes ordenados 100 000 números y buscas el sitio de cada nuevo recorriendo hasta él, tanto en la lista como en el array. ¿Cuál suele ganar en la práctica?Empatan: las dos son O(n) por inserción, así que en tiempo miden lo mismo con cualquier cantidad de datosLa lista: insertar es O(1) y eso la hace más rápida que desplazar valores del array en cada inserciónLa lista: no necesita reservar capacidad de sobra ni copiar todo cuando el bloque se llena para crecerEl array: la búsqueda domina y es más rápida en memoria contigua, y desplazar contiguo también es rápido