Unterschied zwischen Arrays und verknüpften Listen

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 zum einfachen Deklarieren von Arrays und Zugriffselementen in den Arrays. Verknüpfte Liste, genauer eine einfach verknüpfte Liste, ist auch eine Datenstruktur, in der eine Sammlung von Elementen gespeichert werden kann. Sie besteht aus einer Folge von Knoten und jeder Knoten hat eine Referenz 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, in dem 5 Ganzzahlen gespeichert werden können, auf das über die 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 im Array einen eigenen Speicherplatz erhält. Sobald ein Array definiert ist, wird seine Größe festgelegt. Wenn Sie sich zum Zeitpunkt des Kompilierens nicht sicher sind, wie groß das Array ist, müssen Sie ein ausreichend großes Array definieren, um sich auf der sicheren Seite zu befinden. Meistens werden wir jedoch weniger Elemente verwenden, als wir zugewiesen haben. Eine beträchtliche Menge an Speicher wird also tatsächlich verschwendet. Wenn andererseits das „ausreichend große Array“ nicht groß genug ist, würde das Programm abstürzen.

Eine verknüpfte Liste ordnet ihren Elementen Speicher separat in ihrem eigenen Speicherblock zu, und die Gesamtstruktur wird durch Verknüpfung dieser Elemente als Verknüpfungen in einer Kette erhalten. Jedes Element in einer verknüpften Liste hat zwei Felder, wie in Abbildung 3 dargestellt. Das Datenfeld enthält die tatsächlich gespeicherten Daten und das nächste Feld enthält die Referenz 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 Element speichern eine Referenz auf das nächste Element. Letztes 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 sich in dem Sinne ähnlich sind, dass beide zum Speichern der Sammlung von Elementen verwendet werden, ergeben sich aufgrund der Strategien, die sie zum Zuweisen von Speicher zu ihren Elementen verwenden, Unterschiede. Arrays weisen all 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 den Elementen Speicher separat zuordnet, ist sie in Situationen, in denen Sie die Größe der Liste zum Zeitpunkt des Kompilierens nicht kennen, sehr effizient. Die Deklaration und der Zugriff auf Elemente in einer verknüpften Liste wäre nicht direkt verglichen mit dem direkten Zugriff auf Elemente in einem Array über deren Indizes.