Schnelles suchen in einfach verketeter Liste

[Christian]

Ich hab da mal n kleines Problem für die alten Hasen.
Ich hab ne einfach verkettete Liste, die ich komplett durchgehn muss um ein Element zu finden.
Gibt es einen einfachen Weg, um das zu beschleunigen ?
Ich dachte daran die Liste zu sortieren und dann je nach irgendwo in de Mitte anzufangen zu suchen jedoch wird das immer alles so verdammt komplex. Ich lande immer wieder bei Bäumen. Gibt es da keine einfachere Möglichkeit ?

[Tillman]

Hmm.. mir fällt da auf die Schnelle nur bubblesort ein.

Ich denke, englisch ist dir geläufig.
http://www.wiu.edu/users/mflll/cs214/bubble_sort.html
aber der Code ist wenigstens in "international" geschrieben
Komplex ist die Routine nicht, nur ganz laaaaaaannn..g ähn,
aber innerhalb des Algorithmus kannst du gleich nach deinem Element suchen.
Sortieren abbrechen wenn Element gefunden.

[Christian]

Das sortieren ist gar kein stress, mir gehts wie geschrieben ums suchen.

[af0815]

Du wirst entweder um eine sortierte Liste nicht umhinkommen, der nächste Schritt ist die doppelt verkettet liste (von beiden Seiten aus zu durchsuchen. Oder die Bäume, die die Daten für die Suche optimiert halten. Genau dieses suchen war die Lösung für schnelle Suchabfolgen. Wenn die Daten komplexer sicd -> mehere Suchen -> dann musst du dir mit Indexbäumen helfen.

[Christian]

Wie schon einleitend gesagt stellt das sortieren kein Problem dar. Hab ich mich so undeutlich ausgedrückt ?

Ich hab jetzt eine sortierte Liste meinetwegen auch eine doppelt verkettete das wäre auch kein Problem. Aber wie geh ich nun in meiner sorteierten Liste ans suchen heran ? Ich weiss ja ohne Index nicht wo welcher anfangswert steht ?!
genauer gefragt wie geh ich am besten vor um mit Sprüngen näherungsweise ans Ziel zu kommen...

[theo]

Hast du diese Varianten schon mal durchgeschaut?
http://de.wikipedia.org/wiki/Suchverfahren

[Tillman]

@theo
ich vermute, bis Christian das alles gelesen und passende Algorithmen probiert und verworfen hat, ist er vom Thema ab.

@Christian
Kannst du dein Problem abstrahieren.
Ich bin immer noch der Meinung, dass Du mit dem Sortieren das Suchen gleich verbinden kannst.
Nenn doch mal ein Beispiel.

[Christian]

@theo, blindheit danke. die binary search dürfte für den anfang schon ganz gut sein.

@tillmann nein wüsste nicht warum man das verbinden sollte ?! dann muss ich zwangsweise jedesmal sortieren wenn ich was suchen will oder was ?

[pluto]

Evlt. auch nur beim ersten Sortieren da suchst du auch gleich.
beim zweiten suchen könntest du jetzt einfach die Stelle berechnen wo der Index sein müsste. z.b. alle Einträge die G anfangen könntest du übersrpingen wenn du nach einem Eintrag suchst der mit H anfängt. Allerdings müsstest du hier die anzahl irgendwie abspeichern. wie viele fangen mit G an ?

[Christian]

Ich hab aber von anfang an ausgeschlossen das ich nen Index will pluto.

[pluto]

Ja schon klar. Willst du bei null anfangen oder wie ?
jedes mal.

[theo]

@Christian: Bist du eigentlich sicher, dass du mit der verketteten Liste auf das richtige Pferd setzt? Wenn es dir hauptsächlich ums Suchen geht, dann wäre wohl ein binärer Suchbaum besser. Oder vielleicht auch ein Array?
Man kann deiner Frage halt nicht wirklich entnehmen was dein Ziel ist.

[Christian]

@Pluto, nein muss man nicht siehe Binäre Suche.

@Theo, ich hab eine Objektliste in der ich einen String hab nach dem ich suchen muss. Wenn ich die Struktur an sich jetzt übern Haufen werfe muss ich ne ganze menge Code neu schreiben. Wie meinst das mitm Array ?

[pluto]

warum verwendest du dafür nicht eine "Daten Bank" ?
da ist sowas schon dabei. Weil sich das so anhört das es sich um viele Daten Handelt.

[theo]

Wie meinst das mitm Array ?

Naja, ob der Binary Search mit verketteten Listen auch geht bin ich mir nicht ganz sicher.
Wie willst du denn auf ein beliebiges Element zugreifen, ohne die Liste durchzurattern?
Binary Search ist doch meist mit Arrays implementiert.
Kann mich auch irren....
Achtung: Binary Search <> Binary Tree