verkettete Listen

[Gerkey]

Suche ein einfaches vollständiges Beispielprogramm (Delphi Seattle) für verkettete Listen.
Kann mir da jemand helfen ?

[Neutral General]

Versuch es selbst und schau dir den Wikipedia Artikel oder so dazu an.
Verkettete Listen sind echt nicht schwer ;)

Wenn du nicht weiterkommst, sag Bescheid woran es hängt und wir helfen dann.

[Ghostwalker]

Zwar kein Beispielcode aber ein Tutorial zum Thema:

Zeiger & Zeigerketten

[Neutral General]

--- Bitte ignorieren (oder löschen) ---

[KodeZwerg]

Zitat:

Die Domain moonraven.kilu.de ist noch frei!

Existieren die PDFs noch wo anders?

[Neutral General]

Zitat:

Zitat von KodeZwerg (Beitrag 1399695)

Zitat:

Die Domain moonraven.kilu.de ist noch frei!

Existieren die PDFs noch wo anders?

Genau sowas stand in meinem Post oben den ich wegeditiert hab, bis ich gemerkt hab, dass im Thread eine Zip mit dem PDF angehangen ist ;)

[KodeZwerg]

Ohhh mein Fehler! Ich hatte das Zip nicht geladen weil ich dacht das da Sourcecode drinnen ist.
Ich nehm alles zurück, alles ist da wie es sein sollte, tut mir leid für spamm!

[Dennis07]

...oder man schaut sich einfach an, wie es andere machen. Es gibt tausende Beispiele.
zB die DeHL.Collections.LinkedList.pas von der DeHL: https://github.com/pavkam/DeHL/blob/...LinkedList.pas

Oder die ReferenceData-Typen der Lina Components Library: https://bitbucket.org/Dennis07/lina-...ysTools.pas-87

Sinn machen verkettete Listen aber nur in den wenigsten Fällen. Es ist meistens nur zum Üben sinnvoll. Siehe hier.

[p80286]

Gut zu lesen, was sinnvoll ist.

Bisher neigte ich eher zu dieser Auffassung:

Zitat:

Zitat von stoxx (Beitrag 925444)

Zitat:

und nein, mir fällt gerade kein einfaches _und_ praktisches Beispiel für Zeigerlisten ein, welches man im Tutorial verwenden könnte)

man braucht sie nicht oft, aber wenn, dann sind sie sehr effektiv.

Als dynamischer Datenbuffer sind sie sehr gut geeignet. Du möchtest hinten in einer Liste etwas anhängen, und manchmal vorn etwas rausnehmen.
Alle array basierten Lösungen wie TList zb. haben nun das Problem, dass diese ja immer zusammenhängenden Speicher benötigen.
Beim löschen oder einfügen eines Elementes an erste Stelle wird das komplette Pointerarray nach vorn oder hinten geschoben. und das ist lahm, wie man so schön sagt :-)

Gruß
K-H

[Ghostwalker]

Zitat:

Zitat von Dennis07 (Beitrag 1399733)

Sinn machen verkettete Listen aber nur in den wenigsten Fällen. Es ist meistens nur zum Üben sinnvoll. Siehe hier.

Da muss ich Einspruch erheben.

1. Vergleicht er das ganze mit seiner Implementierung einer Zeigerkette. Ich weißt nicht was er da gebaut hat,
aber der Overhead bei einer Zeigerkette dürfte um einiges weniger sein, als bei TList.

a) TList ist eine Klasse. D.h. ich hab die ganze Verwaltung eines Objektes dahinter.
b) TList basiert auf einem Array. Wie p80286 schon anführte, gibts da einige Nachteile.

2. Komplexere Datenstrukturen (z.B. Baumstrukturen) kommst du mit einer TList nicht weiter.

Das beste Beispiel für Verkette Listen, das mir bekannt ist, dürfte der VirtualTree (VirtualStringTree) sein. TList hat seine Stärke, wenn ich eine einfache (sprich 1.Dimensional) List von Daten brauche. Sobalds komplexer wird, ist eine richtig angewandte verkette Liste weit effizienter.

[TigerLilly]

<offtopic>Vielleicht wäre es klüger, das Anliegen des TE zu berücksichtigen, als den Thread zu kapern + persönliche Vorlieben kundzutun.</offtopic>

http://www.pascal-programming.info/a...inkedlists.php
http://mc-computing.com/Languages/De...nkedLists.html

[Ghostwalker]

[QUOTE=TigerLilly;1399765]<offtopic>Vielleicht wäre es klüger, das Anliegen des TE zu berücksichtigen, als den Thread zu kapern + persönliche Vorlieben kundzutun.</offtopic>
:gruebel::wiejetzt:

