Gibt es ein Modell für "Doppelt verkettete Listen" ?

[EccoBravo]

Hallo,

meine Fragerei geht weiter.
Es geht um die Kapselung oder Verallgemeinerung der Algoritmen
zur Erzeugung, dem Aufbau doppelt verketteter Listen oder zum Bewegen in diesen Listen.


Mein Wunsch ist es, irgend wo nur einmal "abstrakt" den Algoritmus für das Anhängen neuer Listenglieder, das Einfügen oder Löschen von Listengliedern, das Sortieren von Listen und das Vor- oder Zurückwandern in einer Liste zu schreiben.

Ich will im laufenden Programm nicht für jede Liste diesen Algoritmus neu schreiben.
Für jede Liste meiner Programme will ich einen vorhandenen Algoritmus mit nutzen.
Damit will ich Code und Pflegeaufwand sparen.


Irgendwie riecht mir dieses wie ein Strategy-Muster
aber ich weiß nicht wie das gehen soll.

[mkinzler]

Kannt du doch per Ableitung machen.
Schau dir mal TList und deren Ableitungen an.

[Der_Unwissende]

Hi,
den einen Weg gibt es nicht. Das liegt aber einfach daran, dass du eine Liste implementieren kannst wie du möchtest. Arbeitest du auf Arrays (der übliche Weg), dann heißt das Vorwärtsbewegen etwas anderes, als wenn du hier Records oder Klassen mit Veweisen auf die Nachbarn hast. Der eine Weg ist dabei effizienter, der andere Platzsparender.

Aber wenn ich dich richtig verstanden habe, dann reicht es, wenn du mit einer abstrakten Klasse, einer konkreten Implementierung (oder auch beliebig vielen) und zu guter Letzt noch einen Wrapper für spezielle Datentypen arbeitest.

An sich kannst du eigentlich sogar den Datentyp TList von Delphi verwenden, verwendest du nur Objekte, dann natürlich auch TObjectList. Hier gibt es bereits Funktionen zum hinzufügen oder entfernen von Elementen. Allerdings speichert eine TList einfach nur Zeiger, ganz untypisiert. Das heißt, wenn du etwas reinpackst, musst du es beim rausnehmen wieder casten (sonst hast du nur einen normalen Zeiger). Dazu kannst du dann für jede der Klassen einen Wrapper schreiben. Noch komfortabler geht das ganze mit Generics, die werden aber von Delphi nicht wirklich unterstützt (gab da glaube ich einen Weg, der aber auch nicht so richtig elegant ist).

Jedenfalls kannst du einfach eine Klasse von TList ableiten und in dieser Klasse dann deine eigenen Funktionen einfügen (add, remove, first, last,..). Bei Hinzufügen lässt du dann ebend nur typisierte Zeiger zu. Den Parameter speicherst du dann einfach in der TList, beim rausnehmen gehst du analog vor und castest das entfernte Element einfach in diesen typisierten Zeiger.

Alternativ kannst du auch sowas verwenden:

Delphi-Quellcode:

type
  TClassType = TObject;

  TMyList = class(TObject)
    private
      FList : TObjectList;
    public
      procedure add(const Element : TClassType);
      function getFirst : TClassType;
      function getLast : TClassType;
      function remove(const index : Integer) : TClassType;
  end;

Ist nicht schön, aber du kannst einfach für jede Liste die komplette Unit kopieren und dann halt TClassType immer entsprechend anpassen. Das Speichern kann weiterhin eine TObjectList (oder irgendwas anderes) übernehmen, das was du rausholst castet du dann einfach in den Typ TClassType (der immer dem Typ der Liste entspricht).

Gruß Der Unwissende

[EccoBravo]

Seid mir nicht böse, aber jetzt bin ich ganz blöd:

Wo und wie finde ich TList?

Danke
E. B.

[Gausi]

TList ist keine Liste, sondern ein Array.

Afaik gibt es in Delphi von Haus aus keinen Datentyp, der dem einer Liste im Sinne der Informatik entspricht - da hilft nur selber programmieren.

[Der_Unwissende]

Zitat:

Zitat von Gausi

TList ist keine Liste, sondern ein Array.

Afaik gibt es in Delphi von Haus aus keinen Datentyp, der dem einer Liste im Sinne der Informatik entspricht - da hilft nur selber programmieren.

Sorry, aber das ist so falsch. Die Liste in der Informatik ist nur ein abstrakter Datentyp (das ist gerade der Sinn), die eigentliche Umsetzung bleibt dem Programmierer überlassen. Eine Liste ist eine Datenstruktur, in die man etwas einfügen kann, die ihre Größe dyn. anpasst, dass tut kein Array. Natürlich wird bei der TList intern ein Array verwaltet, aber das wiederspricht nicht der Idee der Liste!

TList wird in der Unit Classes deklariert.

[mkinzler]

Man makk sich aber leicht eine flexible Listenklasse, welche als doppelt-verkettete Liste implemnetiert ist erzeugen, in dem man die Litenstruktur vom verwendeten Typ trenne. also in der liste nur Zeiger/Referenzen auf die eigentlichen Elemente stehen.

[Der_Unwissende]

Zitat:

Zitat von mkinzler

Man makk sich aber leicht eine flexible Listenklasse, welche als doppelt-verkettete Liste implemnetiert ist erzeugen, in dem man die Litenstruktur vom verwendeten Typ trenne. also in der liste nur Zeiger/Referenzen auf die eigentlichen Elemente stehen.

Ja, aber man kann auch einfach einen Wrapper um die TList erstellen, sich in einer Variable die aktuelle Position merken und next und previous sind dann nur Operationen auf dem Array hinter TList (also wirklich der Wahlfreie Zugriff mit dem Index).
Auch hier ist der Datentyp wieder abstrakt. Das sieht man schon daran, dass man Zeiger und Records verwenden kann oder Objekte mit Referenzen.

[mkinzler]

Mein Vorschlag war ja nur für den fall, daß er er unbedingt verkettete Listen haben will. Ich würde auch auf Tlist aufsetzen, wie ich schon unter #2 vorschlug.

[Gausi]

In einer Liste kann man sehr schnell einfügen und löschen. Nämlich in konstanter Zeit, ganz egal, wie lang die Liste ist. Dafür benötigt man Objekte, die Zeiger auf das nächste (und vorige) Element in dieser Liste speichern können.
Da TList als Array implementiert ist, ist diese Eigenschaft da nicht gegeben. Wenn die TList voll ist, und man ein neues Objekt einfügen möchte, muss man komplett umkopieren. Ebenso muss komplett umkopiert werden, wenn man das erste Element entfernen möchte. Man muss zwar nicht die Objekte umkopieren, aber alle Zeiger. Vom Aufwand her ist das prinzipiell egal.
Bei einer echten Liste müssen beim Löschen/Einfügen immer nur ein paar Zeiger umgehangen werden.

Wenn es also darum geht, die Datenstruktur "Liste" zu implementieren, dann sollte man nicht von TList ausgehen. Array und Liste sind zwei völlig unterschiedliche Strukturen!