12 Unterschied zwischen Array- und Linked-List-Datenstrukturen (mit Vergleichstabelle)

Array und verknüpfte Listen sind Typen von Datenstrukturen. Eine Datenstruktur ist eine Methode zum Organisieren eines Datensatzes. Die Struktur wird dadurch definiert, wie die Daten gespeichert werden und wie Operationen wie Datenzugriff, Einfügen und Löschen an den gespeicherten Daten durchgeführt werden. Datenstrukturen sind wichtige Werkzeuge für Programmierer, da jede Struktur eine Reihe von Vorteilen hat, die sie für die Lösung bestimmter Problemtypen nützlich machen.

Contents

Was ist eine Array-Datenstruktur?

Eine Array-Datenstruktur oder einfach Array ist eine Datenstruktur, die aus einer Sammlung von Elementen (Werten oder Variablen) besteht, die jeweils durch mindestens einen Array-Index oder -Schlüssel identifiziert werden. Ein Array wird so gespeichert, dass die Position jedes Elements aus seinem Indextupel durch eine mathematische Formel berechnet werden kann.

Arrays sind vor allem deshalb nützlich, weil die Elementindizes zur Laufzeit berechnet werden können. Unter anderem ermöglicht diese Funktion einer einzelnen iterativen Anweisung, beliebig viele Elemente eines Arrays zu verarbeiten. In dieser Hinsicht müssen die Elemente einer Array-Datenstruktur die gleiche Größe haben und sollten die gleiche Datendarstellung verwenden. Die Menge der gültigen Indextupel und die Adressen der Elemente sind normalerweise, aber nicht immer, während der Verwendung des Arrays festgelegt.

Arten von Arrays

Eindimensionale (1-D) Arrays oder lineare Arrays . In diesen Arrays wird jedes Element durch einen einzelnen Index dargestellt.
Zweidimensionale (2-D) Arrays oder Matrix-Arrays . In diesen Arrays wird jedes Element durch einen einzelnen Index dargestellt.
Dreidimensionale Arrays. In diesen Arrays wird jedes Element durch drei Indizes dargestellt.

Was Sie wissen müssen Array-Datenstruktur

Ein Array ist die Datenstruktur, die eine Sammlung ähnlicher Datenelemente enthält.
Speicher wird allokiert, sobald das Array zur Kompilierzeit deklariert wird. Dies wird als statische Speicherzuweisung bezeichnet.
Array kann eindimensional, zweidimensional oder dreidimensional sein.

Die Größe des Arrays muss zum Zeitpunkt der Array-Deklaration/Initialisierung angegeben werden.
Der Speicherbedarf ist begrenzt, da die tatsächlichen Daten im Index im Array gespeichert sind.
Einfüge- und Löschvorgänge dauern einige Zeit, da die Speicherplätze aufeinanderfolgend und fest sind.

Im Array ist jedes Element unabhängig, keine Verbindung zum vorherigen Element oder zu seiner Position.
In Arrays werden Elemente in aufeinanderfolgenden Speicherplätzen gespeichert, also beim Einfügen von Elementen; wir müssen Platz zum Einfügen schaffen.
Array unterstützt Random Access, die Mittel können Elemente direkt ihren Index verwendet zugegriffen werden, wie arr [0] für 1 ^st Element, arr [4 ] für 5 ^th Element usw. Daher Elemente in einem Array zugreift ist schnell mit einer konstanten Zeit Komplexität von 0(1).

Array erhält Speicher im Stack- Abschnitt zugewiesen .
Die Speicherauslastung im Array ist ineffizient.
Binäre und lineare Suche werden im Array verwendet.

Was ist die Datenstruktur der verknüpften Liste?

Eine verknüpfte Liste ist eine lineare Datenstruktur, bei der jedes Element ein separates Objekt ist. Verknüpfte Listenelemente werden nicht an ansteckenden Orten gespeichert; die Elemente werden mit Zeigern verknüpft. Jeder Knoten einer Liste besteht aus zwei Elementen – den Daten und einem Verweis auf den nächsten Knoten. Der letzte Knoten hat eine Referenz auf null.

Verknüpfte Listen gehören zu den einfachsten und gebräuchlichsten Datenstrukturen. Sie können verwendet werden, um mehrere andere allgemeine abstrakte Datentypen zu implementieren, einschließlich Listen, Stapel, Warteschlangen, assoziative Arrays und S-Ausdrücke, obwohl diese Datenstrukturen direkt implementiert werden können, ohne eine verkettete Liste als Grundlage zu verwenden.

Arten von verknüpften Listen

Einfache Linked List – Die Navigation in den Elementen erfolgt nur vorwärts.

