Array Und Verlinkte Liste sind die beiden Möglichkeiten, die Daten im Speicher zu organisieren. Bevor Sie die Unterschiede zwischen den verstehen Array und das Verlinkte Liste , wir schauen zuerst in einem Array Und eine verknüpfte Liste .
Verzeichnisnamen unter Linux ändern
Was ist ein Array?
Eine Datenstruktur, die Elemente desselben Typs enthält. Eine Datenstruktur ist eine Möglichkeit, die Daten zu organisieren. Ein Array ist eine Datenstruktur, da es die Daten sequentiell organisiert. Ein Array ist ein großer Speicherblock, in dem der Speicher in kleine Blöcke unterteilt ist und jeder Block einen bestimmten Wert speichern kann.
Angenommen, wir haben ein Array erstellt, das aus 10 Werten besteht, dann speichert jeder Block den Wert eines Ganzzahltyps. Wenn wir versuchen, den Wert in einem Array unterschiedlicher Typen zu speichern, handelt es sich nicht um ein korrektes Array und es wird ein Fehler bei der Kompilierung ausgegeben.
Array-Deklaration
Ein Array kann wie folgt deklariert werden:
data_type name of the array[no of elements]
Um ein Array zu deklarieren, müssen wir zunächst den Typ des Arrays und dann den Namen des Arrays angeben. Innerhalb der eckigen Klammern müssen wir die Anzahl der Elemente angeben, die unser Array enthalten soll.
Lassen Sie es uns anhand eines Beispiels verstehen.
int a[5];
Im obigen Fall haben wir ein Array aus 5 Elementen mit ' deklariert A ' Name eines ganze Zahl Datentyp.
Was ist eine verknüpfte Liste?
Eine verknüpfte Liste ist die Sammlung von Knoten, die zufällig gespeichert werden. Jeder Knoten besteht aus zwei Feldern, d. h. Daten Und Verknüpfung . Hier sind Daten der Wert, der an diesem bestimmten Knoten gespeichert ist, und der Link ist der Zeiger, der die Adresse des nächsten Knotens enthält.
Unterschiede zwischen Array und verknüpfter Liste
Wir können nicht sagen, welche Datenstruktur besser ist, also Array oder verlinkte Liste . Es besteht die Möglichkeit, dass eine Datenstruktur für eine Art von Anforderung besser ist, während die andere Datenstruktur für eine andere Art von Anforderung besser ist. Es gibt verschiedene Faktoren, wie z. B. die häufigen Operationen, die an der Datenstruktur ausgeführt werden, die Größe der Daten und andere Faktoren, auf deren Grundlage die Datenstruktur ausgewählt wird. Jetzt werden wir einige Unterschiede zwischen dem Array und der verknüpften Liste sehen, die auf einigen Parametern basieren.
1. Kosten für den Zugriff auf ein Element
Im Falle eines Arrays benötigt ein Array unabhängig von seiner Größe eine konstante Zeit für den Zugriff auf ein Element. In einem Array werden die Elemente zusammenhängend gespeichert. Wenn wir also die Basisadresse des Elements kennen, können wir leicht die Adresse jedes Elements in einem Array ermitteln. Wir müssen eine einfache Berechnung durchführen, um die Adresse eines beliebigen Elements in einem Array zu erhalten. Der Zugriff auf das Element in einem Array ist also O(1) in Bezug auf die zeitliche Komplexität.
In der verknüpften Liste werden die Elemente nicht zusammenhängend gespeichert. Es besteht aus mehreren Blöcken und jeder Block wird als Knoten dargestellt. Jeder Knoten hat zwei Felder, d. h. eines ist für das Datenfeld und ein anderes speichert die Adresse des nächsten Knotens. Um einen Knoten in der verknüpften Liste zu finden, müssen wir zunächst den ersten Knoten bestimmen, der als Kopfknoten bezeichnet wird. Wenn wir den zweiten Knoten in der Liste finden müssen, müssen wir vom ersten Knoten aus durchlaufen, und im schlimmsten Fall müssen wir alle Knoten durchlaufen, um den letzten Knoten zu finden. Der durchschnittliche Fall für den Zugriff auf das Element ist O(n).
Wir kommen zu dem Schluss, dass die Kosten für den Zugriff auf ein Element im Array geringer sind als für den Zugriff auf die verknüpfte Liste. Wenn wir also auf die Elemente zugreifen müssen, ist Array die bessere Wahl.
alle 4 Monate
2. Kosten für das Einfügen eines Elements
Bei der Einfügung kann es drei Szenarien geben:
Im Falle einer verknüpften Liste erstellen wir zum Einfügen eines Elements am Anfang der verknüpften Liste einen neuen Knoten und fügen die Adresse des ersten Knotens dem neuen Knoten hinzu. Auf diese Weise wird der neue Knoten zum ersten Knoten. Die zeitliche Komplexität ist also nicht proportional zur Größe der Liste. Die Zeitkomplexität wäre konstant, also O(1).
Wenn das Array nicht voll ist, können wir das neue Element direkt über den Index hinzufügen. In diesem Fall wäre die Zeitkomplexität konstant, also O(1). Wenn das Array voll ist, müssen wir es zunächst in ein anderes Array kopieren und ein neues Element hinzufügen. In diesem Fall wäre die Zeitkomplexität O(n).
Um ein Element am Ende der verknüpften Liste einzufügen, müssen wir die gesamte Liste durchlaufen. Wenn die verknüpfte Liste aus n Elementen besteht, wäre die Zeitkomplexität O(n).
Angenommen, wir möchten das Element am i einfügenThPosition des Arrays; wir müssen die n/2 Elemente nach rechts verschieben. Daher ist die Zeitkomplexität proportional zur Anzahl der Elemente. Die Zeitkomplexität wäre für den Durchschnittsfall O(n).
Konvertieren Sie einen String in ein JSON-Objekt
Im Fall einer verknüpften Liste müssen wir zu der Position wechseln, an der wir das neue Element einfügen müssen. Obwohl wir keine Verschiebung durchführen müssen, müssen wir zur n/2-Position verfahren. Die benötigte Zeit ist proportional zur n-Anzahl der Elemente und die Zeitkomplexität für den Durchschnittsfall wäre O(n).
Die resultierende verknüpfte Liste lautet:
Die Implementierung eines Arrays ist im Vergleich zur verknüpften Liste einfach. Beim Erstellen eines Programms mithilfe einer verknüpften Liste ist das Programm anfälliger für Fehler wie Segmentierungsfehler oder Speicherverlust. Beim Erstellen eines Programms in der verknüpften Liste ist daher große Sorgfalt geboten.
Die Größe der verknüpften Liste ist dynamisch, während das Array statisch ist. Statisch bedeutet hier nicht, dass wir die Größe zur Laufzeit nicht festlegen können, aber wir können sie nicht ändern, sobald die Größe festgelegt ist.
3. Speicherbedarf
Da die Elemente in einem Array in einem zusammenhängenden Speicherblock gespeichert werden, hat das Array eine feste Größe. Angenommen, wir haben ein Array der Größe 7 und das Array besteht aus 4 Elementen, dann bleibt der Rest des Platzes ungenutzt. Der von den 7 Elementen belegte Speicher:
Speicherplatz = 7*4 = 28 Bytes
Dabei ist 7 die Anzahl der Elemente in einem Array und 4 die Anzahl der Bytes eines Ganzzahltyps.
Im Falle einer verknüpften Liste gibt es keinen ungenutzten Speicher, sondern der zusätzliche Speicher wird von den Zeigervariablen belegt. Wenn es sich bei den Daten um Ganzzahldaten handelt, beträgt der von einem Knoten insgesamt belegte Speicher 8 Bytes, d. h. 4 Bytes für Daten und 4 Bytes für Zeigervariablen. Wenn die verknüpfte Liste aus 4 Elementen besteht, beträgt der von der verknüpften Liste belegte Speicherplatz:
Webtreiber
Speicherplatz = 8*4 = 32 Bytes
Die verknüpfte Liste wäre die bessere Wahl, wenn der Datenteil größer ist. Angenommen, die Daten umfassen 16 Byte. Der vom Array belegte Speicherplatz beträgt 16*7=112 Bytes, während die verknüpfte Liste 20*4=80 belegt. Hier haben wir 20 Bytes als 16 Bytes für die Größe der Daten plus 4 Bytes für die Zeigervariable angegeben. Wenn wir eine größere Datenmenge wählen, würde die verknüpfte Liste weniger Speicher verbrauchen; andernfalls hängt es von den Faktoren ab, die wir zur Bestimmung der Größe heranziehen.
Schauen wir uns die Unterschiede zwischen dem Array und der verknüpften Liste in tabellarischer Form an.
| Array | Verlinkte Liste |
|---|---|
| Ein Array ist eine Sammlung von Elementen eines ähnlichen Datentyps. | Eine verknüpfte Liste ist eine Sammlung von Objekten, die als Knoten bezeichnet werden, wobei der Knoten aus zwei Teilen besteht, nämlich Daten und Adresse. |
| Array-Elemente werden an einem zusammenhängenden Speicherort gespeichert. | Verknüpfte Listenelemente können an einer beliebigen Stelle im Speicher oder zufällig gespeichert werden. |
| Array arbeitet mit einem statischen Speicher. Statischer Speicher bedeutet hier, dass die Speichergröße fest ist und zur Laufzeit nicht geändert werden kann. | Die verknüpfte Liste arbeitet mit dynamischem Speicher. Dynamischer Speicher bedeutet hier, dass die Speichergröße zur Laufzeit entsprechend unseren Anforderungen geändert werden kann. |
| Array-Elemente sind voneinander unabhängig. | Verknüpfte Listenelemente sind voneinander abhängig. Da jeder Knoten die Adresse des nächsten Knotens enthält, müssen wir zum Zugriff auf den nächsten Knoten auf dessen vorherigen Knoten zugreifen. |
| Das Array benötigt beim Ausführen von Vorgängen wie Einfügen, Löschen usw. mehr Zeit. | Die verknüpfte Liste nimmt beim Durchführen von Vorgängen wie Einfügen, Löschen usw. weniger Zeit in Anspruch. |
| Der Zugriff auf jedes Element in einem Array ist schneller, da auf das Element in einem Array direkt über den Index zugegriffen werden kann. | Der Zugriff auf ein Element in einer verknüpften Liste ist langsamer, da der Durchlauf vom ersten Element der verknüpften Liste aus beginnt. |
| Im Fall eines Arrays wird der Speicher zur Kompilierungszeit zugewiesen. | Im Fall einer verknüpften Liste wird der Speicher zur Laufzeit zugewiesen. |
| Die Speichernutzung im Array ist ineffizient. Wenn die Größe des Arrays beispielsweise 6 beträgt und das Array nur aus 3 Elementen besteht, bleibt der Rest des Platzes ungenutzt. | Die Speichernutzung ist im Fall einer verknüpften Liste effizient, da der Speicher zur Laufzeit entsprechend unseren Anforderungen zugewiesen oder freigegeben werden kann. |