Unterschied zwischen Array-Liste und verknüpfter Liste

Wie werden Daten gespeichert?

Array-Liste und Verknüpfte Liste sind gebräuchliche Begriffe, wenn es um Datenspeicherung und -abruf geht. Obwohl es viele Speichergeräte gibt, hängen sie letztendlich vom Speichermechanismus ab. Diese beiden Speichermechanismen platzieren Ihre Daten in den Speichergeräten und rufen sie bei Bedarf ab. Werfen wir einen Blick darauf, wie sie Daten in ihrem Speicher speichern. Die Array-Liste verwendet einen sequentiellen Speicher, und die Daten werden nacheinander gespeichert. Dies ist vielleicht eine einfachere Form der Speicherung - es vermeidet Verwirrung. Ja, wir können das nächste Element oder die nächsten Daten vom nächsten Speicherort der Array-Liste abrufen. Es wird jedoch mithilfe von Zeigern in der Liste Linked gespeichert. Hier benötigen wir zwei Speicherplätze für den Speicher - einen für die Daten, den anderen für den Zeiger. Ein Zeiger adressiert den Speicherort der nächsten Daten. Wir können leicht verstehen, dass die verknüpfte Liste niemals Daten sequenziell speichert; Stattdessen wird ein zufälliger Speichermechanismus verwendet. Die Zeiger sind die Schlüsselelemente zum Lokalisieren der Datenorte in dem Speicher.

Dynamisches Array und Verknüpfte Liste

Wir haben bereits besprochen, wie beide Speichermechanismen Daten einfügen, und wir können den Begriff "dynamisches Array" für das interne Speicherschema der Array-Liste angeben. Es fügt nur Datenstücke nacheinander - also den Namen - ein, während die Linked-Liste eine interne Liste mit Hilfe von Zeigern verwendet, um das nächste Element zu verfolgen. Daher verwendet es eine interne verkettete Liste, wie eine einfach oder doppelt verknüpfte Liste, um uns die nächsten Daten zu zeigen.

Speichernutzung

Da die Array-Liste nur die tatsächlichen Daten enthält, benötigen wir nur Speicherplatz für die Daten, die wir speichern. Umgekehrt verwenden wir in der Linked-Liste auch Zeiger. Daher sind zwei Speicherorte erforderlich, und wir können sagen, dass die verknüpfte Liste mehr Speicher belegt als die Array-Liste. Eine vorteilhafte Seite der Verknüpfungsliste besteht darin, dass im Gegensatz zur Array-Liste niemals fortlaufende Speicherorte zum Speichern unserer Daten erforderlich sind. Die Zeiger können die Position des nächsten Datenorts halten, und wir können sogar kleinere Speichersteckplätze verwenden, die nicht kontinuierlich sind. Wenn es um die Speichernutzung geht, spielen Zeiger die Hauptrolle in der Linked-Liste und damit auch die Effektivität.

Größe der ersten Array-Liste und der verknüpften Liste

Bei der Array-Liste ist für eine leere Liste eine Größe von 10 erforderlich, aber bei einer Linked-Liste benötigen wir keinen so großen Platz. Wir können eine leere Linked-Liste mit einer Größe von 0 erstellen. Später können wir die Größe nach Bedarf erhöhen.

Datenabruf

Der Datenabruf ist in der Array-Liste einfacher, da er sequenziell gespeichert wird. Alles, was es tut, ist die erste Datenstelle zu identifizieren; Von dort aus wird auf den nächsten Ort sequentiell zugegriffen, um den Rest abzurufen.Es berechnet sich wie die erste Datenposition + 'n', wobei 'n' die Reihenfolge der Daten in der Array-Liste ist. Die verknüpfte Liste verweist auf den Anfangszeiger, um den ersten Datenspeicherort zu finden, und von dort verweist er auf den Zeiger, der den einzelnen Daten zugeordnet ist, um den nächsten Datenspeicherort zu finden. Der Abrufprozess ist hier hauptsächlich von den Zeigern abhängig und zeigt uns effektiv den nächsten Datenstandort.

Ende der Daten

Die Array-Liste verwendet einen Nullwert, um das Ende der Daten zu markieren, während die Verknüpfungsliste einen Nullzeiger für diesen Zweck verwendet. Sobald das System Nulldaten erkennt, stoppt die Array-Liste den nächsten Datenabruf. In ähnlicher Weise hält der Nullzeiger das System davon ab, mit dem nächsten Datenabruf fortzufahren.

Reverse Traversal

Die Linked-Liste ermöglicht es, mit Hilfe von despendingiterator () in umgekehrter Richtung zu verfahren. Eine solche Möglichkeit haben wir jedoch nicht in einer Array-Liste - Reverse Traversal wird hier zum Problem.

Syntax

Betrachten wir die Java-Syntax beider Speichermechanismen.

Erstellen einer Array-Liste:

List arraylistsample = new ArrayList ();

Hinzufügen von Objekten zur Array-Liste:

Arraylistsample. addiere ("name1");

Arraylistsample. füge hinzu ("name2");

So sieht die resultierende Array-Liste aus - [name1, name2].

Erstellen einer verknüpften Liste:

List linkedlistsample = new linkedList ();

Hinzufügen von Objekten zur verknüpften Liste:

Linkedlistsample. füge hinzu ("name3");

Linkedlistsample. füge hinzu ("name4");

So sieht die resultierende Linked-Liste aus - [name3, name4].

Was ist besser für die Get oder Search Operation?

