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 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)

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 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 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.