Array vs Linked List – Verschil tussen Array en Linked List

Ooit afgevraagd, hoe gegevens worden opgeslagen in het geheugen van de computer? Je kunt niet zomaar gegevens in het geheugen gooien zonder een goede structuur voor de gegevens te maken.

Om een georganiseerde structuur voor de gegevens in het geheugen van de computer op te slaan, zodat we de opgeslagen gegevens op de meest efficiënte manier kunnen gebruiken en beheren, gebruiken we Data Structures.

Alle programmeertalen bieden fundamentele gegevensstructuren zoals int, char, float enz. om de primitieve type waarden op te slaan. Maar met behulp van door de gebruiker gedefinieerde gegevenstypen kunnen we gegevensstructuur creëren zoals vereist. Het is net als het maken van ons huis met bakstenen, we kunnen elk type structuur maken die we willen.

Hier in dit artikel zullen we twee meest gebruikte door de gebruiker gedefinieerde datatypen zien: Arrays en Linked List, Verschil tussen Array en Linked List en hun implementatie.

Array

Het eenvoudigste type datastructuur is Array dat wordt gebruikt om set van soortgelijke gegevens op te slaan in continue blokken geheugen onder een gemeenschappelijke kop of variabele naam. De eenvoud brengt enkele belemmeringen met zich mee, zoals het feit dat er continu blokken geheugen nodig zijn en als er geen vrij geheugen beschikbaar is in aaneengesloten blokken, wordt het inefficiënt om arrays te gebruiken.

Array Representation

Array Representation (Source)

Arrays indexeren begint met 0, en elk element van de array kan worden benaderd met behulp van zijn index. De werking op een array is zeer snel, omdat elk element direct toegankelijk is met behulp van array-indexering. De naam van de array is het basisadres van de array en alle andere elementen kunnen worden benaderd met behulp van het basisadres, omdat het geheugen dat aan de array is toegewezen opeenvolgend is.

Linked List

Aan de andere kant is Linked List een eenvoudige maar zeer bruikbare gegevensstructuur die geen aaneengesloten blokken geheugen nodig heeft. Zij worden gebruikt in situaties waarin het nodig is dynamisch geheugen toe te wijzen, dat wil zeggen tijdens de runtime van een programma. Het kan worden gevisualiseerd als een trein met een locomotief (hoofd) en alle wagons (knooppunten) die direct of indirect via andere wagons met de locomotief zijn verbonden.

Linked list Representation

Linked list Representation (Source)

Linked list is een door de gebruiker gedefinieerd gegevenstype waarbij alle knooppunten van de lijst met elkaar zijn verbonden via pointers. Om toegang te krijgen tot een knooppunt van de lijst, moeten we de lijst lineair doorkruisen, in tegenstelling tot array, waar we direct toegang hebben tot de elementen.

Array vs. Gekoppelde lijst – Verschil tussen Array en Gekoppelde lijst

Parameters Array Gekoppelde lijst
Definitie Het is een verzameling elementen van hetzelfde gegevenstype met een gemeenschappelijke naam. Het is een geordende verzameling van elementen die met elkaar verbonden zijn door links of pointers.
Size Vast, kan eenmaal gedeclareerd niet worden gewijzigd. Variabel, kan tijdens run-time worden gewijzigd.
Geheugentoewijzing Eis aaneengesloten blokken geheugen. Random geheugen kan worden toegewezen.
Toegang Directe of willekeurige toegang, d.w.z., Geef de array-index of subscript op. Sequentieel benaderd, d.w.z., Traverse vanaf de eerste node in de lijst door de pointer.
Insertion and Deletion Ratief traag, omdat voor het invoegen of verwijderen van een element, andere elementen moeten worden verschoven om de lege ruimte in te nemen of ruimte te maken. Sneller, eenvoudiger en efficiënter, omdat alleen het koppelen of ontkoppelen van node vereist is.
Zoeken Binair zoeken en Lineair zoeken Lineair zoeken
Extra ruimte Extra ruimte is niet nodig. Om knooppunten van lijst te koppelen, worden pointers gebruikt die extra ruimte vergen.
Gebruik van geheugen Inefficiënt Efficiënt
Types Het kan een eendimensionale, tweedimensionale of multidimensionale lijst zijn. Het kan een enkelvoudig, dubbelvoudig of cirkelvormig gekoppelde lijst zijn.

Array Implementatie 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; // declaratie van een integer array van grootte 5
arr=5; // toekennen van waarden aan de array-elementen
arr=4; // merk op dat array-indexering begint bij 0 en eindigt bij grootte-1
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i++)
cout<<arr<<” “; // afdrukken van array-elementen
return 0;
}

Output

5 4 3 2 1

Linked List Implementation 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;
/* Creëert een door de gebruiker gedefinieerde structuur voor het opslaan van gegevens in een gekoppelde lijst */
struct Node
{
int data;
struct Node *next; // pointer naar gekoppelde nodes van de lijst
};
struct Node* head = NULL; // Initieel is er geen element in de lijst, dus head wijst nergens naar
/* functie om nodes in de lijst in te voegen en te linken */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // dynamisch geheugen toewijzen
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* functie om gegevens van de lijst weer te geven */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<” “;
ptr = ptr->next;
}
}
int main()
{
insert(5); // gegevens invoegen in de lijst
insert(1);
insert(4);
insert(6);
insert(7);
cout<<“De gekoppelde lijst is: “;
display();
return 0;
}

Output

De gekoppelde lijst is: 7 6 4 1 5

Video Tutorial

Leave a Reply

Geef een antwoord

Het e-mailadres wordt niet gepubliceerd.