Nochmal verkettete Listen

[aps]

Moin,

ich bin es noch gewohnt, mit doppelt verketteten Listen zu arbeiten, die so aussehen:

Delphi-Quellcode:

type
  PData = ^TData;
  TData = class
    next : PData;
    prev : PData;
    datum: integer;
  end;

Soweit ich das verstanden habe, soll man so nicht mehr arbeiten. Als Alternative las ich irgendwo, dass man das jetzt auch so implementieren dürfe:

Delphi-Quellcode:

type
  TData = class
    next : TData;
    prev : TData;
    datum: integer;
  end;

Ist das so korrekt? Und dann funktioniert auch

Delphi-Quellcode:

var a,b : TData;
begin
  a := TData.create;
  b := TData.create;
  a.next := b;
  b.prev := a;
end;

?

D. h. a, b, a.next und b.prev werden intern auch nur als Zeiger gespeichert, wobei a und b.prev sowie b und a.next auf jeweils identische Speicherbereiche zeigen?

Hintergrund: Ich entwickle zurzeit ein neues Projekt, welches zwar zunächst Win32 kompiliert werden soll, später soll aber ohne große Änderungen auch eine Konvertierung nach .NET möglich sein.

TIA!

[alzaimar]

Ich würde auf stinknormale Listen zurückgreifen. wieso verwendest Du keine TList? Oder eine TStringList?
Eine TStringlist (Sorted = True) hätte den Vorteil, relativ schnell danach suchen zu können. Die 'Nutzdaten' packst Du in die Objects[i].

[aps]

Zitat:

Zitat von alzaimar

wieso verwendest Du keine TList? Oder eine TStringList?

Weil die für komplexe Klassen ziemlich ungeeignet sind, genauso wie Arrays. Ich war davon ausgegangen, dass die Leserschaft hier in der Lage ist, aus vereinfachten Beispielen, wie ich sie anbrachte, zu abstrahieren, dass da mehr hinterstecken könnte.

Gemäß meinen Tests ist meine Aussage im OP wahr, aber ich wäre glücklich, wenn mir das jemand (mit Erfahrung) bestätigen könnte.

[jfheins]

Und wie wäre es mit einer TObjectList (evtl. + Template) :?: :stupid:

Und ja, es müsste alles so funktionieren, wie du es dir vorstelltst, aber OOP ist das imho nicht ;)

[Robert_G]

Dein Ansatz ist schon richtig. ;)
Eine KnotenKlasse mit Vorgänger, Nachfolger und einem Zeiger auf das eientliche Item (Irgendeinem TObject-Nachfahre).
Drumrum noch eine Klasse die dir Head, Tail, Add, Remove, Insert, Count,.... bereitstellt und das war's auch schon. ;)

[alzaimar]

@aps: Ja, das sind Zeiger. Ich verstehe nicht, wieso Listen etc. für komplexe Klassen ungeignet sind, wo doch sowieso nur der Pointer in der Liste gespeichert wird. Dann können die Klassen auch so komplex wie das Abstraktionsvermögen der Leserschaft hier sein (wo immer du das ansiedelst).

Wenn Du mit sowas Banalem wie verkettenen Listen ankommst, um Fragen nach Klassenzeigern zu stellen, kann man, auch mit so wenig Erfahrung wie ich, schon denken, das Du etwas mit linked lists machen willst.

Du meinst also, Meinungen von Teilnehmern ohne Erfahrung interessieren Dich nicht? Wenn ich ein Klasse mit ein paar Feldern erstelle und eine Instanz dieser Klasse hat (gemessen mit SizeOf) eine Größe von 4 Bytes, dann riecht das nach einem Pointer. Das muss ich nicht verifizieren, und wenn, reicht ein Anfänger.
Bei deiner nächsten Frage würde ich die Kandidaten, die dir Anworten dürfen, nicht von vorneherein einschränken, weil es durchaus sein kann, das sich keiner zutraut, dir das Wasser reichen zu können.

[Hansa]

Zitat:

Zitat von alzaimar

..Die 'Nutzdaten' packst Du in die Objects[i].

Das wurde wohl übersehen ? Glaube, das steht ab TStrings zur Verfügung ! Bei .NET ist übrigens das @ verpönt und nicht das ^.

[aps]

