hilfe! verkettet liste!

[Gast]

ich hab ein problem: in meinem buch das ich zum lernen von c++ verwende wird andauernd die verkette liste als beispiel verwendet. aber ich versteh die irgendwie nicht, was hat das für einen sinn? zahlen eingeben lassen und rückwärts wieder ausgeben geht auch ohne so ne dämlich liste! das sind vielleicht 10zeilen code die ich brauchen würde. und diese blöde liste ist über 30 lang! also könnt ihr mir das erklären? oder kennt ihr sowas garnicht? wenn ihr wollt kann ich den quellcode auch komplett abtippen, das mach ich zwar sonst auch, aber ich hab ihn schonmal abgetippt und genützt hats mir nichts.. naja wär nett wen ihr mir helfen könntet, denn mich interresiert nur: was hat das für einen sinn?!

[liro]

kennst du schon arrays? auf jeden Fall hat ein Array einen feste Größe. Wenn du jetzt aber ne beliebig lange liste aufbauen willst, brauchst du ne eben die std::list.

also wie schon gesagt ... list wird dynamisch erweitert ... hat also keine feste größe

[Gast]

na kalr kenn ich arrays, mit den grunddatentypen bin ich durch (structuren und co auch) ich bin grade bei funktionen, das ist in meinem buch ein ganzes kapitel.. ähh ja, zum thema: das ist ja schön und gut, aber wofür zum teufel brauch ich denn ne unendlich lange liste? warum so ein drama um zeiger? ich versteh den sinn einfach nicht, was mir das jetzt bringt..

[liro]

na kalr kenn ich arrays, mit den grunddatentypen bin ich durch (structuren und co auch) ich bin grade bei funktionen, das ist in meinem buch ein ganzes kapitel.. ähh ja, zum thema: das ist ja schön und gut, aber wofür zum teufel brauch ich denn ne unendlich lange liste? warum so ein drama um zeiger? ich versteh den sinn einfach nicht, was mir das jetzt bringt..

hängt vom Problemfall ab ^^, wenn du z.B. bei ner GUI, ein Fenster hast und dieses Fenster hat Buttons, werden diese Buttons in so einer Liste gespeichert. Beim zeichnen wird die Liste einfach abgearbeitet , also jeder Button einzeln gezeichnet... nur so als beispiel

[Xardas2]

Der Sinn einer Liste ist ganz einfach. Wenn du ein Programm zur verwaltung von irgendwelchen Daten schreibst (Adressbuch), oder einen Text nach irgendwelchen Schlüsselwörtern durchsuchst (Compiler/Parser, Editor, Filter ...), Benutzereingaben bzw. allgemein wenn du irgendwelche Werte puffern musst, da du schneller Neue bekommst als du die alten bearbeiten kannst (Kommunikation zwischen mehreren Geräten z.B. Chatprogramm über LAN/Internet oder Messwerterfassung).

Der wesentliche Vorteil von verketteten Listen ist, dass sie in solchen Fällen Speichereffizienter sind und einen Stabilen Programmablauf garantieren.

Wenn du ein Array verwendest, wird ja bei Start deiner Anwendung eine gewisse Menge Speicher allokiert (reserviert).
Dieser ist für das System dann nicht mehr weiter nutzbar, auch wenn dein Programm eigentlich nur einen kleinen Bruchteil davon bräuchte, um z.B. Benutzereingaben zu puffern. Wenn du jedoch weniger Speicher allokierst und der Benutzer mehr Werte speichern will, als du vorgesehen hast oder wenn auf Grund einenr zu hohen Netzauslastung die Nachricht nicht gleich gesendet werden kann und dadurch mehrere Nachrichten Zwischengespeichert werden müssen, dann stürzt deine Anwendung mit einer für den Benutzer wenig sagenden Fehlermeldung ab.

Eine Liste dagegen allokiert zur Laufzeit deiner Anwendung immer nur dann neuen Speicher, wenn er wirklich benötigt wird und nutzt somit den Speicher trotz des Overheads (der zur Verwaltung der Liste zusätzlich benötigte Speicher) effizienter. Somit kann es zu kein Overflow des allokierten Speichers kommen. Den Fehlerfall, dass der Benutzer einen neuen Wert in der Liste Speichern will, aber das System nicht mehr über genügend Speicherplatz verfügt, kannst du elegant abfangen und dem Benutzer mitteilen, ohne dass die Anwendung abstürzt und die bisherige Arbeit zunichte macht.
Bei Zugriff auf die gespeicherten Werte und für die Verwaltung (neues Listenelement hinzufügen/entfernen) benötigt so eine Liste je nach Typ und Anzahl der Werte etwas mehr Zeit.


FAZIT:
Wenn du weist, dass dein Programm immer nur eine feste Anzahl von Werten Speichern muss und eine geringe Varianz* besitzt, benutze ein Array.
Soll deine Anwendung jedoch verschieden viele Werte verwalten können, dann lohnt sich der Einsatz einer Liste.


Gruß Xardas2


* wie groß der Unterschied der zu erwartenden Anzahl der Werte sein darf, musst du selbst festlegen, denn dies ist stark von der Größe des zu Speichernden Wertes und des eingesetzten Systems abhängig. Ob du 100 Integer mehr oder weniger speicherst macht im normal Fall keinen Unterschied (400 Byte von 2 - 4 GB ist vernachlässigbar). Wenn du jedoch keine Standardspeichertypen verwendest sondern gröere Strukturen oder Klassen, oder du dich auf einer sehr Hardwarenahen Schicht befindest (z.B. Mikrocontroller) können 10 Werte mehr oder weniger schnell eine große Rolle spielen.

[Xardas2]

Was mir gerade noch einfällt, bei einem Array muss der benötigte Speichrplatz an einem Stück vorhanden sein. Dies kann bei größeren Arrays problematisch sein, da der benötigte Speicherplatz wohl vorhanden ist, aber nicht zusammenhängend. Denn der Hauptspeicher ist im höchsten Maße fragmentiert.
Einer verketteten Liste ist dies jedoch egal, da sie ja immer auf den Anfang der nachfolgenden bzw. vorangegangenen Information verweist.

[Gast]

ich liebe es, wenn (fast ganz) neue leute sich passioniert zu fast 1 jahre alte beiträge hingeben *ernst*