Blatt7 Aufgabe 1.3

[Jan Harms]

Wo gibt es noch weitere Infos zu den doppelt verketteten Listen?
Ich habe auf der Vorlesungsfolie 10 nochmal geschaut. Da ist nur eine Folie zu d.v.Listen.
Von welcher Eigenschaft wird hier gesprochen?
Man könnte doch einfach jeder Instanz noch eine Variable geben, die die Länge enthält und bei jeder Operation (enqueue, dequeue, usw) diese Variable entsprechend verändern. Dies hat dann aber nichts mit der den d.v.Listen eigenen Eigenschaft zu tun. (Kann man ja für jeden Datentyp machen)

mfg

jan


--------------= Posted using GrabIt =----------------
------= Binary Usenet downloading made easy =---------
-= Get GrabIt for free from http://www.shemes.com/ =-

[Robert Buchholz]

Post by Jan Harms
Wo gibt es noch weitere Infos zu den doppelt verketteten Listen?
Ich habe auf der Vorlesungsfolie 10 nochmal geschaut. Da ist nur eine Folie zu d.v.Listen.
Von welcher Eigenschaft wird hier gesprochen?
Man könnte doch einfach jeder Instanz noch eine Variable geben, die die Länge enthält und bei jeder Operation (enqueue, dequeue, usw) diese Variable entsprechend verändern. Dies hat dann aber nichts mit der den d.v.Listen eigenen Eigenschaft zu tun. (Kann man ja für jeden Datentyp machen)

Hallo Jan,

das Speichern der Länge ist tatsächlich auch ohne doppelte Verkettung
möglich, wie du sagst. Dies verbessert die asymptotische Laufzeit von
getLenght().
Allerdings kannst du auch die praktische Laufzeit einiger anderer Option
durch doppelte Verkettung verbessern: Wie würdest du vorgehen, wenn du
eine Liste der Länge neun hast und das achte Element löschen musst?

Ciao,

Robert