C: Was kann eine verkettete Liste, was ein Array nicht kann?
Hab gerade eine Frage über verkettete Listen gesehen, und jetzt denke ich mir: Was genau kann denn so eine verkettete Liste mehr als ein Array/Pointer?
Mit realloc kann ich die größe des arrays ja auch während das Programm läuft verändern.. mehr vorteile einer linked list finde ich nicht. also: Warum sollte man eine Linked List hernehmen?
4 Antworten
Ein Vorteil ist beim Hinzufügen und Löschen eines Elements: Bei der verketteten Liste haben beide Operationen konstante Laufzeit.
Bei Arrays kommt es auf die Implementierung an. In den meisten Situationen sind (dynamische) Arrays genauso effizient, oftmals sogar effizienter. In manchen Situationen ist eine verkettete Liste aber auch besser geeignet; dabei kommt es darauf an, was du mit der Liste machen willst.
Der wichtigste Vorteil ist aber bei unveränderlichen Listen: Funktionale Programmiersprachen bevorzugen nicht grundlos fast immer verkettete Listen. Bei einer verketteten Liste kannst du nämlich am Anfang ein Element anhängen oder entfernen, ohne andere Referenzen auf die Liste zu beeinflussen. Die Liste ist also effektiv unveränderlich (auch persistent genannt). Bei Arrays ist das nicht in konstanter Laufzeit möglich.
Der Speicher für eine verkettete Liste kann beliebig fragmentiert sein, solange jedes Fragment ein Item der Liste fassen kann. Der Speicher muss dazu theoretisch nicht mal auf dem selben Gerät liegen (was bei Mikroprozessoren interessant sein kann).
Löschen und Einfügen führt in einem Array zur Verschiebung des Speicherinhalts, braucht also sehr teure Verschiebeoperationen. Das ist bei verketteten Listen nicht nötig.
Dazu ist reallozieren eine unheimlich teure Aktion. Das während der Laufzeit zu tun ist also alles andere als empfehlenswert.
realloc kann dir nur einen zusammengesetzen Speicherbereich liefern. Wenn du also insgesamt 1GB Arbeitsspeicher frei hättest, aber in diesem kein zusammenhängender Block mit 1GB existiert wird dir realloc kein Ergebnis liefern können eine Linked List kann aber den vollen Speicher nutzen (mit Abzug des Overheads natürlich), weil die Elemente nicht in einem zusammenhängenden Speicherbereich sein müssen.
Je nach implementierung und umständen kann realloc aber auch sehr langsam sein, weil es dein Array nimmt. Dann malloc aufruft um einen größeren Speicherblock zu finden und dann mittels memcpy dein altes Array in den neuen Speicher kopiert. Bei einer Linked List reicht zum hinzufügen ein malloc Aufruf und ein paar Speicheroperationen aus.
malloc und realloc nutzt man also nur dann wenn man vorne herein weiß, dass sich der allozierte Speicher vermutlich nicht oft verändern wird. Dann sind Arrays ja auch viel schneller als Linked Lists und Linked Lists verwendet man wenn sich der Speicherverbrauch ständig dynamisch an die gespeicherten Daten anpassen sollen.
Ein weiterer Vorteil von Linked Lists ist, dass man mit relativ geringen aufwand Elemente in der Mitte einfügen kann. Bei einem Array müsste man alles nach diesem jeweiligen Eintrag verschieben, was eine menge Operationen sein können.
Außerdem bleibt ein Zeiger auf ein Element der Linked List, auch nach dem löschen oder einfügen beliebiger Element gleich, was bei Arrays nicht der Fall ist.
Wenn du ein Array mit 100 Mio. Einträgen hast, und du willst einen einzigen Eintrag anfügen, muss realloc() den ganzen Klimmbimm umkopieren. Bei einer Liste wird kurz und knapp einfach nur das neue Element ans Ende angefügt.
Außerdem ist ein Array eigentlich immer etwas zu groß ... eine Liste hingegen hat immer die perfekte Größe.
Ein Array arbeitet u. U. aber schneller, aber dafür gibt es ja Datenstrukturen, die Arrays mit Listen kombinieren. Für mehr gibts dann noch Bäume, Maps, Sets, usw. usf.
realloc() ist verglichen mit dem einfach anfügen an eine Liste viel viel "teuer" und benötigt gerne 10000 mal oder mehr so viel Zeit.