Marco D. - Mi 12.07.06 14:59
Titel: Vorteile der verketteten Liste

---

Hab schon oft gesucht, aber noch nie eine richtige präzise Antwort bekommen. Was sind denn nun genau die Vorteile einer verketteten Liste gegenüber einer Stringlist und einem dynamischen Array? Und die Nachteile?

Gausi - Mi 12.07.06 15:08

---

Der Vorteil bei einer verketteten Liste ist ganz klar die Performanz der Einfügeoperation. Wenn man an einer bestimmten Stelle in der Liste etwas einfügen möchte, muss man nur ein paar Zeiger verbiegen. Bei einem Array muss man alle nachfolgenden Einträge verschieben.

Der Nachteil bei (sortierten) Listen gegenüber (sortierten) Arrays ist eine schlechte Suchperformanz. Da eine Liste keine Möglichkeit bietet, zum x-ten Element zu springen, muss man immer die komplette Liste durchgehen. Bei einem Array kann man z.B. Binärsuche anwenden.
Es gibt zwar auch Listen, die nicht nur den Nachfolger und Vorgänger speichern, sondern noch mehr (eben die Sprungstellen für die Binärsuche), aber die erkaufen die Laufzeit durch (leicht) erhöhten Speicherplatzbedarf.

So gesehen macht es einen gewissen Sinn, Listen zu verwenden, wenn man oft Daten hinzufügt, und Arrays, wenn man öfter suchen muss.

Marco D. - Mi 12.07.06 15:11

---

Gausi hat folgendes geschrieben:

So gesehen macht es einen gewissen Sinn, Listen zu verwenden, wenn man oft Daten hinzufügt, und Arrays, wenn man öfter suchen muss.

Und wenn man oft Daten hinzufügt und öfter suchen muss? :mrgreen: Macht es Sinn, eine Klasse für verkettete Listen zu schreiben?

crowley - Mi 12.07.06 15:24

---

ja... es ist in jedem fall sinnvoll, eine klasse für so eine verkettete liste zu schreiben ;)

ich habe irgendwann mal eine art virtuelles Grid entwickelt, dass eine Protokolldatei mit beliebigen Spalten/Messwerten im Speicher abbildet...

es war quasi eine zweidimensionale Liste... dabei habe ich stets einen Zeiger auf die erste Zelle jeder Spalte und jeder Zeile abrufbar gehalten und man konnte von jeder Zelle aus nach oben, unten, links und rechts gehen. hatte natürlich auch immer noch einen Zeiger auf meine aktuelle Zelle im Speicher...

Performance ist hier ganz signifikant... das Einlesen in ein TStringGrid dauerte bei 2MB-Protokolldateien an die 10 Sekunden... mit meinem TVirtualGrid nicht mal eine Sekunde...

Motzi - Fr 14.07.06 13:09

---

Marco D. hat folgendes geschrieben:

Und wenn man oft Daten hinzufügt und öfter suchen muss? :mrgreen: Macht es Sinn, eine Klasse für verkettete Listen zu schreiben?

In so einem Fall ist wohl eine Hash-Liste (THashedStringList und TBucketList) optimal! ;)

Arrays können ihren Vorteil beim Suchen aber nur dann ausspielen wenn sie sortiert sind. Bei unsortieren Arrays muss man erst recht wieder alle Elemente vom Anfang bis zum Ende durchegehen womit auch dieser Vorteil weg wäre.

Marco D. - So 16.07.06 13:00

---

Gibt es denn schon eine Klasse dafür, sodass meine Mühen dann umsonst wären?

Marco D. - Mo 17.07.06 13:17

---

Hm, also gibt es so eine noch nicht?

digi_c - Mo 17.07.06 14:07

---

Nun es gibt ja TCollection, TStack, TQueue.

TStringlist tauscht z.B. auch nur Zeiger(TStringList.ExchangeItems) und nicht die Werte. Wie das aber nun ganz im Detail aussieht weiß ich auch nicht, vermutlich nur ein Array of String.

Verkette Listen sind die Grundlagen, wie man flexibel Daten anordnet. Dadurch bruahc man nicht den Speicher verändern sondern verändert nur den Zeiger auf den Eintrag im Speicher(also 1x32bit anstatt einen ganzen Record oder so).
Die Klassen umhüllen das für dich nur in einem schönen OOP Kostüm(was mir persönlich ganz gut gefällt ;))

Motzi - Mo 17.07.06 19:00

---

In meinem Pointer-Tutorial auf http://www.manuel-poeter.de ist eín Demo-Projekt dabei das eine doppelt verkettete Liste implementiert, allerdings nicht in OOP, sondern mit Records - schließlich sollte der Gebrauch von Pointern demonstriert werden.