Hallo!
Mich hat schon immer interessiert, wie man eine dynamische Verwaltung realisiert (z.B. Studentenverwaltung oder ähnliches). Ich habe gehört, dass man dieses Problem am besten mit einer doppelt verketteten Liste lösen kann.
Meine Frage:
Was ist das und wie kann ich solch eine Liste programmieren?
Vielen dank für Eure Hilfe!
mfg Tobi
Hallo,
ich weiss zwar nicht, was das eine mit dem anderen zu tun hat, aber eine doppelt verkettete Liste funktioniert folgendermaßen:
Das Ziel ist eine Datenstruktur, bei der Einfüge- und Löschoperationen sowie Navigation in der Datenstruktur möglichst einfach ist. Nehmen wir als Beispiel ein mit sortierten Werten gefülltes Array. Eine Einfügeoperation müsste jetzt alle größeren Werte um ein Feld nach hinten verschieben (oder die kleineren nach vorne), damit Platz für das neue Element geschafft wird, ebenso müsste bei Löschvorgängen auch der REst der Liste verschoben werden. Eichfacher ist es, wenn in jeder Position des Arrays mit gespeichert wird, welches das nachfolgende Objekt ist. (Bei sortieter Liste, steht also zusätzlich 2,3,4,… im Array (-1=kein Element)), z.B.:
17 23 56 78
2 3 4 -1
Bei einer Einfügeoperation wird jetzt nichts mehr verschoben, sondern einfach die neue Zahl hinten angehängt und beim kleineren Element n als Nachfolger ein neues Element x eingetragen und von dort ein Zeiger auf das größere Element n+1. Beispiel: (Füge 47 ein)
17 23 56 78 47
2 5 4 -1 3
Wenn man dann die Liste durchgeht, weiss man das man vom 2. Element 23 zum 5. Element 47 muss, von da zum 3. Element 56, dann zum 4. …
Da man mit dieser einfach verketteten Liste nur die Nachfolgeelemente bekommt und man z.B. bei einer Löschoperation wissen muss, welche Zahl der Vänger ist, weil diese jetzt ja auf den Nachfolger der gelöschten Zahl zeigen muss, fügt man auch Indizes für die Vorgänger ein:
17 23 56 78 47
2 5 4 -1 3
-1 1 5 3 2
So einfach ist das! Diese Listen kann man z.B. wie gezeigt mit Arrays implementieren oder mit Pointern auf dem Heap. Beim Einfügen erzeugt man einen neuen Speicherplatz auf dem Heap, der Next-Pointer des Vorgängers wird dann auf die neue Adresse gebogen, der Next-Pointer des neuen Elements wird auf die alte Next-Adresse der Vorgängers gestellt…
Das wars, etwas kompliziert, aber einfach 
Ralph
Danke Ralph für Deine schnelle und sehr gute Antwort!
Bei C++ brauchst du die Dynamische verwaltung garnicht selber programmieren da verschiedenste Dynamische Datentypen in der STL-libary vorcodiert sind!
(unteranderem auch die doppelt verkettete liste!)
MFG Michael
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]