Come mantenere al meglio un elenco ordinato da un flusso di numeri interi?

Question

Se ho un flusso di numeri interi in arrivo, come posso mantenerne al meglio un elenco ordinato? L'unico modo in cui riesco a pensare è la ricerca binaria della posizione e spostare gli elementi rimanenti a destra. Ciò equivarrebbe a $ O (n + log n) $ volta. Esiste una struttura di dati migliore che può aiutarmi a raggiungere lo stesso in tempo migliore? So che possiamo usare un albero di ricerca binario equilibrato con $ O ( log n) $ Inserzioni ma vorrei avere un accesso efficiente nell'elenco.