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

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