Linked List Eintrag schneller suchen

[sen-me]

Gibt es eine Möglichkeit in einer Linked List einen Eintrag schneller zu suchen als sie immer von vorne durchlaufen zu lassen und mit dem Suchbegriff zu vergleichen?

[Tafkadasom2k5]

Wenn du ein Array hast, könnte man "quicksort" und "B-baum" anwenden. Da bei einer LinkedList aber keine Möglichkeit besteht, diese zu sortieren, geschweige denn, ein Item ganz präzise auszuwählen (z.B. "Gib mir Item 4". Das hat was mit der Technik zu tun, wie eine LinkedList funktioniert), hast du dann wohl ein Problem.

Einfach einen naderen Variablencontainer nehmen.

Gr33tz
Tafkadasom2k5

[Kiffi]

wie so oft: ohne Code kann man nur mutmaßen, was man noch optimieren
könnte.

eine Möglichkeit wäre es, die Schleife sofort zu verlassen, wenn der Eintrag
gefunden wurde (wird oft vergessen).

Grüße ... Kiffi

[mk-soft]

Index Listen erzeugen

[Karl]

Möglicherweise könnte man die LL von Zeit zu Zeit reorganisieren oder stattdessen Hashing verwenden.

Gruß Karl

[Hyper]

Hallo sen-me,

ich erstelle mir für schnelle Zugriffe auf große Listen parallel ein Array und speichere in Array-Element X den Pointer zum Listenelement X ab. Da kannst Du über den Array-Schlüssel und ChangeElement() schnell zugreifen :-)

[Karl]

Hallo Hyper,

ich denke das meinte mk-soft mit seiner Indexliste.

Gruß Karl

[edel]

Dann geht doch aber der Vorteil einer LL floeten, und man
kann auch gleich ein Array benutzen.

[Kaeru Gaman]

es kommt sowieso drauf an, was man machen will.
viele nutzen auch LLs für problemstellungen, wo ein array angebrachter wäre.
auch für'n array ist schnell ne schleife geschrieben, die elemente aufrückt.

[jear]

Nehmen wir mal an, es gelte eine wirklich große Liste zu durchsuchen, wobei über den Nachnamen zuzugreifen wäre.

Eine solche Liste hält man dann gut sortiert und speichert sie auch sortiert ab. Legt man sich nun noch ein Array mit den Startindizes der Anfangsbuchstaben an, kann man so den Zugriff dramatisch beschleunigen. Bei einem Buchstaben sind das dann 26, bei zweien 676 Indizes, die in einem Array abgelegt werden müssen. Lässt man Sonderzeichen und Zahlen in Namen zu, entsprechend mehr.