linked list mit random access

[pointercrash**]

c_newbie schrieb:

... Dacht auch schon an eine mischung aus ner Linked List und nem Array "Unrolled Linked List" aber optimal ists auch nicht

Wird aber so gemacht, hast Du korrekt erfasst. Die Listenelemente sind zwangsweise größer als die Pointer drauf, also schubst Du besser die Pointer herum, als ein komplettes, großes dyn. Array.
Wenn Dir das immer noch zu lahm ist, gibt's dann noch so Tricks, dieses Array auch aufzubrechen und mit Teiltabellen auf Listenteile zu arbeiten - aber das wird dann wirklich aufwendig, da nimmst Du dann besser eine fertige DB- Library her.

[knivil]

Man koennte auch einen Baum nehmen, dann hat man fuer random access nur noch O( log Ewigkeit ).

[hando]

wie wäre es denn mit einer art hashing? dann kannst du die elemente per index "anspringen" und hast ne nette datenstruktur

[index0r]

c_newbie schrieb:

Axo also dass ich alle Elemente durchlaufen kann bis ich bei Index x bin ist mir bekannt,
aber das dauert ja ewig...
lg

Wieson das? Das Durchlaufen indexbasierter Arrays ist doch schnellste wo gibt. Es sein denn du willst nach irgendwas suchen, dann nimm be Binärsuche oder eine Hashtabelle.

[c_newbie]

@pointercrash()
meinst du mit DB-Library sowas wie SQLite?

@knivil
mit nem bin-tree?

@index0r
ja da hast du vollkommen recht, aber ich wollte eigentlich in der Mitte
löschen und einfügen dafür brauch ich doch dann schon fast ne verkettete Liste
in dieser Liste müßt ich nun auch noch das Element an Position X abfragen
und da liegt genau das Problem, ich kann den Elementen zwar sowas wie nen
Primary key verpassen und den in nem bin-tree mit nem zeiger auf das Element
ablegen. Womit ich dann das Listenelement in O(log n) abfragen kann.
Damit kann ich doch dann immer noch nicht Element an Pos xy abfragen,
und dass ist genau das was ich brauch

@hando
eher als alternative zum bintree

[index0r]

Das Hashverfahren könnte die Lösung sein. Wenn du mehr Infos verrätst?

[knivil]

@knivil
mit nem bin-tree?

Ja.

[pointercrash**]

c_newbie schrieb:

@pointercrash()
meinst du mit DB-Library sowas wie SQLite?

Klar sowas. Dein Problem reicht in den Bereich von DBs rein, ob's jetzt der Overkill für die Geschichte ist, mußt Du entscheiden.
Für meinen Teil bilde ich mir gar nicht erst ein, das viel besser hinzukriegen, als das, was ich da "einfach so" zulinken kann.

[c_newbie]

das Problem mit dem zulinken ist, dass ich nicht genau weiß was abläuft.
Um das besser zu verstehen versuche ich mich mit den Structuren zu
beschäftigen. Also es geht nicht darum das Rad neu zu erfinden, oder sich
einzubilden es besser zu können, rein ums verstehen wann welcher Index
verwendet wird und evtl. welche kombinationen günstig sind.

[Der aus dem Westen ...]

An was denkst du dabei?

Ein Array hat den Vorteil, dass es statisch ist und der Programierer weniger Sorgen hat. Der Nachteil: es ist statisch, kann somit nicht wachsen.

Ein Zeiger kann dynamisch wachsen und lässt sich (wie das Array) durch einen Index ansprechen. Der Nachteil: Wenn du den reservierten Speicher erhöhen willst und die Werte erhalten bleiben sollen, brauchst du einen Buffer.

Eine List kanm dynamisch wachsen und schrumpfen. Der Nachteil: Man kann keinen Index verwenden, um die Werte anzusprechen, und wenn man Listen implementiert, braucht man (meiner Erfahrung nach) ein bisschen viel Code, um volle Funktionalität zu bekommen.