Arrays vs verknüpfte Listen
Arrays sind die am häufigsten verwendete Datenstruktur zum Speichern der Sammlung von Elementen. Die meisten Programmiersprachen bieten Methoden zum einfachen Deklarieren von Arrays und zum Zugriff auf Elemente in den Arrays. Verknüpfte Liste, genauer gesagt einfach verknüpfte Liste, ist auch eine Datenstruktur, die zum Speichern der 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 Code dargestellt, der normalerweise zum Deklarieren und Zuweisen von Werten zu einem Array verwendet wird. Abbildung 2 zeigt, wie ein Array im Speicher aussehen würde.
Der obige Code definiert ein Array, das 5 Ganzzahlen speichern kann und auf das mit den Indizes 0 bis 4 zugegriffen wird. Eine wichtige Eigenschaft eines Arrays besteht darin, dass das gesamte Array als einzelner Speicherblock zugewiesen wird und jedes Element seinen eigenen Speicherplatz im Array erhält. Sobald ein Array definiert ist, ist seine Größe festgelegt. Wenn Sie sich also beim Kompilieren 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. Meistens werden wir jedoch weniger Elemente verwenden, als wir zugewiesen haben. So wird tatsächlich eine beträchtliche Menge an Speicher verschwendet. Wenn andererseits das "ausreichend große Array" nicht groß genug ist, stürzt das Programm ab.
Eine verknüpfte Liste ordnet ihren Elementen Speicher separat in einem eigenen Speicherblock zu, und die Gesamtstruktur wird erhalten, indem diese Elemente als Glieder in einer Kette verknüpft werden. Jedes Element in einer verknüpften Liste verfügt über zwei Felder (siehe Abbildung 3). 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.
Abbildung 3: Element einer verknüpften Liste
Abbildung 4 zeigt eine verknüpfte 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 im nächsten Feld einen Nullwert. Auf jedes Element in der Liste kann zugegriffen werden, indem Sie am Kopf beginnen und dem nächsten Zeiger folgen, bis Sie das gewünschte Element erreichen.
Obwohl die Arrays und verknüpften Listen in dem Sinne ähnlich sind, dass beide zum Speichern der Sammlung von Elementen verwendet werden, ergeben sich aufgrund der Strategien, mit denen sie den Elementen Speicher zuweisen, Unterschiede. 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 Kompilierungszeit nicht kennen. Da eine verknüpfte Liste ihren Elementen Speicher separat zuweist, ist sie in Situationen, in denen Sie die Größe der Liste zum Zeitpunkt der Kompilierung nicht kennen, sehr effizient. Das Deklarieren und Zugreifen auf Elemente in einer verknüpften Liste wäre nicht einfach, verglichen mit dem direkten Zugriff auf Elemente in einem Array mithilfe seiner Indizes.
