Unterschied zwischen Arrays und verknüpften Listen
Arrays gegen verknüpfte Listen
Arrays sind die am häufigsten verwendete Datenstruktur, um die Sammlung von Elementen zu speichern. Die meisten Programmiersprachen bieten Methoden, um Arrays und Zugriff auf Elemente in den Arrays zu deklarieren. Die verknüpfte Liste, genauer gesagt nur verknüpfte Liste, ist auch eine Datenstruktur, mit der die Sammlung von Elementen gespeichert werden kann. Es besteht aus einer Sequenz von Knoten und jeder Knoten hat einen Verweis auf den nächsten Knoten in der Sequenz.
In Abbildung 1 ist ein Stück Code angezeigt, das normalerweise verwendet wird, um ein Array zu deklarieren und Werte zuzuweisen. Abbildung 2 zeigt, wie ein Array im Speicher aussehen würde.
Oben Code definiert ein Array, mit dem 5 Ganzzahlen gespeichert werden können und auf sie werden mit Indizes 0 bis 4 zugegriffen. Eine wichtige Eigenschaft eines Arrays ist, 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 nicht sicher sind, wie groß das Array zur Kompilierungszeit ist, müssten Sie ein ausreichend großes Array definieren, um sich auf der sicheren Seite zu befinden. Aber die meiste Zeit werden wir tatsächlich weniger Elemente verwenden, als wir zugewiesen haben. Es wird also tatsächlich eine beträchtliche Menge an Speicher verschwendet. Andererseits würde das Programm zum Absturz gebracht, wenn das „Groß genug Array“ nicht wirklich groß genug ist.
Eine verknüpfte Liste verteilt ihren Elementen in ihrem eigenen Speicherblock Speicher und die Gesamtstruktur wird erhalten, indem diese Elemente als Glieder in einer Kette verknüpft werden. Jedes Element in einer verknüpften Liste enthält zwei Felder, wie in Abbildung 3 gezeigt. Das Datenfeld enthält die tatsächlichen Daten gespeichert und das nächste Feld enthält den Verweis auf das nächste Element in der Kette. Das erste Element der verlinkten Liste wird als Kopf der verknüpften Liste gespeichert.
| Daten | nächste |
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 mit Ausnahme des letzten einen Verweis auf das nächste Element. Das letzte Element hält einen Nullwert in seinem nächsten Feld. Auf jedes Element in der Liste kann zugegriffen werden, indem Sie am Kopf beginnen und dem nächsten Zeiger folgen, bis Sie das erforderliche Element erfüllen.
Obwohl die Arrays und verknüpften Listen in dem Sinne ähnlich sind. Arrays vergeben allen Elementen Speicher als einzelner Block und die Größe des Arrays muss zur Laufzeit ermittelt 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 separat Speicher zugibt, wäre sie in Situationen, in denen Sie die Größe der Liste zur Kompilierungszeit nicht kennen, viel effizient. Die Erklärung und Zugriff auf Elemente in einer verknüpften Liste wäre im Vergleich dazu, wie Sie mit seinen Indizes direkt auf Elemente in einem Array zugreifen.
