doppelt verkettete Liste

[Reaper]

Stellt eine doppelt verkettete Liste einen Ring dar?
Was sind die Vorzüge gegenüber einer einfach verketteten Liste?

 

[stev.glasow]

Nein sollte sie nicht.


Und eine einfach verketteten Liste kannst du nur in eine Richtung durchlaufen eine doppelte in beide.

 

[crazy_N]

sie ist kein ring. es gibt ein anfang und ein ende. eine einfach verkettete kannst du nur in eine richtung durchlaufen. bei einer doppelt verketteten kannst du in beide richtungen gehen. dadurch ist es z.b. möglich ohne großen aufwand ein object vorher einzufügen.

 

[Reaper]

Kannst du mir ein konkretes Beispiel nennen wo das einen Vorteil bringt?

 

[crazy_N]

wenn du z.b. was in einer sortierten liste gleich an der richtigen stelle einfügen willst (z.b. wörter alphabetisch sortiert). dein wort fängt mit e an. du fängst oben an und schaust mit welchem buchstaben das aktuelle objekt anfängt. irgendwann bist du bei f angelangt. das bedeutet, dass dein objekt eine position höher eingefügt werden muss. bei einer doppelt verketteten liste kannst du einfach eins zurückspringen. bei einer einfach verketteten musst du wieder am anfang anfangen und dich durcharbeiten.

 

[Reaper]

So da ich ja jetzt gerade mit einem Beispiel für eine doppelt verkettete Liste angefangen habe kannst du mir vielleicht sagen wieso ich sie hierbei brauche.
Bsp.: Mehrere Kinder bilden einen Kreis. Durch einen Reim wird ein Kind ermittelt, welches den Kreis verlässt. So nun soll ich dass ganze eben in einen Algorithmus verwandeln. Hierbei wird eben beschrieben dass ich für den Kreis eine doppelt verkettete Liste nehmen soll.

 

[stev.glasow]

In dem fall kann man die Liste schon wie einen Kreis laufen lassen.
Und sie ist doppel verkettet weil du dich ja in beide Ritungen der Liste bewegen willst.
Sagen wir du hast noch 10 Kinder im Kreis du hast zu letzt das 2. entfernt und wills jetzt das 9. entfernen.
Jetzt musst du zum 9. Element 'gehen' um dieses zu entfernen ,das würde bei einer einfach Verketteten Liste heißen, dass du erst 7 Schritte nach rechts gehen musst (2. -> 3. -> 4. -> 5. -> 6.-> 7-> 8. -> [9.] ) , bei einer doppelverketten Liste reichen 4 Schritte da du auch rückwärts gehen kannst. sprich 2. -> 1. -> 10. -> [9]

 

[Reaper]

Und wie mach ich das dass ich meine Liste wie einen Ring behandle

 

[foobar]

Und wie mach ich das dass ich meine Liste wie einen Ring behandle

Indem das erste Element auf das letzte zeigt und das letzte wieder aufs erste, das ist dann eine zirkulär verkettete Liste