verbesserte Laufzeit bei LinkedList

Mariexshhx

Bekanntes Mitglied
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

Super-Moderator
Mitarbeiter
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

Bekanntes Mitglied
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

Super-Moderator
Mitarbeiter
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

Bekanntes Mitglied
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

Super-Moderator
Mitarbeiter
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?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Build-Zeitpunt (Datum und Uhrzeit) irgendwie während der Laufzeit zugänglich machen..? Allgemeine Java-Themen 4
M Laufzeit des Prim Algorithmus Allgemeine Java-Themen 3
M Laufzeit LinkedList Allgemeine Java-Themen 9
K Verbesserung der Laufzeit beim Sortieren von Einwohnern nach ihrem Geburtsjahr Allgemeine Java-Themen 0
H was ist den dieses zur Kompilierzeit und zur Laufzeit in Java? Allgemeine Java-Themen 3
L Classpath Zur Laufzeit bestimmte Klassen in Classloader hinzufügen? Allgemeine Java-Themen 4
L Compiler-Fehler Google Guice Module zur Laufzeit zusammenstellen und binden Allgemeine Java-Themen 4
J Jasper Reports - Subreport zur Laufzeit ändern Allgemeine Java-Themen 6
O jar und EXE Dateien, Pfade zur Laufzeit Allgemeine Java-Themen 1
T Externe Java Klasen zur Laufzeit einbinden Allgemeine Java-Themen 10
X Collections Gibt es eine Klasse welche die Vorteile von List und HashMap vereint, aber konstante Laufzeit (O(1)) hat in Java? Allgemeine Java-Themen 4
D Boolean von ein anderem Java Programm während der Laufzeit ändern Allgemeine Java-Themen 23
N Generic Type einer Generischen Klasse während der Laufzeit bekommen Allgemeine Java-Themen 2
J .java-Dateitext Compile zur Laufzeit ohne File Allgemeine Java-Themen 15
kodela Daten während Laufzeit zugriffsbereit Allgemeine Java-Themen 15
Neumi5694 Interpreter-Fehler final Eigenschaft während Laufzeit geändert Allgemeine Java-Themen 2
A Java Klasse auf Tomcat während der Laufzeit austauschen Allgemeine Java-Themen 1
M Sinn von Kompilierung zur Laufzeit Allgemeine Java-Themen 3
T Java Class Intrumentation mit Annotations in Laufzeit Allgemeine Java-Themen 1
S Byte Array welches in Laufzeit aufgelöst wird // Objekt Array Allgemeine Java-Themen 3
T Dateien zur Laufzeit in Java-Programm packen? Allgemeine Java-Themen 3
S Laufzeit Primzahlgenerator Allgemeine Java-Themen 18
S Zur Laufzeit Klasse mit einer anzahl von X Objekten erstellen Allgemeine Java-Themen 5
F Classpath Programmteile zur Laufzeit nachladen Allgemeine Java-Themen 6
D Variablen zur Laufzeit global speichern (Registry Pattern?) Allgemeine Java-Themen 6
H ResourceBundle während Laufzeit bearbeiten Allgemeine Java-Themen 3
J Input/Output Jar-Datei zur Laufzeit erweitern Allgemeine Java-Themen 13
P Generic zur Laufzeit Allgemeine Java-Themen 4
A ar während der Laufzeit überschreiben Allgemeine Java-Themen 20
X MergeSort Laufzeit Problem Allgemeine Java-Themen 4
J Resourcen waehrend der Laufzeit aendern? Allgemeine Java-Themen 9
P Wie bei log4j den Dateipfad der Logdatei zur Laufzeit ändern? Allgemeine Java-Themen 3
X Update einer Jar während der Laufzeit Allgemeine Java-Themen 8
T Klassen Fabrik (Factory) zur Laufzeit erweitern Allgemeine Java-Themen 5
S UML zur Laufzeit ändern Allgemeine Java-Themen 10
E Wert von enum zur Laufzeit festlegen. Allgemeine Java-Themen 5
L Methode in Thread mit langer Laufzeit unterbrechen (ANT executeTarget) Allgemeine Java-Themen 4
O Problem bei Darstellung der Laufzeit eines Programms Allgemeine Java-Themen 3
hdi Ressourcen dynamisch zur Laufzeit laden Allgemeine Java-Themen 15
A Wie zur Laufzeit auf Objekte zugreifen Allgemeine Java-Themen 7
N variable Anzahl von Objektinstanzen zur Laufzeit erstellen Allgemeine Java-Themen 4
P Java Konsole zur Laufzeit einblenden Allgemeine Java-Themen 4
P Klassenwahl zur Laufzeit Allgemeine Java-Themen 5
R Objekt zur Laufzeit zerstören? Allgemeine Java-Themen 12
E formartierte Ausgabe zur Laufzeit Allgemeine Java-Themen 2
Sonecc Zugriff auf Class File einer anderen Jar während der Laufzeit Allgemeine Java-Themen 2
F Wie zur Laufzeit ganz neue Objekte erzeugen? Allgemeine Java-Themen 5
T Class-files zur Laufzeit zu Reflection-Zwecken laden Allgemeine Java-Themen 18
DamienX Debug Modus zur Laufzeit erkennen Allgemeine Java-Themen 3
Stillmatic Debuggen/ Laufzeit von Methoden Allgemeine Java-Themen 2
Dragonfire Generic Typ zur Laufzeit Allgemeine Java-Themen 9
M Klasse zur Laufzeit ersetzen Allgemeine Java-Themen 10
S Wie gross ist die Laufzeit für diese Schleife?? Allgemeine Java-Themen 8
G File zur Laufzeit erzeugen Allgemeine Java-Themen 4
G Jar File zur Laufzeit ändern. Allgemeine Java-Themen 4
T Java - Compilieren während Laufzeit Allgemeine Java-Themen 3
Y JARs austauschen zur Laufzeit Allgemeine Java-Themen 11
G Datenbank zur laufzeit wechseln Allgemeine Java-Themen 11
C Innere Klassen zur Laufzeit Instanzieren Allgemeine Java-Themen 4
T Zur Laufzeit erben? Allgemeine Java-Themen 22
L HashMap / Objekte auf Festplatte zur Laufzeit auf HD swappen Allgemeine Java-Themen 7
L Zur Laufzeit eine Klasse laden, die auf jar-File zugreift Allgemeine Java-Themen 15
V Java-Programm weiss zur Laufzeit wie es gestartet wurde? Allgemeine Java-Themen 6
N Endlosschleifen automatisiert erkennen (Code oder Laufzeit)? Allgemeine Java-Themen 6
G Eindeutiges Identifizieren einer JTable/Component z.laufzeit Allgemeine Java-Themen 2
G Datei durchsuchen, lange Laufzeit! Allgemeine Java-Themen 2
A log4j 1.3 und ändern der log Konfiguration zur Laufzeit Allgemeine Java-Themen 4
Apo Zur Laufzeit Klassen mit Packages laden? Allgemeine Java-Themen 2
G genauen Typ einer generischen Klasse zur Laufzeit ermitteln Allgemeine Java-Themen 2
F Typ eines Objekts zur Laufzeit bestimmen? Allgemeine Java-Themen 8
T xverify-parameter : Workaround zur Laufzeit? Allgemeine Java-Themen 8
M Bibliotheksname zur Laufzeit ermitteln (Classloader) Allgemeine Java-Themen 7
G Klasse wird zur Laufzeit nicht gefunden? Allgemeine Java-Themen 3
@ zur Laufzeit Interface aus jar implementieren? Allgemeine Java-Themen 5
MQue Laufzeit Allgemeine Java-Themen 4
D Lautstärke einzelner AudioClips zur Laufzeit verändern Allgemeine Java-Themen 4
C Mathefunktion zur Laufzeit einlesen und dann verarbeiten Allgemeine Java-Themen 13
G Klassen zur Laufzeit einbinden Allgemeine Java-Themen 3
J Bibliotheken erst zur Laufzeit laden Allgemeine Java-Themen 5
R Drag und Drop - Fehler während Laufzeit Allgemeine Java-Themen 14
byte Generic Type einer List zur Laufzeit rausfinden? Allgemeine Java-Themen 4
A Class File zur Laufzeit laden ohne den Binary Name zu kennen Allgemeine Java-Themen 11
M Überprüfen einer zur Laufzeit geladenen Klasse Allgemeine Java-Themen 3
H Klassen aus einem Ordner zur Laufzeit laden. Allgemeine Java-Themen 6
S Laufzeit und Compilefehler Allgemeine Java-Themen 6
S JPanel zur Laufzeit verbergen bzw. wieder anzeigen lassen Allgemeine Java-Themen 4
F Objektname zur Laufzeit festlegen? Allgemeine Java-Themen 12
I Sprache zur Laufzeit des Programms ändern Allgemeine Java-Themen 3
G Laufzeit eines aus Java gestarteten Programms beobachten Allgemeine Java-Themen 3
S Log4J: Logdatei zur Laufzeit ermitteln. Allgemeine Java-Themen 2
I Zur Laufzeit ermitteln, ob Klasse in JAR-Datei Allgemeine Java-Themen 2
R iText.jar wird zur Laufzeit nicht gefunden Allgemeine Java-Themen 4
J ResourceBundle / properties-datei während der Laufzeit verän Allgemeine Java-Themen 6
H Methode einer zur Laufzeit generierten Instanz aufrufen Allgemeine Java-Themen 2
M Formel in einem String während Laufzeit berechnen. Allgemeine Java-Themen 4
O Werte einer Generic LinkedList zusammenrechenen Allgemeine Java-Themen 14
M Delete bei sortierter LinkedList Allgemeine Java-Themen 5
M ArrayList oder LinkedList Allgemeine Java-Themen 10
L Unterschied zwischen List und LinkedList implementierung? Allgemeine Java-Themen 15
K Gespeicherte Daten von einer LinkedList auf vier LinkedList verteilen Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben