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 das Speichern und Abrufen von Daten geht. Obwohl es viele Speichergeräte gibt, hängen sie letztendlich vom Speichermechanismus ab. Diese beiden Speichermechanismen speichern Ihre Daten in den Speichergeräten und rufen sie bei Bedarf ab. Lassen Sie uns einen Blick darauf werfen, wie sie Daten in ihrem Speicher ablegen. Die Array-Liste verwendet einen sequentiellen Speicher, und die Daten werden nacheinander gespeichert. Dies ist möglicherweise eine einfachere Form der Speicherung - es wird Verwirrung vermieden. Ja, wir können das nächste Element oder die nächsten Daten vom nächsten Speicherplatz der Array-Liste abrufen. es wird jedoch mit Hilfe von Zeigern in der verknüpften Liste gespeichert. Hier benötigen wir zwei Speicherplätze - einen für die Daten, den anderen für den Zeiger. Ein Zeiger adressiert den Speicherplatz der nächsten Daten. Wir können leicht verstehen, dass die verknüpfte Liste niemals Daten sequentiell speichert. es verwendet vielmehr einen Zufallsspeichermechanismus. Die Zeiger sind die Schlüsselelemente zum Auffinden der Datenorte im Speicher.

Dynamisches Array und verknüpfte Liste

Wir haben bereits diskutiert, wie beide Speichermechanismen Daten einfügen, und wir können einen Begriff "dynamisches Array" für das interne Speicherschema der Array-Liste angeben. Es werden nur Datenstücke nacheinander eingefügt - und zwar der Name -, während die Verknüpfte Liste eine interne Liste mit Hilfe von Zeigern verwendet, um das nächste Element zu verfolgen. Daher verwendet es eine interne verknüpfte Liste, beispielsweise eine einfach oder doppelt verknüpfte Liste, um uns die nächsten Daten anzuzeigen.

Speichernutzung

Da die Array-Liste nur die tatsächlichen Daten speichert, benötigen wir nur Platz 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 beansprucht als die Array-Liste. Eine vorteilhafte Seite der Linked-Liste ist, dass im Gegensatz zu der Array-Liste niemals fortlaufende Speicherorte zum Speichern unserer Daten erforderlich sind. Die Zeiger sind in der Lage, die Position des nächsten Datenorts zu 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 Verknüpften Liste, ebenso wie deren Wirksamkeit.

Größe der anfänglichen Array-Liste und der verknüpften Liste

Bei der Array-Liste ist selbst für eine leere Liste eine Größe von 10 erforderlich. Bei einer Linked-Liste benötigen wir jedoch keinen so großen Speicherplatz. Wir können eine leere Verknüpfte Liste mit einer Größe von 0 erstellen. Später können wir die Größe bei Bedarf vergrößern.

Datenabruf

Der Datenabruf ist in der Array-Liste einfacher, da er sequentiell gespeichert wird. Alles, was es tut, ist, den ersten Datenort zu identifizieren. Von dort aus wird der nächste Ort sequentiell aufgerufen, um den Rest abzurufen. Es berechnet 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 Datenort zu finden, und verweist von dort auf den Zeiger, der jedem Datenwert zugeordnet ist, um den nächsten Datenort zu finden. Der Abrufprozess ist hauptsächlich von den Zeigern abhängig und zeigt uns effektiv den nächsten Datenort.

Ende der Daten

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

Reverse Traversal

Die Verknüpfte Liste ermöglicht es uns, mit Hilfe von descendingiterator () in die umgekehrten Richtungen zu fahren. Wir haben jedoch keine solche Möglichkeit in einer Array-Liste - Reverse Traversal wird hier zum Problem.

Syntax

Betrachten wir die Java-Syntax beider Speichermechanismen.

Array-Listenerstellung:

Liste arraylistsample = new ArrayList ();

Objekte zur Array-Liste hinzufügen:

Arraylistsample.add ("name1");

Arraylistsample.add ("name2");

So sieht die resultierende Array-Liste aus - [Name1, Name2].

Verknüpfte Listenerstellung:

Liste linkedlistsample = neue linkedList ();

Objekte zur verknüpften Liste hinzufügen:

Linkedlistsample.add ("name3");

Linkedlistsample.add ("name4");

So sieht die resultierende verknüpfte Liste aus - [Name3, Name4].

 Welches ist besser für die Get- oder Search-Operation?

Die Array-Liste benötigt O (1) Zeit, um eine Datensuche auszuführen, während die Linked-Liste u O (n) für das n benötigt^th Datensuche. Daher verwendet eine Array-Liste immer eine konstante Zeit für die Datensuche. In der Linked-Liste hängt die Zeit jedoch von der Position der Daten ab. Daher sind Array-Listen immer eine bessere Wahl für Abruf- oder Suchoperationen.

Welches ist besser für das Einfügen oder das Hinzufügen?

