Opción 1: Haga una lista que implemente Comparable y ordénela usando collections.sort (Lista l) cada vez que agregue un valor. Opción 2: hacer un TreeSet (que se mantiene ordenado todo el tiempo).

¿Cuál será más rápido? Pregunto esto porque List me da la opción de ListIterator que necesito en mi caso, ya que me permite agregar un elemento mientras itero.