[Gerkey]

Hab's ja selbst versucht mit folgendem Beispiel aus (Hanser Verlag) Borland Delphi 7 Beispiel von Seite 728:
type
PKnoten = ^TKnoten;
TKNoten = record;
Nr : Integer;
Inhalt : String;
Next: PKnoten;
end;

private
public
end;
...

Nach Start kommt folgende Fehlermeldung: Feld M.Inhalt besitzt keine entsprechende Komponente ! Soll die Deklaration entfernt werden ?
Wo liegt der Haken ?

[HolgerX]

Hmm..

Zitat:

Zitat von Gerkey (Beitrag 1399774)

Delphi-Quellcode:

type
  PKnoten = ^TKnoten;
  TKNoten = record;
    Nr : Integer;
    Inhalt : String;
    Next: PKnoten;
  end;

private
public
end;
...

Könnte dies an dem Tippfehler liegen : TKNoten = record;
Hier ist ein ';' zu viel

[p80286]

Zitat:

Zitat von Gerkey (Beitrag 1399774)

Nach Start kommt folgende Fehlermeldung: Feld M.Inhalt besitzt keine entsprechende Komponente ! Soll die Deklaration entfernt werden ?
Wo liegt der Haken ?

Woher kommt

Delphi-Quellcode:

M.Inhalt

?
Zeig doch mal den vollständigen Code.

Gruß
K-H

[Codehunter]

Also ich arbeite recht oft mit verketteten Listen, wobei ich das eher verkettete Zeiger nennen würde. Das kommt in der Tat duch VirtualTreeView. Dort kann man, wenn man die Funktionsweise erst einmal kapiert hat, Baumstrukturen mit einer Million Knoten in Sekundenbruchteilen aufbauen. Mach das mal mit einem TTreeView 8-)

Aber auch die nachgelagerten Daten verkette ich ganz gerne über Zeiger auf Records. So kann ich die selben Daten in mehreren Bäumen bzw. Grids verwenden. Mein Projekt FMC macht das beispielsweise.

[p80286]

[OT]

Zitat:

Zitat von Codehunter (Beitrag 1399780)

So kann ich die selben Daten in mehreren Bäumen bzw. Grids verwenden.

Auch wenn das etwas fortgeschritten ist, kannst Du mal ein Beispiel posten?
[/OT]

Gruß
K-H

[Codehunter]

Zitat:

Zitat von p80286 (Beitrag 1399788)

Auch wenn das etwas fortgeschritten ist, kannst Du mal ein Beispiel posten?

Was genau willst denn wissen? Die Verkettung als solches ist ja einfach (Pointer-Element im Record, z.B. "ParentNode", "FirstChild", "NextSibling" - geht also über die Implementierung in TVirtualNode hinaus), die Verwendung von einmal reserviertem Speicher in mehreren VirtualTrees ist dann fallspezifisch. Beim oben erwähnten Projekt FMC sind die einzelnen Radiostationen eigentlich Childnodes im linken Tree. Dort werden sie jedoch ausgeblendet und stattdessen im rechten Grid, was ja auch ein verkappter VirtualTree ist, angezeigt.

[Stevie]

Newsflash: Performance of Array vs. Linked-List on Modern Computers

[Codehunter]

Zitat:

Zitat von Stevie (Beitrag 1399809)

Newsflash: Performance of Array vs. Linked-List on Modern Computers

Wie schon gesagt, das ist immer fallspezifisch. Ich wüsste keine sinnvolle Methode, hierarchische Strukturen in einem Array abzubilden ohne genau das künstlich zu erzeugen, was man eigentlich dadurch vermeiden will: Wildes Gespringe im Speicher. Obendrein hast du bei Arrays nur sehr starre Strukturen. Willst da mittendrin ein Element einfügen, verschiebst du den halben Ozean um einen Eimer Wasser einzufügen ^^

[p80286]

Zitat:

Zitat von Codehunter (Beitrag 1399799)

Zitat:

Zitat von p80286 (Beitrag 1399788)

Auch wenn das etwas fortgeschritten ist, kannst Du mal ein Beispiel posten?

Was genau willst denn wissen?

Erst einmal vollkommen ohne Virtualxxxx. Dein (?) Ansatz ist ja eine Pointer-Verküpfung (und eine zweite und eine dritte...) in der in jedem Eintrag (Node?) ein pointer auf Daten enthalten ist. Aber wie sind die Daten organisiert? Einfach verpointerte Liste oder Array oder ? Oder liegen die wild im Speicher herum und wenn die Organisationslisten weg sind hast du Datenzombies?

Gruß
K-H

[Namenloser]

Zitat:

Zitat von Stevie (Beitrag 1399809)