Sowohl die Array-Liste als auch die Verknüpfte Liste benötigen O (1) -Zeit für das Hinzufügen von Daten. Wenn das Array jedoch voll ist, benötigt die Array-Liste viel Zeit, um die Größe des Arrays zu ändern und die Elemente in das neuere zu kopieren. In diesem Fall ist die Verknüpfte Liste die bessere Wahl.

Welches ist besser für den Remove-Vorgang?

Der Vorgang zum Entfernen dauert sowohl in der Array-Liste als auch in der Linked-Liste fast dieselbe Zeit. In der Array-Liste löscht dieser Vorgang die Daten und verschiebt dann die Position der Daten, um das neuere Array zu bilden. Dies dauert O (n) Zeit. In der verknüpften Liste wird dieser Vorgang zu den jeweiligen Daten verschoben und die Zeigerpositionen werden so geändert, dass die neuere Liste entsteht. Die Zeit für die Durchquerung und die Entfernung ist auch hier O (n).

Welche ist schneller?

Wir wissen, dass eine Array-Liste ein internes Array verwendet, um die tatsächlichen Daten zu speichern. Wenn also Daten gelöscht werden, müssen alle anstehenden Daten umgedreht werden. Dies erfordert natürlich viel Zeit und verlangsamt die Dinge. Eine solche Speicherverschiebung ist in der Linked-Liste nicht erforderlich, da sie lediglich 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. H. Für die Abruf- oder Suchoperation benötigt die verknüpfte Liste viel mehr Zeit als eine Array-Liste. Wenn wir die Gesamtleistung betrachten, können wir sagen, dass die verknüpfte 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. Wenn wir jedoch mit großen Datenmengen umgehen, werden durch die Verfügbarkeit von Dauerspeicher die Datenspeichermechanismen implementiert, unabhängig davon, ob sie klein oder groß sind. Als Nächstes entscheiden Sie sich für die Auswahl - die Array-Liste oder die Verknüpfte Liste. Sie können mit einer Array-Liste fortfahren, wenn Sie nur Daten speichern und abrufen möchten. Eine Liste kann Ihnen jedoch weiterhelfen, indem Sie Daten bearbeiten. Wenn Sie sich entschieden haben, wie häufig Daten manipuliert werden müssen, müssen Sie unbedingt prüfen, welche Art von Datenabruf Sie normalerweise ausführen. Wenn es sich lediglich um Abrufen oder Suchen handelt, ist die Array-Liste die bessere Wahl. Für andere Vorgänge wie Einfügen oder Löschen fahren Sie mit der Verknüpften Liste fort.

Lassen Sie uns die Unterschiede in Tabellenform betrachten.

S.Nr	Konzepte	Unterschiede
		Anordnungsliste	Verknüpfte Liste
1	Datenspeicherung Mode	Verwendet sequentielle Datenspeicherung	Verwendet nicht sequentiellen Datenspeicher
2	Internes Speicherschema	Behält ein internes dynamisches Array bei	Verwaltet eine verknüpfte Liste
3	Speichernutzung	Benötigt Speicherplatz nur für die Daten	Erfordert Speicherplatz für Daten sowie für Zeiger
4	Größe der Ausgangsliste	Benötigt Platz für mindestens 10 Artikel	Benötigt keinen Platz und wir können sogar eine leere Liste mit der Größe 0 erstellen.
5	Datenabruf	Berechnet wie die erste Datenposition + 'n', wobei 'n' die Reihenfolge der Daten in der Array-Liste ist	Eine Durchquerung von der ersten oder letzten bis zu den erforderlichen Daten ist erforderlich
6	Ende der Daten	Die Nullwerte markieren das Ende	Der Nullzeiger markiert das Ende
7	Reverse Traversal	Erlaubt es nicht	Erlaubt es mit Hilfe von descendingiterator ()
8	Syntax für die Listenerstellung	Liste arraylistsample = new ArrayList ();	Liste linkedlistsample = neue linkedList ();
9	Objekte hinzufügen	Arraylistsample.add ("name1");	Linkedlistsample.add ("name3");
10	Holen Sie sich oder suchen Sie	Nimmt O (1) Zeit in Anspruch und ist leistungsstärker	Nimmt Zeit in Anspruch (n) und die Leistung hängt von der Position der Daten ab
11	Einfügen oder Hinzufügen	Verbraucht O (1) Zeit, außer wenn das Array voll ist	Verbraucht unter allen Umständen 0 (1) Zeit
12	Löschung oder Entfernung	Braucht O (n) Zeit	Braucht O (n) Zeit
13	Wann verwenden??	Wenn es viele Abruf- oder Suchvorgänge gibt; Die Speicherverfügbarkeit sollte schon zu Beginn höher sein	Wenn es viele Einfüge- oder Löschvorgänge gibt und die Speicherverfügbarkeit nicht kontinuierlich sein muss