Array vs Linked List – Unterschied zwischen Array und Linked List

Haben Sie sich schon einmal gefragt, wie Daten im Speicher des Computers gespeichert werden? Man kann nicht einfach Daten in den Speicher werfen, ohne eine geeignete Struktur für die Daten zu schaffen.

Um eine geordnete Struktur für die Daten zu schaffen, die im Speicher des Computers gespeichert werden sollen, so dass wir die gespeicherten Daten so effizient wie möglich verwenden und verwalten können, verwenden wir Datenstrukturen.

Alle Programmiersprachen bieten grundlegende Datenstrukturen wie int, char, float usw., um die primitiven Werte zu speichern. Aber mit der Verwendung von benutzerdefinierten Datentypen können wir Datenstrukturen nach Bedarf erstellen. Es ist so, als ob wir unser Haus mit Ziegelsteinen bauen würden, wir können jede Art von Struktur erstellen, die wir wollen.

In diesem Artikel werden wir zwei der am häufigsten verwendeten benutzerdefinierten Datentypen sehen: Arrays und Linked List, den Unterschied zwischen Array und Linked List und ihre Implementierung.

Array

Der einfachste Typ von Datenstruktur ist Array, der verwendet wird, um eine Menge ähnlicher Daten in kontinuierlichen Speicherblöcken unter einem gemeinsamen Titel oder Variablennamen zu speichern. Mit seiner Einfachheit kommen einige Hindernisse, wie z.B. die Notwendigkeit eines kontinuierlichen Speicherblocks, und wenn kein freier Speicher in einem zusammenhängenden Block verfügbar ist, wird die Verwendung von Arrays ineffizient.

Array-Darstellung

Array-Darstellung (Quelle)

Die Indizierung von Arrays beginnt bei 0, und auf jedes Element des Arrays kann über seinen Index zugegriffen werden. Die Operation auf einem Array ist sehr schnell, da auf jedes Element direkt über die Array-Indizierung zugegriffen werden kann. Der Name des Arrays ist die Basisadresse des Arrays und auf alle anderen Elemente kann über die Basisadresse zugegriffen werden, da der dem Array zugewiesene Speicher fortlaufend ist.

Verknüpfte Liste

Eine einfache, aber sehr nützliche Datenstruktur, die keine zusammenhängenden Speicherblöcke benötigt, ist die verknüpfte Liste. Sie werden in Situationen verwendet, in denen Speicher dynamisch zugewiesen werden muss, d.h. während der Laufzeit eines Programms. Man kann sie sich wie einen Zug vorstellen, bei dem es eine Lokomotive (Kopf) gibt und alle Waggons (Knoten) entweder direkt oder indirekt über andere Waggons mit der Lokomotive verbunden sind.

Verknüpfte Listendarstellung

Verknüpfte Listendarstellung (Quelle)

Verknüpfte Listen sind benutzerdefinierte Datentypen, bei denen alle Knoten der Liste mit Zeigern verbunden sind. Um auf einen beliebigen Knoten der Liste zuzugreifen, muss die Liste linear durchlaufen werden, im Gegensatz zu einem Array, bei dem ein direkter Zugriff auf die Elemente möglich ist.

Array vs Linked List – Unterschied zwischen Array und Linked List

Parameter Array Linked List
Definition Es handelt sich um eine Sammlung von Elementen gleichen Datentyps mit einem gemeinsamen Namen. Es ist eine geordnete Sammlung von Elementen, die durch Links oder Zeiger verbunden sind.
Größe Fest, einmal deklariert, kann nicht geändert werden. Variabel, kann während der Laufzeit geändert werden.
Speicherzuweisung Erfordern zusammenhängende Speicherblöcke. Zufälliger Speicher kann zugewiesen werden.
Zugriff Direkter oder zufälliger Zugriff, d.h., Geben Sie den Array-Index oder Subscript an. Sequentieller Zugriff, d.h., Traverse ab dem ersten Knoten in der Liste durch den Zeiger.
Einfügen und Löschen Relativ langsam, da zum Einfügen oder Löschen eines Elements andere Elemente verschoben werden müssen, um den leeren Platz zu besetzen oder Platz zu schaffen. Schneller, einfacher und effizienter, da nur das Verknüpfen oder Entknüpfen von Knoten erforderlich ist.
Suchen Binärsuche und Lineare Suche Lineare Suche
Extra Space Extra Space wird nicht benötigt. Um Knoten der Liste zu verknüpfen, werden Zeiger verwendet, die extra Space benötigen.
Speicherauslastung Ineffizient Effizient
Typen Eindimensional, zweidimensional oder mehrdimensional kann sie sein. Einfach, doppelt oder zirkulär verkettet kann sie sein.

Array Implementation in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;
int main()
{
int arr; // Deklaration eines Integer-Arrays der Größe 5
arr=5; // Zuweisung von Werten zu den Array-Elementen
arr=4; // beachte, dass die Array-Indizierung bei 0 beginnt und bei Größe-1 endet
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i++)
cout<<arr<<“ „; // Drucken der Array-Elemente
return 0;
}

Ausgabe

5 4 3 2 1

Verknüpfte Listenimplementierung in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include<iostream>
using namespace std;
/* Erstellen einer benutzerdefinierten Struktur zum Speichern von Daten in einer verknüpften Liste */
struct Node
{
int data;
struct Node *next; // Zeiger auf die Verknüpfungsknoten der Liste
};
struct Node* head = NULL; // Am Anfang ist kein Element in der Liste, also zeigt head ins Leere
/* Funktion zum Einfügen und Verknüpfen von Knoten in die Liste */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // Speicher dynamisch allozieren
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* Funktion zum Anzeigen der Daten der Liste */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<“ „;
ptr = ptr->next;
}
}
int main()
{
insert(5); // Einfügen von Daten in die Liste
insert(1);
insert(4);
insert(6);
insert(7);
cout<<„The linked list is: „;
display();
return 0;
}

Output

Die verknüpfte Liste ist: 7 6 4 1 5

Video Tutorial

Leave a Reply

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.