Alles, was die Daten in sortierter Form liefern kann, sei es ein Index oder ein sortierender Container, würde den Suchvorgang auf lineare Laufzeit verkürzen. Das Erstellen eines Index bzw. das Sortieren selbst ist aber O(n * log n). Wenn man den Index persistent halten kann oder die Daten sortiert wieder ablegt, hat man den Aufwand natürlich nur einmal.
@Moeki,
Dein Algorithmus ist nicht linear. Im Worst Case (nur ZZZZZ ist noch frei, und danach suchst du zuletzt) hast du quadratische Laufzeit. Wie wahrscheinlich dieser Worst Case ist, hängt aber davon ab, wie voll die Liste ist.