Die Array-Liste benötigt eine O (1) Zeit, um eine Datensuche auszuführen, während die Verknüpfte Liste u O (n) für die n th Datensuche verwendet. Daher verwendet eine Array-Liste immer eine konstante Zeit für jede Datensuche, aber in der Linked-Liste hängt die benötigte Zeit von der Position der Daten ab. Daher sind Array-Listen immer eine bessere Wahl für Get- oder Search-Operationen.

Was ist besser für den Einfüge- oder Additionsvorgang?

Sowohl die Array-Liste als auch die verknüpfte Liste benötigen eine O (1) -Zeit für die Datenaddition. Wenn das Array jedoch voll ist, benötigt die Array-Liste eine beträchtliche Zeit, um die Größe zu ändern und die Elemente auf die neuere zu kopieren. In einem solchen Fall ist die Linked-List die bessere Wahl.

Was ist besser für den Remove-Betrieb?

Die Entfernung dauert in der Array-Liste und in der Linked-Liste fast genauso lange. In der Array-Liste löscht diese Operation die Daten und verschiebt dann die Position der Daten, um das neuere Array zu bilden - es dauert O (n) -Zeit. In der Verknüpfungsliste durchläuft diese Operation die bestimmten Daten und ändert die Zeigerpositionen, um die neuere Liste zu bilden. Die Zeit für das Traversieren und das Entfernen ist auch hier O (n).

Was ist schneller?

Wir wissen, dass eine Array-Liste ein internes Array zum Speichern der eigentlichen Daten verwendet. Wenn irgendwelche Daten gelöscht werden, benötigen daher alle bevorstehenden Daten eine Speicherverschiebung.Offensichtlich erfordert dies eine beträchtliche Menge an Zeit und verlangsamt die Dinge. Solch eine Speicherverschiebung ist in der Linked-Liste nicht erforderlich, da sie nur die Position des Zeigers ändert. Daher ist eine verknüpfte Liste in jeder Art von Datenspeicher schneller als eine Array-Liste. Dies hängt jedoch ausschließlich von der Art der Operation ab, d. e. Für die Operation Get oder Search benötigt die Linked-List viel mehr Zeit als eine Array-Liste. Wenn wir uns die Gesamtleistung ansehen, können wir sagen, dass die Linked-Liste schneller ist.

Wann wird eine Array-Liste und eine verknüpfte Liste verwendet?

Eine Array-Liste eignet sich am besten für kleinere Datenanforderungen, bei denen kontinuierlicher Speicher verfügbar ist. Aber wenn wir mit riesigen Datenmengen umgehen, implementiert die Verfügbarkeit von kontinuierlichem Speicher die Datenspeichermechanismen, ob sie klein oder riesig sind. Entscheiden Sie als Nächstes, welche Sie auswählen möchten - die Array-Liste oder die Linked-Liste. Sie können mit einer Array-Liste fortfahren, wenn Sie nur Daten speichern und abrufen müssen. Aber eine Liste kann Ihnen darüber hinaus helfen, Daten zu manipulieren. Sobald Sie entscheiden, wie häufig Datenmanipulationen erforderlich sind, müssen Sie überprüfen, welche Art von Datenabruf normalerweise durchgeführt wird. Wenn es nur Get oder Search ist, dann ist die Array-Liste die bessere Wahl; Für andere Operationen wie Einfügen oder Löschen, fahren Sie mit der Linked-Liste fort.

Betrachten wir die Unterschiede in der Tabellenform.

S. Nein Konzepte Unterschiede
Array-Liste Verknüpfte Liste
1 Datenspeicher Mode Verwendet sequentiellen Datenspeicher Verwendet nicht sequentiellen Datenspeicher
2 < Internes Speicherschema Behält ein internes dynamisches Array bei Verwaltet eine verknüpfte Liste 3
Speicherbelegung Benötigt Speicherplatz nur für die Daten Benötigt Speicherplatz für Daten sowie für Zeiger 4
Größe der Anfangsliste Benötigt Platz für mindestens 10 Objekte Benötigt keinen Platz und wir können sogar eine leere Liste der Größe 0 erstellen. 5
Data Retrieval Berechnet wie die erste Datenposition + 'n', wobei 'n' die Reihenfolge der Daten in der Array-Liste ist Traversal vom ersten oder letzten bis die benötigten Daten benötigt werden 6 < Ende der Daten
Die Null-Werte markieren das Ende Der Null-Zeiger markiert das Ende 7 Reverse Traversal
Erlaubt es nicht Erlaubt es mit Hilfe von descending ( ) 8 Listenerstellung Syntax
Liste arraylistsample = new Array Liste (); Liste Linkedlistsample = new linkedList (); 9

Hinzufügen von Objekten

Arraylistsample. addiere ("name1"); Linkedlistsample. füge hinzu ("name3"); 10

Holen oder Suchen

Nimmt O (1) Zeit und ist besser in der Leistung Nimmt O (n) Zeit und Leistung ist abhängig von der Position der Daten 11 REPLACE oder Addition
Verbraucht O (1) Zeit, außer wenn das Array voll ist Verbraucht O (1) Zeit unter allen Umständen 12 Löschen oder Entfernen
Nimmt O (n) Zeit < Nimmt O (n) Zeit 13 Wann zu verwenden? Wenn viele Get- oder Search-Operationen beteiligt sind; die Speicherverfügbarkeit sollte schon beim Start höher sein
Bei vielen Operationen Einfügen oder Löschen und die Speicherverfügbarkeit muss nicht kontinuierlich sein