Delete bei sortierter LinkedList

[Mariexshhx]

Hey ich habe die Frage, ob ich bei einer delete Funktion einer LinkedList die Laufzeit verkürzen kann, wenn die Liste sortiert ist. Ich hatte erst überlegt, dass man ja den Vorgänger von dem zu löschenden Elemente mit einer binären Suche schneller finden kann, anstatt über alle Elemente der Liste zu iterieren bis man den Vorgänger hat. Nur jetzt ist mir aufgefallen ich habe ja so gesehen keinen Suchschlüssel, weil ich den Vorgänger meines zu löschenden Elements ja noch nicht kenne. Denke ich so richtig oder kann man die binäre Suche doch irgendwie verwenden, um den Vorgänger des zu löschenden Elements zu finden

 

[KonradN]

Das ist doch der Punkt, den wir schon in https://www.java-forum.org/thema/verbesserte-laufzeit-bei-linkedlist.199920/ hatten.

Ist Dir klar, wie Du auf Elemente einer LinkedList zugreifen kannst? Wie kommst Du da zu dem mittleren von zwei Elementen?
Wenn da eine einfache Operation ist, dann kannst Du eine binäre Suche nutzen. Wenn es keine einfache Operation ist, dann geht es nicht.

Du musst Dich mit diesen Datentypen vertraut machen. Das sind alles Fragen, die man sich selbst schnell beantworten kann mit einem Blick auf die Dokumentation des Datentypen.

 

[LimDul]

Binäre Suche ist ziemlich scheise bei einer linken list.

 

[temi]

die man sich selbst schnell beantworten kann mit einem Blick auf die Dokumentation des Datentypen

Hier ist die Dokumentation: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

Es gibt zwar eine Methode get(int index), aber in der allgemeinen Beschreibung steht folgendes:

Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

 

[KonradN]

Wobei ich nicht einmal auf die Doku vom Framework hinaus wollte. Da wurde ja in Vorlesung oder Unterricht über verkettete Listen geredet. Die Funktionsweise sollte also bekannt sein. Und wenn nicht, dann sollte man sich damit vertraut machen.

Und dabei unterstütze ich auch gerne. Ich bin ja auch durchaus bekannt dafür, dass ich recht ausdauernd Dinge erläutern kann. Aber da muss halt auch was kommen.

 

[temi]

Jo, passt schon. Allerdings "kann" man schon, wenn man die Antwort etwas weiter fasst. Da gäbe es z. B. die SkipList, was dann allerdings keine reine LinkedList mehr ist.