C/C++ : Verkettete

[cleptomanicx]

Hallo,
Kann mir jemand Verkettete Listen erklären weil ich kapier nicht recht wofür man die braucht und wie dieses aussehen.

MFG

[bischi]

Warum man die braucht? Ganz einfach: Wenn du ein array machst, muss beim kompilieren feststehen, wieviele Einträge dieses hat. Willst du beliebig viele Einträge ermöglichen, so nimmst du eine verkettete Liste.

Wie eine Liste aussieht? Nimm ne Eisenbahn und stell dir vor, dass du immer weisst, wo die Lokomotive steht. Jetzt kannst du hinten beliebig Wagen anhängen und wegnehmen. Wenn du zusätzlich noch spezialmethoden hast (bspw. Kran :D), so kannst du auch Wagen aus der Mitte entfernen.

Lg Bischi

[cleptomanicx]

Hast du auch ein Beispiel wo man Verkettete Listen einsetzen könnte?
Und wie sieht sone Liste als Code aus?

[peschmae]

In Wikipedia hats z.B. Pseudocode: http://de.wikipedia.org/wiki/Verkettete_Liste
Aber eigentlich kannst du dir den ja auch gut selber ausdenken ;)

Ein Beispiel wo man die einsetzen könnte? Naja, eigentlich überall. Meiner Meinung fragst du die falsche Richtung rum; das was man im Normalfall macht ist fragen: Ich hab ein Problem, was könnte ich zur Lösung einsetzen?

Wenn du z.B. weisst dass du irgend eine Listenart benutzen wirst/willst, dann stellst du dir Fragen wie:
Welche Operationen soll die Liste unterstützen?
Welche Operationen führe ich oft aus?
Welche Operationen müssen effizient sein?
Und dann wählst du nach den Kriterien aus was am besten oder einigermassen gut passt.

MfG Peschmä

[BLUESCREEN3D]

ich kapier nicht recht wofür man die braucht
Verkettete Listen haben den Vorteil, dass man in konstanter Zeit O(1) an jeder beliebigen Stelle neue Elemente einfügen oder löschen (falls doppelt verkettet) kann.
Im Gegensatz dazu müsste man bei z.B. einem Array beim Hinzufügen oder Entfernen von Elementen jedes Mal ein neues Array anderer Größe erstellen und alle alten Elemente in das neue Array kopieren.
Dafür haben Listen allerdings den Nachteil, dass du nicht in konstanter Zeit auf ein Element an bestimmter Position zugreifen kannst. Element Nr. n zu finden dauert wieder lineare Zeit O(n). Das kann sich wiederum auf die für das Einfügen oder Löschen benötigte Zeit auswirken, da du die betroffenen Elemente vllt. erstmal mühselig finden musst.

Allgemein gilt, wie schon von peschmae gesagt, dass die verketteten Listen nur eine von vielen Datenstrukturen sind und wie jede Vorteile und Nachteile hat.
Je nach Anwendungsgebiet musst du dir passende Datenstruktur aussuchen und das ist eben in manchen Fällen eine verkettete Liste.

[jeebee]

Verkettete Listen haben den Vorteil, dass man in konstanter Zeit O(1) an jeder beliebigen Stelle neue Elemente einfügen oder löschen (falls doppelt verkettet) kann.

Das stimmt so aber nur falls du irgendwo ne Liste hast, mit der du auf alle Elemente in O(1) zugreifen kannst, allgemein hast du das bei einer verketteten Liste nicht und musst daher die Liste durchgehen bis du das Element findest, welches du löschen möchtest. (Dasselbe für die Position an der du einfügen willst), das Durchgehen kostet aber O(n) bei n Elementen (worst-case, average-case)

[BLUESCREEN3D]

(...) allgemein hast du das bei einer verketteten Liste nicht und musst daher die Liste durchgehen (...)
Habe ich doch zwei Absätze später auch geschrieben:

Dafür haben Listen allerdings den Nachteil, (...)

PS: Wenn man irgendwo noch eine Liste mit Zuordnungen hätte, dann würde das Einfügen wieder länger dauern, weil dieser Index geändert werden müsste :D

[peschmae]

Das stimmt so aber nur falls du irgendwo ne Liste hast, mit der du auf alle Elemente in O(1) zugreifen kannst, allgemein hast du das bei einer verketteten Liste nicht und musst daher die Liste durchgehen bis du das Element findest, welches du löschen möchtest.

Naja, du kannst auch einfach davon ausgehen dass du das Element schon "hast" wenn dus löschen willst. Element raussuchen gehört eigentlich nicht zwingend zu Element löschen. Kommt halt immer aufs Szenario an. ;)

MfG Peschmä, im allgemeinen kein grosser Fan von verketteten Listen

[jeebee]

Naja, du kannst auch einfach davon ausgehen dass du das Element schon "hast" wenn dus löschen willst. Element raussuchen gehört eigentlich nicht zwingend zu Element löschen. Kommt halt immer aufs Szenario an. ;)

Stimmt natürlich, aber für (sortiertes) Einfügen brauchst du trotzdem O(n) Zeit.

MfG jeebee (der Listen vor allem für Callback-Funktions-Argumente braucht und sie dort jeweils nur von hinten nach vorne füllt und von vorne nach hinten liest :) )

[panzi]

Stimmt natürlich, aber für (sortiertes) Einfügen brauchst du trotzdem O(n) Zeit.

MfG jeebee (der Listen vor allem für Callback-Funktions-Argumente braucht und sie dort jeweils nur von hinten nach vorne füllt und von vorne nach hinten liest :) )

Klingt nach einen Anwendungsfall für std::queue (http://www.sgi.com/tech/stl/queue.html).

[jeebee]

In C wohl eher nicht ;) Ich könnte natürlich auch GQueue anstatt GList nehmen, aber das umgekehrte Lesen und Schreiben dient eh nur der Performance!