Array vs Linked List – Forskellen mellem Array og Linked List

Har du nogensinde undret dig over, hvordan data gemmes i computerens hukommelse? Du kan ikke bare smide data i hukommelsen uden at lave en ordentlig struktur for dataene.

For at give en organiseret struktur for dataene til at blive gemt inde i computerens hukommelse, så vi kan bruge og administrere de gemte data på den mest effektive måde, bruger vi datastrukturer.

Alle programmeringssprog giver grundlæggende datastrukturer som int, char, float osv. til at gemme de primitive typeværdier. Men ved hjælp af brugerdefinerede datatyper kan vi oprette datastrukturer efter behov. Det er ligesom at skabe vores hjem med mursten, vi kan lave enhver type struktur, vi ønsker.

Her i denne artikel vil vi se de to mest almindeligt anvendte brugerdefinerede datatyper: Arrays og Linked List, forskellen mellem Array og Linked List og deres implementering.

Array

Den enkleste type datastruktur er Array, som bruges til at gemme sæt af lignende data i kontinuerlige blokke af hukommelse under en fælles overskrift eller variabelnavn. Med dens enkelhed følger nogle barrierer som f.eks. at den har brug for en kontinuerlig blok af hukommelse, og hvis der ikke er ledig hukommelse til rådighed i sammenhængende blokke, bliver det ineffektivt at bruge arrays.

Arrayrepræsentation

Arrayrepræsentation (kilde)

Arrays indeksering starter med 0, og hvert element i arrayet kan tilgås ved hjælp af dets indeks. Operationen på array er meget hurtig, da der er direkte adgang til ethvert element ved hjælp af array-indeksering. Arrays navn er arrayets basisadresse, og alle andre elementer kan tilgås ved hjælp af basisadressen, fordi den hukommelse, der er allokeret til arrayet, er fortløbende.

Linked List

På den anden side er Linked List en simpel, men meget nyttig datastruktur, som ikke har brug for sammenhængende blokke af hukommelse. De bruges i situationer, hvor der er behov for at allokere hukommelse dynamisk, dvs. i løbet af et programs køretid. Det kan visualiseres som et tog, hvor vi har en motor (hoved), og alle vogne (knuder) er knyttet til togmotoren enten direkte eller indirekte gennem andre vogne.

Linked list Repræsentation

Linked list Repræsentation (Kilde)

Linked list er en brugerdefineret datatype, hvor alle knuder i listen er knyttet ved hjælp af pointere. For at få adgang til en hvilken som helst node i listen skal vi gennemløbe listen lineært i modsætning til array, hvor vi kan få direkte adgang til elementerne.

Array vs Linked List – Forskellen mellem Array og Linked List

Parametre Array Linked List
Definition Det er en samling af elementer, der har samme datatype med et fælles navn. Det er en ordnet samling af elementer, der er forbundet med links eller pointere.
Størrelse Fikseret, kan ikke ændres, når den først er deklareret. Variabel, kan ændres under kørselstiden.
Hukommelsesallokering Kræver sammenhængende blokke af hukommelse. Lukket hukommelse kan allokeres.
Access Direkte eller tilfældigt tilgået, dvs, Angiv arrayindeks eller subscript. Sekvent adgang, dvs, Traverse fra den første node i listen ved hjælp af pointeren.
Indsætning og sletning Relativt langsomt, da der for at indsætte eller slette et element skal andre elementer flyttes for at besætte den tomme plads eller skabe plads. Snavere, nemmere og mere effektivt, da der kun kræves linking eller unlinking af node.
Søgning Binær søgning og lineær søgning Linær søgning
Ekstra plads Ekstra plads er ikke nødvendig. For at linke noder i listen bruges pointers, som kræver ekstra plads.
Hukommelsesudnyttelse Ineffektiv Effektiv
Typer Den kan være endimensional, todimensional eller flerdimensional. Den kan være enkeltvis, dobbeltvis eller cirkulært linket liste.

Array-implementering i 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 af et heltals array af størrelse 5
arr=5; // tildeling af værdier til arrayelementerne
arr=4; // bemærk, at array-indeksering starter fra 0 og slutter ved størrelse-1
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i++)
cout<<<arr<<<” “; // udskrivning af array-elementer
return 0;
}

Output

5 4 3 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;
/* Oprettelse af brugerdefineret struktur til lagring af data i linket liste */
struct Node
{
int data;
struct Node *next; // pegepind til link noder i listen
};
struct Node* head = NULL; // I første omgang er der intet element i listen, så head peger ingen steder hen
/* funktion til at indsætte og linke knuder i listen */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // allokering af hukommelse dynamisk
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* funktion til visning af data i listen */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<” ” “;
ptr = ptr->næste;
}
}
int main()
{
insert(5); // indsætter data i listen
insert(1);
insert(4);
insert(6);
insert(7);
insert(7);
cout<<“Den sammenkædede liste er: “;
display();
return 0;
}

Output

Den sammenkædede liste er: “;

Den sammenkædede liste er: “: 7 6 4 4 1 5

Videovejledning

Leave a Reply

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.