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!

[hoika]

Hallo,

TList kopiert nicht um, wenn gelöscht wird,
sondern setzt die entsprechenden Stellen auf NIL.

Siehe Hilfe von Pack.


Heiko

[Gausi]

Das ändert nichts an meiner Aussage. Das Problem beim einfügen bleibt. (Und ja, ich weiß, was Capacity ist.)

Für eine Liste würde ich so vorgehen: Zuerst einmal von TObject eine Klasse TElement ableiten. TElement enthält zwei Zeiger auf TElement, dei man Next und Prev nennen könnte, da sie den Vorgänger/Nachfolger in der Liste speichern sollen.

Der Datentyp TDoppeltVerkettete Liste könnte so aussehen:

Je ein Zeiger auf TElement: First, Actual. Dann verschiedened Methoden: Insert, Delete zum Einfügen und Löschen, GetNext, GetPrev, GetFirst, GetLast zum Navigieren in der Liste und evtl. ein paar weitere (IsLast, IsFirst, IsEmpty, InsertAtEnd, InsertAtBeginning, etc.).
Ein Element wird an der aktuellen Stelle eingefügt, indem man die Zeiger Next und Prev des aktuellen Elements, dessen alten Nachfolgers/Vorgängers und des neuen Elements entsprechend setzt/umbiegt - einfach mal aufmalen, dann wird klar, wie man das machen muss. Beim Entfernen entsprechend verfahren.

Das kann man einmal implementieren und anschließend in seinen Programmen Klassen nicht mehr von TObject ableiten, sondern von TElement.

[Der_Unwissende]

[OT]

Zitat:

Zitat von Gausi

Das ändert nichts an meiner Aussage. Das Problem beim einfügen bleibt. (Und ja, ich weiß, was Capacity ist.)

Vorallem nichts daran, dass deine Aussage falsch ist. Eine Liste ist und bleibt ein Datentyp, der bestimmte Operationen anbietet, die Realisierung (und damit die Laufzeit) hat nichts mit der Liste zu tun (auch der Platzbedarf nicht). Kannst du gerne sehen wie du möchtest, aber warum siehst du es als quasi erwiesen an? Nach wessen Definition?

Was das einfügen in ein Array angeht, wie kommst du darauf dass das langsamm ist? Wenn ich ein Objekt erzeugen muss, dass Zeiger für links und rechts enthält, dann kostet mich das Zeit, das zuweisen der zwei Zeiger kostet wiederum Zeit, klar, nur konstant viel, aber wer sagt dir dass die Speicherverwaltung von Windows da schlechter arbeitet? Es ist ziemlich unabhängig von der Länge des Arrays, wie lange Windows braucht den Speicher zu allozieren und dir einen Zeiger drauf zu liefern. Auch das kopieren von Speicherblöcken ist extrem flink (und nicht linear)...
[/OT]

[marabu]

Hi folks,

ich leide beim Lesen dieses threads. Ihr diskutiert auf verschiedenen Ebenen.

Zuerst möchte ich auf die eigentliche Frage (siehe Titel des threads) antworten: eine "doppelt verkettete Liste" ist eine so elementare Struktur, dass es im Wesentlichen nur eine Art gibt sie zu implementieren.

Und jetzt noch ein wenig Begriffsbestimmung, damit der Schmerz nachlässt: Es wurde nicht nach einer modellhaften Listenimplementierung gefragt - TList wäre eine solche. Natürlich ist die Liste ein abstrakter Datentyp (endliche geordnete Menge von Items), wobei erstmal zwischen linearen Listen und Listenstrukturen zu unterscheiden ist, je nachdem ob ein Item wieder eine Liste sein kann.

Listen unterscheiden sich dann noch durch bestimmte Merkmale ihrer Graphen-Repräsentation (pure, reentrant, cyclic).

Dann gibt es noch die Speicher-Repräsentation - sequentiell oder verkettet - und daran reibt ihr euch hier unnötigerweise. Standish (Data Structure Techniques) spricht von sequential allocation, wenn die Items einer Liste als gepackter Vektor (Array) gespeichert werden.

Zitat:

TList ist keine Liste, sondern ein Array

TList ist eine sequentielle Listen-Implementierung. Ist aber in diesem thread eigentlich egal, weil sowieso am Thema vorbei, denn Eyck sucht ja nach einer Basis-Implementierung für eine "verkettete Liste" und nicht nach einer Alternative. Allerdings macht mich sein Anspringen auf TList in Beitrag #4 stutzig. Vielleicht sollte er sich nochmal in seinem thread melden um aufzuklären ob es ihm nur um das Prinzip geht oder ob er nach einer beliebigen effizienten Implementierung sucht.

Freundliche Grüße vom marabu

[EccoBravo]

Ja Hallo Marabu und Kollegen,

die Frage, was ich einfach suche:
Es ist mir wirklich egal, was für eine Struktur es dann letztlich wird.
Ich will nur 3 Dinge:

1. Ich will Listen oder Objekte (auch verschachtelte hirarchisch strukturierte Listen oder 2D-Felder für Objekte) beliebiger (vorher unbekannter) Länge.

2. Diese Listen sollen sich leicht handeln lassen, (in Parameterlisten zwischen functions.. und Units), leicht sortierbar, änderbar, Suche nach Vorkommen...

3. Die Operatoren der Listen/Felder (wie add delete, search, sort...) will ich nur einmal implementieren und diese Implementierung en sollen leiche veränderbar/erweiterbar sein.

Daher will ich mich nicht unbedingt auf doppelt verkettete Listen festlegen.

Wenn Ihr mir die Vor- und Nachteile von verketteten Listen bzw. Arrays diesbezüglich nennen könnt, wie gesagt, ich bin für beide Sachen offen, es muß sich nur gut handeln lassen.

Vielen Dank

E. B.

[marabu]

Dann schau dir TList genau an und vergiss doppelt verkettete Listen. Deinen Anwendungsdatentyp kannst du direkt auf TList aufsetzen und sparst dir jede Menge Arbeit.

Freundliche Grüße

[negaH]

Jetzt hackt nicht auf Gausi rum, er hat aus meiner Sicht die richtigen Argumente vorgebracht.

Zb.

Zitat:

TList kopiert nicht um, wenn gelöscht wird,
sondern setzt die entsprechenden Stellen auf NIL.

Gausi hat aber denoch recht. TListe kopiert immer um wenn man einen Array Eintrag aus dem Array LÖSCHT, nicht auf NIL setzt.

Also

Array[3] = (Object1, Object2, Object3)

Lösche Eintrag Object2

Array[2] = (Object1, Object3)

Bei TList MUSS hier umkopiert werden, und obige Operation IST die Löschoperation -> .Delete()

Bei "echten" Listen im Sinne der Informatik handelt es sich immer um irgendeine Form von Zeigerobjekten, also Listen die sich bilden wenn man Objekte über Zeiger untereinander Verkettet. Man redet deshalb auch gerne von Ketten oder Chains da das wohl nicht so irritierende Wörter sind wie "Liste".

Chains/Ketten/verlinkte Listen haben eben den entscheidenden Vorteil das sie keinerlei Speicher-umkopier-operationen bei den Einfüge/Entfernen Opertionen benötigen. Dafür benötigen sie

- mehr Speicher für ihre Verwaltungtsstrukturen -> Zeiger -> besonders bei verlinkten Listen mit mehr als einer Verlinkung (sprich einfach verkettete Listen sind identisch zu Array Listen im Speicherverbrauch, alles was drüber ist ist ineffizienter im Speicherverbrauch)

- mehr Aufwand beim Umsortieren und Suchen in der Liste, dh. die Algorithmen zur Suche in Array-Listen (QuickFind, QuickSort etc.pp) sind im Vergleich zu deren Counterparts für verlinkte Listen viel einfacher und effizienter.

- der Aufwand den also verlinkte Listen mitsich bringen lohnt sich in den meisten Fällen nicht. Nur wenige, ganz spezielle Aufgaben wie Stacks, FIFO, FILO Buffer etc.pp. sind mit verlinkten Listen effizienter.

In den meisten Fällen benötigt man an eine Array Liste auf Irgendwas, die man

1.) einmalig füllt
2.) danach sortiert
3.) dann ständig quasi tot im Speicher hält und nur lesend darauf zugreift
4.) von Zeit zu Zeit mal was einfügt oder löscht
5.) alles wieder freigibt

In solchen Szenarien lohnen verlinkte Listen nicht, und das ist das was wir am häufigsten benötigen. Ergo: es gibt keine VCL im Delphi für verlinkte Listen.

Ein weiterer Punkt ist das ein Array[] eine quasi Informationstheoretisch Feste Struktur ist. Arrays sind also in jeder Programmiersprache sehr gleich. Verlinkte Listen dagegen sind nur von ihrer Wirkungsweise identisch aber fast niemals von ihrer realen Implementierung. Denn exakt diese Implementierungsunterschiede machen verlinkte Listen erst effizient im Vergleich zu anderen Verfahren.

Fazit: ein generisches VCL Object für verlinkte Listen macht garkeinen Sinn, da auf Grund der sehr unterschiedlichen Aufgabenstellungen an solche Listen eine solche Basis Klasse immer zu ineffizient auf das zu lösende Problem wäre.

Denoch: verlinkte Listen sind aus Sicht der Informatik nur eine "Untergruppe" von anderen Algorithmen den "Bäumen" bzw. Trees. Aus Sicht dieser Definition sind verlinkte Liste quasi degenerierte und nicht balanzierte Bäume. Solche Bäume lösen aber ganz andere Aufgaben/Probleme die so nicht mher 1 zu 1 mit Array Listen verglichen werden können. Auf diese Probleme bezogen wären die Bäöume/verlinkten Listen wiederum effizienter, auch in den Operationen der Suche/Sortierungen/Indizierungen !

Gruß Hagen