Doppel schnell aus Liste löschen.

[Dejan Vu]

Natürlich kann es sinnvoll sein, eine Prüfung am Eingang vorzunehmen, aber rein rechnerisch ist der Aufwand eh der Gleiche. Wenn ich bei jedem Einfügen mit 'IndexOf' prüfe, ob es den Wert schon gibt, dann habe ich bei jedem Einfügen den Aufwand O(n). Wenn ich also N Elemente einfüge ist das O(n^2). Kein Unterschied zu vorher (vom Aufwand, Komplexität, Big-Oh). Klar, die zu durchsuchende Liste ist anfangs kürzer, insofern wird das schon etwas bringen, aber zuerst schrauben wir an der Komplexität (Aufwand, Algorithmus), und anschließend kümmern wir uns um den Kleinkram.

Wenn ich die Liste ständige sortiert halte, ist der Aufwand sogar höher, denn das Einfügen eines Wertes in eine Liste ist leider vom Aufwand O(n), denn auch wenn das Suchen schnell geht, muss ich doch Platz schaffen, um das Element in der Mitte irgendwo einzufügen, und das geht in einer normalen Liste nicht unter O(n). Ergo habe ich beim Einfügen in eine sortierte Liste den Aufwand O(log n) für das Suchen + O(n) für das Einfügen = O(n). Für N Elemente sind das wieder O(n^2).

Das lohnt sich nur, wenn die Wartezeit beim Einfügen eines Elements unwichtig ist bzw. in der Betrachtung keine Rolle spielt, z.B. da die Erfassung z.B. manuell oder nur sporadisch erfolgt.