suche in einer einfach verketteten liste
-
hi,
ist das richtig, das die suche nach einem element in einer einfach verketteten liste tendenziell schneller ist, wenn diese sortiert ist ( aufsteigende sortierung: 0...n )?
wenn die zu suchenden elemente nicht alle groesser als n sind, sondern einigermassen verteilt sind, muesste im schnitt das ganze schneller funzen, wa?
mfg.
-
list n00b schrieb:
hi,
ist das richtig, das die suche nach einem element in einer einfach verketteten liste tendenziell schneller ist, wenn diese sortiert ist ( aufsteigende sortierung: 0...n )?ja, denn bei nichtfindung kann die suche abgebrochen werden, sobald der suchschlüssel größer als der aktuelle wert ist.
das sotieren der liste zu diesem zweck oder das sortierte einfügen ist aber technischer unfug. verkettet listen haben keinen spaß dran, sortiert zu sein.
-
Ich denke mal, das kann man so pauschal nicht behaupten. Beim Einsortieren brauchst du im Mittel den halben Listenweg, beim Suchen auch. Macht in der Summe einen ganzen Listenweg.
Bei einer unsortierten Liste brauchst du die Elemente nur vorne vorzupacken oder hinten anzuhaengen- beim Suchen brauchst du einen ganzen Listenweg.Bleibt gehüpft wie gesprungen.
Gruß,
A.P.
-
Ändert aber nichts dran, dass es die falsche Datenstruktur ist. Wenn du Wert auf Sortierung legst dann nimm Suchbäume.