Arrays vs. verknüpfte Listen
Arrays sind die am häufigsten verwendete Datenstruktur, um eine Sammlung von Elementen zu speichern. Die meisten Programmiersprachen bieten Methoden, um Arrays einfach zu deklarieren und auf Elemente in den Arrays zuzugreifen. Eine verkettete Liste, genauer gesagt eine einfach verkettete Liste, ist ebenfalls eine Datenstruktur, die zum Speichern einer Sammlung von Elementen verwendet werden kann. Es besteht aus einer Folge von Knoten und jeder Knoten hat einen Verweis auf den nächsten Knoten in der Folge.
In Abbildung 1 ist ein Codestück dargestellt, das normalerweise verwendet wird, um Werte zu deklarieren und einem Array Werte zuzuweisen. Abbildung 2 zeigt, wie ein Array im Speicher aussehen würde.
Der obige Code definiert ein Array, das 5 Ganzzahlen speichern kann und auf die über die Indizes 0 bis 4 zugegriffen wird. Eine wichtige Eigenschaft eines Arrays ist, dass das gesamte Array als ein einzelner Speicherblock zugewiesen wird und jedes Element seinen eigenen Platz erhält im Array. Sobald ein Array definiert ist, ist seine Größe festgelegt. Wenn Sie also zur Kompilierzeit nicht sicher sind, wie groß das Array ist, müssen Sie ein Array definieren, das groß genug ist, um auf der sicheren Seite zu sein. Aber meistens werden wir tatsächlich weniger Elemente verwenden, als wir zugewiesen haben. Es wird also tatsächlich eine beträchtliche Menge an Speicher verschwendet. Wenn andererseits das „large enough array“nicht wirklich groß genug ist, würde das Programm abstürzen.
Eine verkettete Liste weist ihren Elementen Speicher getrennt in ihrem eigenen Speicherblock zu, und die Gesamtstruktur wird erh alten, indem diese Elemente als Glieder in einer Kette verknüpft werden. Jedes Element in einer verknüpften Liste hat zwei Felder, wie in Abbildung 3 gezeigt. Das Datenfeld enthält die tatsächlich gespeicherten Daten, und das nächste Feld enthält den Verweis auf das nächste Element in der Kette. Das erste Element der verknüpften Liste wird als Kopf der verknüpften Liste gespeichert.
| Daten | weiter |
Abbildung 3: Element einer verketteten Liste
Abbildung 4 zeigt eine verkettete Liste mit drei Elementen. Jedes Element speichert seine Daten und alle Elemente außer dem letzten speichern einen Verweis auf das nächste Element. Das letzte Element enthält einen Nullwert in seinem nächsten Feld. Auf jedes Element in der Liste kann zugegriffen werden, indem man am Kopf beginnt und dem nächsten Zeiger folgt, bis man auf das erforderliche Element trifft.
Obwohl die Arrays und verknüpften Listen in dem Sinne ähnlich sind, dass sie beide verwendet werden, um eine Sammlung von Elementen zu speichern, ergeben sie Unterschiede aufgrund der Strategien, die sie verwenden, um ihren Elementen Speicher zuzuweisen. Arrays weisen allen ihren Elementen Speicher als einen einzigen Block zu, und die Größe des Arrays muss zur Laufzeit bestimmt werden. Dies würde die Arrays in Situationen ineffizient machen, in denen Sie die Größe des Arrays zur Kompilierzeit nicht kennen. Da eine verknüpfte Liste ihren Elementen Speicher separat zuweist, wäre dies sehr effizient in Situationen, in denen Sie die Größe der Liste zur Kompilierzeit nicht kennen. Die Deklaration und der Zugriff auf Elemente in einer verknüpften Liste wären nicht einfach, verglichen mit dem direkten Zugriff auf Elemente in einem Array mithilfe seiner Indizes.