Allen ersteinmal Danke für die Antworten/die Hilfe!

Zitat:

Zitat von jfheins

Und ja, es müsste alles so funktionieren, wie du es dir vorstelltst, aber OOP ist das imho nicht

Warum meinst du, dass das kein OOP ist, und wie könnte man es besser machen? Vorschläge gern willkommen!

@alzaimar: Sorry, ich wollte weder jemandem zu Nahe treten, noch und erst recht nicht beleidigen. Vielmehr war der betreffende Satz in #2 als ein Ausdruck des Bedauerns meiner eigenen Unfähigkeit bedacht, es kenntlich zu machen, dass es sich um komplexere Strukturen handelt.
Zur Begründung, weshalb ich Arrays hier in diesem Fall für nicht geeignet halte: (Dynamische) Arrays, die sich häufig in der Länge ändern, sind relativ langsam. Und genau dieses wird in dem geplanten Projekt relativ häufig vorkommen.

[DerDan]

Hallo


ich habe auch schon verschiedene Tests mit dynamischen Arrays gemacht und für mich fetsgestellt, das die nur dann recht schnell sind, wenn man die Länge nicht jedemal um 1 (eins) erhöht wenn ein Element dazukommt sondern eher mal um 1024. Man mus dan halt seperat einen Zähler haben der Anzeigt wieviele Element gültige Einträge haben.

So ähnlich sind auch die Listen (TList, TObjectList) in Delphi implementiert. Dort wird das dahinterliegende Array auch in Stufen vergößert / verkleinert. Dort kann man mit Capacity setzen wieviele Elemente hineinpassen sollen.

DerDan

[barf00s]

Zitat:

Soweit ich das verstanden habe, soll man so nicht mehr arbeiten.

Wer sagt das?
Das doch absoluter Käse.

[alcaeus]

Zitat:

Zitat von DerDan

für mich fetsgestellt, das die nur dann recht schnell sind, wenn man die Länge nicht jedemal um 1 (eins) erhöht wenn ein Element dazukommt sondern eher mal um 1024.

Robert_G hats hier gesagt: Man soll die Liste gleich auf 172% der Groesse vergroessern.

@aps: Wenn du nicht mit Casts usw. arbeiten willst, kannst du dir ja mal mein Objectlist-Template ansehn. Wenn du dann noch ein bisschen mit dem Enum rumspielst, kannst du auch ohne Probleme "rueckwaerts" durch die Liste gehn bzw. dir auch das vorherige oder das naechste Element anzeigen lassen, ohne lang die Pointer im Listenitem speichern zu muessen ;)

@barf00s: Dann sag doch warum es Kaese ist, wenn du schon so davon ueberzeugt bist. :roll:

Greetz
alcaeus

[alzaimar]

Wenn eine Liste gesucht wird, die in allen Punkten schnell arbeitet, in er man Vorwärts/Rückwärts laufen kann, und das Suchen/Einfügen/Löschen jeweils in (so gut wie) O(1) von statten geht, würde ich Skiplists nehmen und die gibt es hier:
http://www.delphipraxis.net/internal...ct.php?t=53649

Wie eine Datenstruktur baut (hier: Hash-Tabellen), und eine dynamische Liste effektiv verwenden kann, steht hier:
http://www.delphipraxis.net/internal...ct.php?t=53653

Die Hashtabellen sind beim Suchen/Einfpügen/Löschen unerreicht schnell, dafür ist das Traversieren (also sukkessive Durchlaufen) nicht so schön, zumal die Elemente nicht soriert erscheinen.

[aps]

Zitat:

Zitat von barf00s

Zitat:

Soweit ich das verstanden habe, soll man so nicht mehr arbeiten.

Wer sagt das?
Das doch absoluter Käse.

Das sagen zumindest Microsoft und Borland. Alles, was mit ^. angesprochen wird, ist "unsicherer Code", der nicht für .NET-Projekte verwendet werden soll:

Zitat:

Zitat von Delphi 2005 Hilfe

Unsafe-Code: '%s' (W1047)

Sie haben einen Datentyp verwendet oder einen Vorgang ausgeführt, der möglicherweise Speicher überschreibt. In einer gesicherten Ausführungsumgebung wie beispielsweise .NET wird solcher Code als unsicher und potentiell gefährlich betrachtet.