proggen.org struct:list http://update.proggen.org/ 2026-04-19T13:48:14+0200 proggen.org http://update.proggen.org/ http://update.proggen.org/lib/tpl/proggenY/images/favicon.ico text/html 2022-09-22T19:39:27+0200 Anonymous (anonymous@undisclosed.example.com) struct:list:double-linked http://update.proggen.org/doku.php?id=struct:list:double-linked&rev=1663868367 Doppelt verkettete Listen Bei einem Problem half der Listenkopf jedoch nicht weiter: Zum Entfernen und Hinzufügen von Elementen benötigen wir weiterhin grundsätzlich den Vorgänger, den wir nur mit sehr viel Aufwand wieder herausfinden können. Eine triviale Lösung ohne mehr Speicherverbrauch gibt es nicht, also bemühen wir eine triviale Lösung, die etwas mehr Speicher verbraucht. text/html 2022-09-22T19:39:27+0200 Anonymous (anonymous@undisclosed.example.com) struct:list:head http://update.proggen.org/doku.php?id=struct:list:head&rev=1663868367 Listenköpfe Den Aufwand, bei jedem Entfernen auch zu prüfen, ob man den Listenkopf überarbeiten muss, möchte man sich selbstverständlich sparen, zumal die Überprüfung in dieser Form sich im Code häufig wiederholen würde. Code, der sich wiederholt, gehört in eine entsprechende Funktion. Eine Möglichkeit ist DeleteNode zusätzlich die Addresse vom Zeiger auf den Listenkopf zu übergeben: text/html 2022-09-22T19:39:27+0200 Anonymous (anonymous@undisclosed.example.com) struct:list:owner http://update.proggen.org/doku.php?id=struct:list:owner&rev=1663868367 Referenz auf den Listenkopf Beim Entfernen eines Elementes könnten wir zuerst die Liste durchsuchen, ob das Element überhaupt mit dieser Liste verwaltet wird. Das ist allerdings aufwendig. Zum Einfügen müsste weiterhin jede Liste durchsucht werden, bei dem das Element Mitglied sein könnte. Das kostet massivst Rechenzeit. Eine Mehrleistung kostet immer Rechenzeit oder Arbeitsspeicher. Im schlimmsten Fall beides. text/html 2022-09-22T19:39:27+0200 Anonymous (anonymous@undisclosed.example.com) struct:list:single-linked http://update.proggen.org/doku.php?id=struct:list:single-linked&rev=1663868367 Einfach verkettete Listen Die einfachste Form einer Liste ist ein Node, das ein Datenelement enthält und einem Zeiger auf das nachfolgende Element. Besteht ein Datensatz zum Beispiel aus einer Adresse, so kann ein Datensatz zum Beispiel so aussehen: text/html 2022-09-22T19:39:27+0200 Anonymous (anonymous@undisclosed.example.com) struct:list:start http://update.proggen.org/doku.php?id=struct:list:start&rev=1663868367 Listen Motivation Auf Arrays kann man hervorragend sehr schnell zugreifen, da alle Einträge zwischen der 0. und der letzten Position in einem großen, zusammenhängendem Speicherblock aufgereiht liegen: Die Daten liegen im Array (engl. für 'Reihe'). Bei manchen Systemen können diese großen Speicherblöcke zu Problemen führen, weil das Betriebssystem gar nicht so große, zusammenhängende Speicherblöcke liefern kann. Dieser Grund ist bei heutigen PCs und modernen Betriebssystemen nicht mehr so aussc…