Doppelt verknüpfte Liste – Elemente können vorwärts und rückwärts navigiert werden.
Circular Linked List – Das letzte Element enthält den Link des ersten Elements als nächstes und das erste Element hat einen Link zum letzten Element wie das vorherige.

Anwendungen der verknüpften Liste

Verknüpfte Listen können verwendet werden, um Hash-Tabellen zu implementieren – Jeder Bucket der Hash-Tabelle kann eine verknüpfte Liste sein (Open Chain Hashing).

Verknüpfte Listen können verwendet werden, um Graphen zu implementieren.
Verknüpfte Listen können verwendet werden, um Stacks, Queues und Trees zu implementieren.

Was Sie über die Datenstruktur von verknüpften Listen wissen müssen

Die verknüpfte Liste wird als nicht-primitive Datenstruktur betrachtet und enthält eine Sammlung von ungeordneten verknüpften Elementen, die als Knoten bezeichnet werden.

Speicher wird zur Laufzeit zugewiesen, wenn ein neuer Knoten hinzugefügt wird. Es wird auch als dynamische Speicherzuweisung bezeichnet.
Die verknüpfte Liste kann eine lineare (einzelne), doppelte oder kreisförmige verknüpfte Liste sein.
Die Größe einer verknüpften Liste ist variabel. Es wächst zur Laufzeit, wenn ihm weitere Knoten hinzugefügt werden.

Die Speicheranforderungen in der verknüpften Liste sind eher auf die Speicherung zusätzlicher nächster und vorheriger Referenzierungselemente zurückzuführen.
Einfüge- und Löschvorgänge sind in einer verknüpften Liste schnell und einfach, da nur der Wert des Zeigers zum Ändern benötigt wird. Im Fall einer verketteten Liste wird ein neues Element an der ersten freien und verfügbaren Speicherstelle gespeichert, mit nur einem einzigen Overhead-Schritt des Speicherns der Adresse der Speicherstelle im vorherigen Knoten der verketteten Liste.
In der verknüpften Liste werden Positionen oder Adressen von Elementen im Verknüpfungsteil des vorherigen Elements/Knotens gespeichert oder Elemente zeigen auf den nächsten, vorherigen oder möglicherweise beide Knoten.

In einer verknüpften Liste können Elemente an jedem verfügbaren Ort gespeichert werden, da die Adresse des Knotens im vorherigen Knoten der verknüpften Liste gespeichert wird, wodurch eine Verbindung zwischen den beiden Knoten/Elementen gebildet wird.
Die verknüpfte Liste unterstützt den sequenziellen Zugriff, was bedeutet, auf jedes Element/Knoten in einer verknüpften Liste zuzugreifen; wir müssen sequentiell die komplette verkettete Liste bis zu diesem Element durchlaufen. Um auf das n- ^te Element einer verknüpften Liste zuzugreifen , beträgt die Zeitkomplexität 0 (n).
Die verknüpfte Liste erhält im Heap-Abschnitt zugewiesenen Speicher.

Außerdem ist die Speicherauslastung in der verknüpften Liste effizient.
In der verknüpften Listendatenstruktur wird nur die lineare Suche verwendet.

Lesen Sie auch: Unterschied zwischen Array und Zeiger

Unterschied zwischen Array und verknüpfter Liste in Tabellenform