Newsflash: Performance of Array vs. Linked-List on Modern Computers

Die gehen aber offensichtlich davon aus, dass man das Element erst noch suchen muss. Das ist ein bisschen unfair der verketteten Liste gegenüber. Denn an sich geht das Einfügen oder Löschen eines Elements in einer verketteten Liste – wenn man den Pointer schon hat – in konstanter Zeit, weil man ja nur zwei Pointer umbiegen muss. Beim Array dagegen muss man immer alle Elemente nach dem gelöschten bzw. eingefügten Element umkopieren, was mit der Anzahl der Elemente linear ansteigt. Gerade da spielt die verkettete Liste ja ihre Stärke aus. Das ist normalerweise genau der Grund, warum man sich für eine verkettete Liste entscheidet.

Bei sehr kleinen Listen (so in der Größenordnung <100 Elemente) ist allerdings das Array oft trotzdem schneller. Es kommt natürlich auch immer darauf an, ob man mehr liest oder mehr schreibt. Wenn man fast nur liest, dann kann das Array auch bei größeren Listen Sinn machen.

[Codehunter]

Zitat:

Zitat von p80286 (Beitrag 1399878)

Zitat:

Zitat von Codehunter (Beitrag 1399799)

Zitat:

Zitat von p80286 (Beitrag 1399788)

Auch wenn das etwas fortgeschritten ist, kannst Du mal ein Beispiel posten?

Was genau willst denn wissen?

Erst einmal vollkommen ohne Virtualxxxx. Dein (?) Ansatz ist ja eine Pointer-Verküpfung (und eine zweite und eine dritte...) in der in jedem Eintrag (Node?) ein pointer auf Daten enthalten ist. Aber wie sind die Daten organisiert? Einfach verpointerte Liste oder Array oder ? Oder liegen die wild im Speicher herum und wenn die Organisationslisten weg sind hast du Datenzombies?

Im Wesentlichen packe ich die Nutzdaten als Payload gleich mit in den Record. Der Record wird mit New() und Dispose() bzw. Initialize() und Finalize() erstellt und zerstört. Seit man Records auch noch Prozeduren anfügen kann, implementiere ich die ganze Verknüpfungslogik direkt im Record. Wenn man es richtig anstellt, stupst man nur das Rootelement an und das Ganze schreibt sich z.B. selbst in einen Stream zwecks Sicherung auf Festspeicher.

Willst du mittendrin ein Element löschen, dann lässt du dieses Element alle Verweise auf sich selbst in anderen Elementen auf das jeweils nächste Nachbarelement ändern. Das geht, wenn jedes Element seine Nachbarn "persönlich" kennt.

Du könntest wenn du viel Wert auf Integrität legst, einen Zeiger auf jeden Record in eine TList schreiben, um sie dann in einem Destructor abzuarbeiten und freizugeben. Aktiv arbeiten würde ich aber mit der TList nicht.

[p80286]

Ah so, vielen Dank!
das halte ich mal im Hinterkopf

Gruß
K-H

[Zacherl]

Zitat:

Zitat von Namenloser (Beitrag 1399889)

Zitat:

Zitat von Stevie (Beitrag 1399809)

Newsflash: Performance of Array vs. Linked-List on Modern Computers

Die gehen aber offensichtlich davon aus, dass man das Element erst noch suchen muss. Das ist ein bisschen unfair der verketteten Liste gegenüber. Denn an sich geht das Einfügen oder Löschen eines Elements in einer verketteten Liste – wenn man den Pointer schon hat – in konstanter Zeit, weil man ja nur zwei Pointer umbiegen muss. Beim Array dagegen muss man immer alle Elemente nach dem gelöschten bzw. eingefügten Element umkopieren, was mit der Anzahl der Elemente linear ansteigt. Gerade da spielt die verkettete Liste ja ihre Stärke aus. Das ist normalerweise genau der Grund, warum man sich für eine verkettete Liste entscheidet.

Das häufige Anfordern und Freigeben von vielen kleinen Speicherblöcken kann durchaus langsamer sein, als die einmalige Anforderung eines einzelnen (oder wenigen) großen Blocks.

Delphi-Quellcode:

std::vector

over-allocated z.B. anhand bestimmter Growth-Faktoren. Bei einer linked-list wäre das nur möglich, wenn man alle Nodes im selben Speicher hält, wofür man dann aber wiederrum z.B. ein extra Bitmap benötigt, um die freien Bereiche zu Tracken (habe ich deshalb noch in kaum bzw. sogar in keiner Implementation gesehen). Kann also schon sein, dass das Verschieben des Speichers performanter ist. Denke das muss man alles individuell auf den Anwendungsfall bezogen testen.