Warum gibt es in Java keine SortedList?

Question

In Java gibt es die SortedSet y SortedMap Schnittstellen. Beide gehören zu den Java Collections-Framework und bieten einen geordneten Zugang zu den Elementen.

Nach meinem Verständnis gibt es jedoch keine SortedList in Java. Sie können verwenden java.util.Collections.sort() um eine Liste zu sortieren.

Haben Sie eine Idee, warum sie so gestaltet ist?

Answer 1

Ich denke, dass alle oben genannten Punkte diese Frage aus folgenden Gründen nicht beantworten,

1. Da dieselbe Funktionalität auch durch die Verwendung anderer Sammlungen wie TreeSet, Collections, PriorityQueue usw. erreicht werden kann ( aber dies ist eine Alternative, die auch ihre Beschränkungen auferlegt, d.h. Set entfernt doppelte Elemente. Einfach zu sagen, auch wenn es keine Einschränkung auferlegt, ist keine Antwort auf die Frage, warum SortedList nicht von der Java-Gemeinschaft erstellt wurde )
2. Da Listenelemente keine compare/equals-Methoden implementieren ( Dies gilt für Set & Map auch, wo im Allgemeinen Elemente nicht implementieren Comparable-Schnittstelle, aber wenn wir diese Elemente benötigen, um in sortierter Reihenfolge zu sein und wollen TreeSet/TreeMap verwenden, sollten Elemente implementieren Comparable-Schnittstelle )
3. Da List die Indizierung verwendet & aufgrund der Sortierung wird es nicht funktionieren ( Dies lässt sich durch die Einführung einer Zwischenschnittstelle/abstrakten Klasse leicht bewerkstelligen )

aber keine hat den genauen Grund dahinter gesagt & wie ich glaube, diese Art von Fragen können am besten von Java-Community selbst beantwortet werden, da es nur eine & spezifische Antwort haben, aber lassen Sie mich mein Bestes versuchen, diese als folgende zu beantworten,

Wie wir wissen, ist das Sortieren eine teure Operation, und es gibt einen grundlegenden Unterschied zwischen Liste und Set/Map, nämlich dass es in der Liste Duplikate geben kann, in Set/Map aber nicht. Dies ist der Hauptgrund, warum wir eine Standardimplementierung für Set/Map in Form von TreeSet/TreeMap haben. Intern ist dies ein Red Black Tree mit jeder Operation (Einfügen/Löschen/Suchen), die die Komplexität von O(log N) wo die Liste aufgrund von Duplikaten nicht in diese Datenspeicherstruktur passen könnte.

Nun stellt sich die Frage, ob wir auch eine Standardsortiermethode für die Liste wählen können, wie MergeSort die verwendet wird von Collections.sort(list) Methode mit der Komplexität von O(N log N) . Die Gemeinschaft hat dies nicht absichtlich getan, da wir mehrere Möglichkeiten für Sortieralgorithmen für nicht eindeutige Elemente haben wie QuickSort, ShellSort, RadixSort ...usw. In Zukunft kann es noch mehr geben. Außerdem funktioniert ein und derselbe Sortieralgorithmus je nach den zu sortierenden Daten manchmal unterschiedlich. Deshalb wollte man sich diese Option offen halten und uns die Wahl überlassen. Dies war bei Set/Map nicht der Fall, da O(log N) ist die beste Sortierkomplexität.

Answer 2

https://github.com/geniot/indexed-tree-map

Erwägen Sie die Verwendung von indexed-tree-map . Es handelt sich um ein erweitertes JDK's TreeSet, das den Zugriff auf Elemente nach Index und die Suche nach dem Index eines Elements ohne Iteration oder versteckte darunterliegende Listen, die den Baum sichern, ermöglicht. Der Algorithmus basiert auf der Aktualisierung der Gewichte der geänderten Knoten bei jeder Änderung.

Answer 3

Wir haben Collections.sort(arr) Methode, die beim Sortieren von ArrayList arr. helfen kann. Um absteigend sortiert zu werden, können wir Collections.sort(arr, Collections.reverseOrder())