linked list mit random access
-
hi,
bin auf der Suche nach ner Daten Structur welche die gleichen Möglichkeiten wie ne linked list bietet.
Sie muß aber darüber hinaus auch noch die Elemente per Index anspringen können.
Such ich da vergebens oder hab ich was übersehen
Axo also dass ich alle Elemente durchlaufen kann bis ich bei Index x bin ist mir bekannt,
aber das dauert ja ewig...lg
-
Du könntest einen Zeiger auf deine Struktur definieren und dann dynamisch Speicher reservieren. Du hast Glück, dass du dabei die Funktion realloc verwenden kannst (oder so ähnlich, habe mich nie ernsthaft mit C auseinander gesetzt), dann musst du keinen Zwischenbuffer benutzen, um die Werte zu speichern, den Zeiger zu löschen, neuen Speicher zu reservieren, die Werte wieder in den Speicher zu schreiben und den Buffer zu löschen. Zumindest nach Dirk Louis.
-
hi,
also ich denke du meintest ein Statisches Array, dessen Größe durch realloc()
verändert wird? Nur dann müßt ich bei nem einfügen in der Mitte alle nach-
folgenden Elemente verschieben. Das wollt ich unbedingt vermeiden. Dacht auch
schon an eine mischung aus ner Linked List und nem Array "Unrolled Linked List"
aber optimal ists auch nicht
-
c_newbie schrieb:
.. bin auf der Suche nach ner Daten Structur welche die gleichen Möglichkeiten wie ne linked list bietet.
Sie muß aber darüber hinaus auch noch die Elemente per Index anspringen können.
Such ich da vergebens oder hab ich was übersehen
Axo also dass ich alle Elemente durchlaufen kann bis ich bei Index x bin ist mir bekannt,
aber das dauert ja ewig...Du kannst parallel zu Deiner linked List die Pointer auf die einzelnen Listenelemente in einem separaten Heapbereich aufheben, der "en bloc" bleibt und demnach arraymäßig ansprechbar ist. Mußt halt aufpassen, wenn Du die Features der List hernimmst, daß auch das Array upgedatet werden muß.
-
pointercrash() hat es schon beschrieben. Und was willst du? Wenn du ein neues Element einfügst, muss entweder Platz durch verschieben verschafft werden, oder dieses Objekt wird gelöscht. Ein bisschen Schwanger geht da nicht.
Und wenn du diese Objekte löschen willst, empfehle ich dir kein statisches Array. Es heisst ja statisch, weshalb es furchtbar unflexibel ist. Ich verwende immer Zeiger, da man bei denen zur Laufzeit bestimmen kann, wie gross sie sein sollen, und der Programmier nicht wissen muss, wie gross beispielsweise ein String maximal werden kann.
-
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.
-
Man koennte auch einen Baum nehmen, dann hat man fuer random access nur noch O( log Ewigkeit ).
-
wie wäre es denn mit einer art hashing? dann kannst du die elemente per index "anspringen" und hast ne nette datenstruktur
-
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...
lgWieson 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.
-
@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
-
Das Hashverfahren könnte die Lösung sein. Wenn du mehr Infos verrätst?
-
@knivil
mit nem bin-tree?Ja.
-
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.
-
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.
-
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.