Sortierte Liste und compareTo

Eine sortierte Liste hält die Invariante: aufeinanderfolgende Elemente stehen in nicht fallender Ordnung bezüglich einer Ordnung. Einfügen sucht die Stelle und hängt den Knoten ein.

In Java liefert Comparable.compareTo die natürliche Ordnung. Comparator erlaubt eine externe Ordnung ohne die Elementklasse zu ändern.

Beispiel: Einfügen von 5 in 1-3-8 ergibt 1-3-5-8.

Komplexität: Suche $O(n)$ in der verketteten Liste, danach $O(1)$ Umhängen.

Wo gebraucht

Kleine sortierte Mengen, Merge von Streams, Prioritäten ohne vollen Heap, wenn n klein bleibt. compareTo/Comparator ist dieselbe Ordnung, die TreeMap, Sortierung und PriorityQueue nutzen.

Vertiefung

Eine sortierte Liste erhält nach jeder Änderung die Invariante, dass aufeinanderfolgende Elemente gemäss Vergleichsrelation nicht absteigen. Die Einfügeposition ist die erste Stelle, an der das neue Element nicht mehr grösser als der aktuelle Wert ist.

compareTo liefert ein negatives, null oder positives Ergebnis. Der konkrete Betrag besitzt keine portable Bedeutung. Eine konsistente Ordnung sollte transitiv und antisymmetrisch im Vorzeichen sein; andernfalls können Suche und Einfügen widersprüchliche Positionen liefern.

Bei einer verketteten Struktur bleibt die Suche nach der Stelle linear. Sortierung verbessert dort nicht den wahlfreien Zugriff, kann aber frühes Abbrechen bei Suche und geordnete Zusammenführung zweier Listen ermöglichen.

Schwierigkeitsstufen

1. Das Vorzeichen von Vergleichsergebnissen korrekt lesen.
2. Eine Einfügeposition unter Duplikatregeln bestimmen.
3. Folgen einer nichttransitiven Vergleichsrelation analysieren.

Fallstricke

Code darf nicht voraussetzen, dass das Ergebnis genau -1, 0 oder 1 ist. Ausserdem kann eine Ordnung, die mit equals unvereinbar ist, überraschende Duplikatsemantik erzeugen.