VERGLEICHSGRUNDLAGE	ARRAY	VERLINKTE LISTE
Beschreibung	Ein Array ist die Datenstruktur, die eine Sammlung ähnlicher Datenelemente enthält.	Die verknüpfte Liste wird als nicht-primitive Datenstruktur betrachtet und enthält eine Sammlung von ungeordneten verknüpften Elementen, die als Knoten bezeichnet werden.
Speicherzuweisung	Speicher wird allokiert, sobald das Array zur Kompilierzeit deklariert wird. Dies wird als statische Speicherzuweisung bezeichnet.	Speicher wird zur Laufzeit zugewiesen, wenn ein neuer Knoten hinzugefügt wird. Es wird auch als dynamische Speicherzuweisung bezeichnet.
Typen	Array kann eindimensional, zweidimensional oder dreidimensional sein.	Die verknüpfte Liste kann eine lineare (einzelne), doppelte oder kreisförmige verknüpfte Liste sein.
Für dich	Die Größe des Arrays muss zum Zeitpunkt der Array-Deklaration/Initialisierung angegeben werden.	Die Größe einer verknüpften Liste ist variabel. Es wächst zur Laufzeit, wenn ihm weitere Knoten hinzugefügt werden.
Speicherbedarf	Der Speicherbedarf ist begrenzt, da die tatsächlichen Daten im Index im Array gespeichert sind.	Die Speicheranforderungen in der verknüpften Liste sind eher auf die Speicherung zusätzlicher nächster und vorheriger Referenzierungselemente zurückzuführen.
Einfüge- und Löschvorgänge	Einfüge- und Löschvorgänge dauern einige Zeit, da die Speicherplätze aufeinanderfolgend und fest sind.	Einfüge- und Löschvorgänge sind in einer verknüpften Liste schnell und einfach, da nur der Wert des Zeigers zum Ändern benötigt wird.
Lagerung von Elementen	In Arrays werden Elemente in aufeinanderfolgenden Speicherplätzen gespeichert, also beim Einfügen von Elementen; wir müssen Platz zum Einfügen schaffen.	In einer verknüpften Liste können Elemente an jedem verfügbaren Ort gespeichert werden, da die Adresse des Knotens im vorherigen Knoten der verknüpften Liste gespeichert wird, wodurch eine Verbindung zwischen den beiden Knoten/Elementen gebildet wird.
Unterstützte Zugriffsarten	Array unterstützt Random Access, die Mittel können Elemente direkt ihren Index verwendet zugegriffen werden, wie arr [0] für 1 ^st Element, arr [4 ] für 5 ^th Element usw. Daher Elemente in einem Array zugreift ist schnell mit einer konstanten Zeit Komplexität von 0(1).	Die verknüpfte Liste unterstützt den sequenziellen Zugriff, was bedeutet, auf jedes Element/Knoten in einer verknüpften Liste zuzugreifen; wir müssen sequentiell die komplette verkettete Liste bis zu diesem Element durchlaufen. Um auf das n- ^te Element einer verknüpften Liste zuzugreifen , beträgt die Zeitkomplexität 0 (n).
Abschnitt zur Speicherzuweisung	Array erhält Speicher im Stack- Abschnitt zugewiesen .	Die verknüpfte Liste erhält im Heap-Abschnitt zugewiesenen Speicher.
Speicherauslastung	Die Speicherauslastung im Array ist ineffizient.	Außerdem ist die Speicherauslastung in der verknüpften Liste effizient.
Art der Suche	Binäre und lineare Suche werden im Array verwendet.	In der verknüpften Listendatenstruktur wird nur die lineare Suche verwendet.

Lesen Sie auch: Unterschied zwischen Stack und Heap in C

Vorteile der verknüpften Liste

Geeignet für jede Art von Einfügung.
Datenstrukturen wie Stacks, Queues und Trees können einfach mit Linked List implementiert werden.

Objekte können mit for loop, iterator, listIterator, descendingIterator durchlaufen werden.
Kann verteilten freien Speicherplatz verwenden.
Folgt intern einer doppelt verketteten Listendatenstruktur.

Die Größe der verknüpften Listen ist nicht festgelegt; sie können sich während der Laufzeit ausdehnen und schrumpfen.
Die Speicherzuweisung erfolgt während der Laufzeit (es muss kein fester Speicher zugewiesen werden).
Einfüge- und Löschvorgänge sind in verknüpften Listen schnell und einfacher.

Die Speicherzuweisung wird zur Laufzeit zugewiesen.
Eine verknüpfte Liste kann mehr als einen Wert gleichzeitig enthalten.

Nachteile der verlinkten Liste

Die Knoten in der verknüpften Liste können hinzugefügt und aus der Liste gelöscht werden.

Das Modifizieren des Knotens in einer verknüpften Liste ist ein komplexer Vorgang.
Zeiger benötigen zusätzlichen Speicher in der Datenstruktur der verknüpften Liste.
Der wahlfreie Zugriff ist nicht erlaubt.

Einfüge- und Löschvorgänge sind in verknüpften Listen kostspieliger.
In einfach verketteten Listen ist das Traversieren von rückwärts nicht möglich.

Vorteile von Array

Arrays sind lineare Datenstrukturen.

Array hat homogene Werte.
Array-Elemente können leicht geändert werden, indem der Indexwert identifiziert wird.
Array-Elemente können nicht hinzugefügt oder gelöscht werden, sobald sie deklariert wurden.

Arrays haben eine bessere Cache-Lokalität, die einen ziemlich großen Unterschied in der Leistung ausmachen kann.
Array kann jeweils nur einen Wert enthalten.
Array kann verwendet werden, um andere Datenstrukturen wie verknüpfte Listen, Stacks, Warteschlangen, Bäume, Grafiken usw. zu implementieren.

Nachteile von Array

Im Array gibt es eine ineffektive Speicherauslastung.
Die Elemente des Arrays werden in aufeinanderfolgenden Speicherplätzen gespeichert. Einfügungen und Löschungen sind daher sehr schwierig und zeitaufwendig.
Da das Array eine feste Größe hat, wird der Speicherplatz verschwendet, wenn wir mehr Speicher als erforderlich zuweisen. Und wenn wir weniger Speicher als erforderlich zuweisen, wird dies zu Problemen führen.