Unterschied zwischen Arrayliste und verknüpfter Liste

Wie werden Daten gespeichert??

Array -Liste und verknüpfte Liste sind häufig. Obwohl es viele Speichergeräte gibt, hängen sie letztendlich vom Speichermechanismus ab. Diese beiden Speichermechanismen legen Ihre Daten in die Speichergeräte ein und holen Sie sie bei Bedarf ab. Schauen wir uns an, wie sie Daten in ihrem Speicher speichern. Die Array -Liste verwendet einen sequentiellen Speicher, und die Datenstücke werden nacheinander gespeichert. Dies ist vielleicht eine einfachere Form des Speichers - sie 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 mit Hilfe von Zeigern in der verlinkten Liste gespeichert. Hier benötigen wir zwei Speicherorte für Speicherplatz - einen für die Daten, die andere für den Zeiger. Ein Zeiger befasst sich mit dem Speicherort der nächsten Daten. Wir können leicht verstehen, dass die verknüpfte Liste Daten niemals nacheinander speichert. Vielmehr verwendet es einen zufälligen Speichermechanismus. Die Zeiger sind die Schlüsselelemente beim Lokalisieren der Datenorte im Speicher.

Dynamisches Array und verknüpfte Liste

Wir haben bereits diskutiert, wie beide Speichermechanismen in Daten einfügen und ein Begriff "dynamisches Array" für das interne Speicherschema der Array -Liste angeben können. Es werden nur Datenstücke nach dem anderen - daher der Name - angezeigt, während die verknüpfte Liste eine interne Liste mit Hilfe von Zeigern verwendet, um das nächste Element zu verfolgen. Daher wird eine interne verlinkte Liste verwendet, wie eine einzig 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 von uns gespeicherten Daten. Umgekehrt verwenden wir in der verlinkten Liste auch Zeiger. Daher sind zwei Speicherorte erforderlich, und wir können sagen, dass die verknüpfte Liste mehr Speicher als die Array -Liste verbraucht. Eine vorteilhafte Seite der verknüpften Liste ist, dass sie niemals kontinuierliche Speicherorte benötigt, um unsere Daten zu speichern, im Gegensatz zur Array -Liste. Die Zeiger sind in der Lage, die Position des nächsten Datenorts zu halten, und wir können sogar kleinere Speicherplätze verwenden, die nicht kontinuierlich sind. In Bezug.

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

Mit der Array -Liste erfordert auch eine leere Liste eine Größe von 10, aber mit einer verknüpften Liste benötigen wir keinen so großen Platz. Wir können eine leere verknüpfte Liste mit einer Größe von 0 erstellen. Später können wir die Größe nach Bedarf erhöhen.

Datenabruf

Das Abrufen von Daten ist in der Array -Liste einfacher, da sie nacheinander gespeichert sind. Es identifiziert nur den ersten Datenort. Von dort aus wird auf den nächsten Ort nacheinander zugegriffen, 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 den ersten Zeiger, um den ersten Datenort zu finden, und von dort aus verweist sie den Zeiger, der jeder Daten zugeordnet ist, um den nächsten Datenort zu finden. Der Abrufprozess hängt hauptsächlich von den Zeigern hier ab und zeigt uns effektiv den nächsten Datenort.

Datenende

Die Array -Liste verwendet einen Nullwert, um das Ende der Daten zu markieren, während die verknüpfte Liste für diesen Zweck einen Nullzeiger verwendet. Sobald das System Nulldaten erkennt, stoppt die Array -Liste das nächste Datenabruf. In ähnlicher Weise verhindert der Nullzeiger das System daran, mit dem nächsten Datenabruf fortzufahren.

Rückwärtsfahrung

Die verknüpfte Liste ermöglicht es uns, mit Hilfe von DescendingIterator () in die umgekehrte Richtungen zu durchlaufen (). Wir haben jedoch keine solche Einrichtung in einer Array -Liste - Reverse -Traversal wird hier zu einem Problem.

Syntax

Schauen wir uns die Java -Syntax beider Speichermechanismen an.

Erstellung von Array -Listen:

Listen arraynlistample = new ArrayList ();

Hinzufügen von Objekten zur Array -Liste:

ArrayLists tample.add ("name1");

ArrayLists tample.add ("name2");

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

Linked List -Erstellung:

LIST LINKEDLISTSample = new LinkedList ();

Hinzufügen von Objekten zur verlinkten Liste:

LinkedListsample.add ("name3");

LinkedListsample.add ("name4");

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

 Welches ist besser für die Get- oder Suchoperation?

Die Array -Liste dauert O (1) Zeit, um eine Datensuche auszuführen, während die verknüpfte Liste u o (n) für die n nimmt^th Datensuche. Daher verwendet eine Array -Liste immer eine konstante Zeit für jede Datensuche, aber in der verknüpften Liste hängt die Zeit für die Position der Daten ab. Daher sind Array -Listen immer eine bessere Wahl für Get- oder Suchvorgänge.

Das ist besser für den Einfügen oder den Zusatzbetrieb?

Sowohl die Array -Liste als auch die verknüpfte Liste nehmen o (1) Zeit für die Datenerweiterung. Wenn das Array jedoch voll ist, braucht die Array -Liste eine beträchtliche Zeit, um die Größe zu ändern und die Elemente in die neuere zu kopieren. In einem solchen Fall ist die verknüpfte Liste die bessere Wahl.

Welches ist besser für den Entfernungsvorgang?

Die Operation von Entfernen nimmt in der Array -Liste und der verknüpften Liste fast die gleiche Zeit in Anspruch. In der Array -Liste löscht diese Operation die Daten und verändert dann die Position der Daten, um das neuere Array zu bilden. Es dauert die Zeit von O (n). In der verknüpften Liste führt dieser Vorgang zu den jeweiligen Daten und ändert sich um Zeigerpositionen, um die neuere Liste zu bilden. Die Zeit für den Traversal 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 Daten gelöscht werden, benötigen alle bevorstehenden Daten eine Speicherverschiebung. Offensichtlich erfordert dies eine beträchtliche Zeit und verlangsamt die Dinge. Eine solche Speicherverschiebung ist in der verknüpften Liste nicht erforderlich, da alles, was es tut, den Zeigerort ändern ist. Daher ist eine verknüpfte Liste schneller als eine Array -Liste in jeder Art von Datenspeicherung. Dies hängt jedoch nur von der Art der Operation ab, ich.e. Für die GET- oder Suchoperation dauert die verknüpfte Liste viel mehr Zeit als eine Array -Liste. Wenn wir uns die Gesamtleistung ansehen, können wir sagen, dass die verknüpfte Liste schneller ist.

Wann verwenden Sie eine Array -Liste und eine verknüpfte Liste?

Eine Array -Liste eignet sich am besten für kleinere Datenanforderungen, bei denen ein kontinuierlicher Speicher verfügbar ist. Wenn wir uns jedoch mit enormen Datenmengen befassen. Entscheiden Sie als Nächst. Sie können eine Array -Liste fortsetzen, wenn Sie nur Speicher und Abrufen von Daten benötigen. Eine Liste kann Ihnen jedoch helfen, indem Sie Daten manipulieren. Sobald Sie entschieden haben, wie häufig Datenmanipulation erforderlich ist, ist es wichtig zu überprüfen, welche Art von Datenabruf Sie normalerweise ausführen. Wenn es sich nur um eine Suche oder Suche handelt, ist die Array -Liste die bessere Wahl. Für andere Operationen wie Insertion oder Löschen finden Sie die verknüpfte Liste.

Schauen wir uns die Unterschiede in der tabellarischen Form an.