|
tOAsD
|
 |
« : November 14, 2008, 23:02 » |
|
Ich habe eine einfach verkettete Liste mit einem Zeiger auf den Kopf. Ich kann in etwa n^n Zeit am Ende löschen. Jetzt wollte ich einen Zeiger auf das vorletzte Element mitverwalten um das Löschen am Ende in konstanter Zeit zu ermöglichen, das sollte für Einfügen auch kein Problem sein. Für löschen komm ich aber nicht an das Vorgängerelement, auf das ich den Zeiger für das vorletzte Element nach dem Löschen setzen muss, richtig?
Hilft da nur doppelt verkette Liste oder hab ich was übersehen?
|
|
|
|
|
H0LL0
|
|
« Antwort #1 : November 15, 2008, 10:28 » |
|
das ist leider der witz bei einer einfach verketteten liste und einem ringbuffer, dass du an die letzten elemente nicht rankommst.
verkettete listen sind eigentlich überhaupt nicht für konstante zugriffszeiten gedacht. und da man sie immer nur in eine richtung ablaufen kann, hast du wohl nichts übersehen.
|
p.S. Dieser Beitrag wurde im 10-Finger System erstellt. Ich bitte darum, ihn entsprechend zu würdigen.
|
|
|
|
tOAsD
|
|
« Antwort #2 : November 15, 2008, 13:19 » |
|
Naja am Anfang kann ich löschen und einfügen in konstanter Zeit, kein Problem durch den Zugriff auf kopf.. Am Ende dachte ich eben durch ein vorletztesElement oder so, das auch zu können, das würde für's Einfügen wie gesagt vermutlich auch gehen (noch nicht getestet, nur programmiert).. nur fürs Löschen seh ichs noch nicht, wie  Vielleicht ein drittletzes Element mitführen, aber dann kann man nur einmal hinternander löschen? |
|
|
|
|
|
H0LL0
|
|
« Antwort #3 : November 16, 2008, 16:16 » |
|
nunja, vielleicht gibt es eine elegante lösung, aber nur wenn man über den tellerrand der bisher gegebenen informationen hinausschaut. angenommen du hast die verkettete liste als struct in c geschrieben, kannst du dein vorhaben nicht ohne verwaltungs bzw. speicheraufwand realisieren.
haste vielleicht noch ein paar mehr details zu dem problem, das du da hast?
|
|
|
|
|
|
tOAsD
|
|
« Antwort #4 : November 16, 2008, 23:53 » |
|
es ist in java also kein wildes im speicher rumspringen, nodes sind ne eigene klasse die halt bisher nur nen next zeiger und ein inhaltsfeld hatten... verwaltungs/speicheraufwand ist jetzt nicht so das problem, es ging mir nur darum die laufzeit konstant zu halten statt n oder größer zu erreichen.. ich denke mittlerweile dass es nur per doppelt verketteter liste am sinnvollsten ist. ich kann mir keine andere option denken, wie ich mehrere hintereinander am ende löschen kann ohne die liste durchzugehen und ohne alle vorgänger zu kennen. vom speicheraufwand ist doppelt verkettet ja auch nicht so riesig, ich hatte nur halt eigentlich keine lust es zu schreiben, da ich fast alles mit einfacher verkettung fertig hatte, sprich vorher nicht gut überlegt bzw. die einfache sowieso gebraucht und dann probiert zu optimieren |
|
|
|
|
|
H0LL0
|
|
« Antwort #5 : November 17, 2008, 19:50 » |
|
konstante zeiten sind in java immer sone sache doppet verketten is wohl am einfachsten |
|
|
|
|
|
tOAsD
|
|
« Antwort #6 : November 17, 2008, 21:29 » |
|
konstant im sinne von nicht linear oder schlimmer wachsend ich habs jetzt mit doppelt verketteter in konstanter zeit gemacht, da läuft eher der speicher über, als dass das einfügen da länger als 1 sekunde dauert (nicht pro element sondern gesamt), vorher hab ich nach fast 20 minuten für ein nichtmal hunderttausend elemente abgebrochen  |
|
|
|
|
|
H0LL0
|
|
« Antwort #7 : November 18, 2008, 08:34 » |
|
wieso nimmst du denn dann überhaupt verkettete listen? die bereits implementierten collections sind doch üblicherweise deutlich schneller
|
|
|
|
|
|
tOAsD
|
|
« Antwort #8 : November 18, 2008, 19:36 » |
|
Handarbeit ruled?  Ne aber ich hab von den Collections keine Ahnung, muss ich mir bei Gelegenheit mal anschauen |
|
|
|
|
|
H0LL0
|
|
« Antwort #9 : November 18, 2008, 20:55 » |
|
Verkettete listen haben eigentlich kein tolles laufzeitverhalten: O(n) index lookup O(1) delete O(1) insert wobei man bedenken muss, dass einem löschen, oder einem insert oft ein lookup vorauseilt. das heißt, index delete und index insert haben auch O(n) als laufzeitverhalten Ich kenne das laufzeitverhalten der Java Collections leider nicht. Ich kenne nur Werte für C++ Dort hat die Containerklasse std::vector üblicherweise ein deutlich besseres laufzeitverhalten: O(1) index lookup O(n) delete O(n) insert vector gibt es in java auch. ist für die meisten anwendungen auch die klasse, die man benutzen sollte, da sie index lookup unterstützt und üblicherweise recht schnell ist. und schwer zu bedienen ist sie auch nicht. wozu das rad neu erfinden? die O-Notations beschreibt wie sich die liste mit zunehmender anzahl elemente verhält. O(n) ist lineares verhalten. O(1) konstant. O(n²) wäre quadratisch. http://de.wikipedia.org/wiki/Zeitkomplexit%C3%A4thttp://de.wikipedia.org/wiki/O-Notation |
|
|
|
|
|
tOAsD
|
|
« Antwort #10 : November 18, 2008, 22:03 » |
|
danke das weiss ich, ich brauchte die liste für insert/delete + peek an ende und anfang und dafür ist sie perfekt |
|
|
|
|
|
Sangoku
|
|
« Antwort #11 : November 18, 2008, 22:09 » |
|
Hab dat jetzt mal nur überflogen, Zeiger sind nicht mein Gebiet.
Aber wenn es sich bei den Listenelementen um Objekte handelt (wäre logisch oder?*g)
Wieso packste die nicht einfach in eine ArrayList?
|
o
L_/
OL
This is Schäuble. Copy Schäuble into your signature to help him on his way to Überwachungsstaat.
|
|
|
|
tOAsD
|
|
« Antwort #12 : November 18, 2008, 23:21 » |
|
Weil Arrayslisten ne mistige Laufzeit haben wenn man da hunderttausende Elemente reinfügt? Außerdem gehts wie schon gesagt auch um den Übungseffekt |
|
|
|
|
|
Sangoku
|
|
« Antwort #13 : November 19, 2008, 00:35 » |
|
Achso, dann hab ich nix gesagt  |
|
|
|
|
|
H0LL0
|
|
« Antwort #14 : November 19, 2008, 19:16 » |
|
danke das weiss ich, ich brauchte die liste für insert/delete + peek an ende und anfang und dafür ist sie perfekt
ok, dann wär das geklärt. wenn man nur am anfang und am ende der liste arbeitet ist ne doppelt verkettete natürlich das beste. und es führt dann auch kein weg an doppelter verkettung vorbei, wenn man am ende arbeite übrigens: http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html ist auch eine doppelt verkette liste wozu das rad neu erfinden? und wenns dir um nen übungseffekt geht, dann programmier es in C |
|
|
|
|
|
tOAsD
|
|
« Antwort #15 : November 20, 2008, 22:44 » |
|
Danke für die Tipps, hab jetzt mal deren LinkedList angewandt aber noch keine großen Laufzeittests gemacht, schien mir lahm, aber das lag auch an meinem SUPER algo den ich damit implementiert hatte hehe die werden das schon optimal gemacht haben denk ich. auf jeden fall ists es weniger arbeit, wenn man weiss wie's geht. |
|
|
|
|
|
