verbesserte Laufzeit bei LinkedList

[Mariexshhx]

Hey, für die Operationen contains und und remove einer Linkedlist, wenn diese sortiert ist kann man dadurch eine bessere Worstcase Laufzeit für contains und remove erzwecken ? ich denken ja, weil wenn das Element was ich suche recht groß ist kann ich ja von hinter drüber iterieren und wenn es klein ist von vorne. Die Frage ist wie definiere ich groß und klein. Weil so könnten die Elemente ja schneller gefunden werden. Im normalen Worstcase also wenn die Liste nicht sortiert ist, beträgt die Worstcase Laufzeit ja O(n). Wie wäre es dann mit der Laufzeit für eine sortierte Liste. Die implemetierung von contains und remove darf für eine bessere Laufzeit angepasst werden. Kann mir jemand helfen ?🙂

 

[KonradN]

Spiel doch Deine Gedanken etwas weiter durch. Was bringt es, da etwas zu "gross" oder "klein" zu sagen? Wie willst Du es festlegen? Und was bringt es? Was ändert sich an der Laufzeit, wenn Du sicher sagen kannst, in welcher Hälfte der Eintrag wäre? Ändert sich die Laufzeit weg von O(n)?

 

[Mariexshhx]

Spiel doch Deine Gedanken etwas weiter durch. Was bringt es, da etwas zu "gross" oder "klein" zu sagen? Wie willst Du es festlegen? Und was bringt es? Was ändert sich an der Laufzeit, wenn Du sicher sagen kannst, in welcher Hälfte der Eintrag wäre? Ändert sich die Laufzeit weg von O(n)?

wie wäre es binäre Suche anzuwenden? Das wäre ja schonmal schneller als alle Indexe durchzugehen... Ich weiß nur nicht, ob das für LinkedList geht. Die Laufzeit wäre dann O(log n) wenn ich nicht falsch liege ....

 

[KonradN]

wie wäre es binäre Suche anzuwenden?

Wie sind die Daten einer Linked List gespeichert? Wir kann man da eine binäre Suche nutzen?

 

[Mariexshhx]

Wie sind die Daten einer Linked List gespeichert? Wir kann man da eine binäre Suche nutzen?

In Listobjekten (also Key und Nachfolger). Ich denke das geht über die Indexe und dann immer vergleichen ist der Key größer oder kleiner als das gesuchte Objekt und dann in der jeweiligen Hälfte weitersuchen

 

[KonradN]

In Listobjekten (also Key und Nachfolger). Ich denke das geht über die Indexe und dann immer vergleichen ist der Key größer oder kleiner als das gesuchte Objekt und dann in der jeweiligen Hälfte weitersuchen

Das ist unverständlich .... Wie genau ist die Liste organisiert? Und wie willst Du dann über den Index zugreifen?

 

[Mariexshhx]

Das ist unverständlich .... Wie genau ist die Liste organisiert? Und wie willst Du dann über den Index zugreifen?

Ich weiß nicht wie es genauer sagen soll, als dass sie aus Listenelementen besteht und ein Listobjekt (eine eigene Klasse) besteht aus einem Key (also der Wert der das Objekt hat) und einem Nachfolger (auf welchen Wert zeigt das Objekt )

 

[KonradN]

Ja, die Beschreibung ist ja schon ok.

Nun fehlt nur, wie Du nun auf Elemente zugreifen kannst. Speziell die Frage, wie Du über einen Index zugreifen kannst. Wie greifst Du auf das 10. Element einer LinkedList zu?