Array vs Linked List – Skillnaden mellan Array och Linked List

Har du någonsin undrat hur data lagras i datorns minne? Du kan inte bara kasta in data i minnet utan att skapa en ordentlig struktur för data.

För att tillhandahålla en organiserad struktur för data som lagras i datorns minne så att vi kan använda och hantera den lagrade datan på ett så effektivt sätt som möjligt använder vi datastrukturer.

Alla programmeringsspråk tillhandahåller grundläggande datastrukturer som int, char, float etc. för att lagra värden av primitiv typ. Men med hjälp av användardefinierade datatyper kan vi skapa datastrukturer efter behov. Det är som att skapa vårt hem med tegelstenar, vi kan skapa vilken typ av struktur som helst.

Här i den här artikeln kommer vi att se två vanligaste användardefinierade datatyper: Arrays och Linked List, skillnaden mellan Array och Linked List och deras implementering.

Array

Den enklaste typen av datastruktur är Array som används för att lagra en uppsättning liknande data i kontinuerliga minnesblock under en gemensam rubrik eller ett gemensamt variabelnamn. Med dess enkelhet följer vissa hinder som att den behöver kontinuerliga block av minne och om ledigt minne inte finns tillgängligt i sammanhängande block blir det ineffektivt att använda matriser.

Matrisrepresentation

Matrisrepresentation (källa)

Matriserna indexeras med 0, och varje element i matrisen kan nås med hjälp av dess index. Operation på array är mycket snabb eftersom varje element kan nås direkt med hjälp av arrayindexering. Namnet på matrisen är matrisens basadress och alla andra element kan nås med hjälp av basadressen eftersom det minne som allokeras till matrisen är sammanhängande.

Länkad lista

En enkel men mycket användbar datastruktur som inte behöver sammanhängande minnesblock är å andra sidan länkad lista. De används i situationer när det finns behov av att allokera minne dynamiskt det vill säga under körning av ett program. Den kan visualiseras som ett tåg där vi har en motor (huvud) och alla vagnar (noder) är länkade till tågmotorn antingen direkt eller indirekt genom andra vagnar.

Länkad lista Representation

Länkad lista Representation (Källa)

Länkad lista är en användardefinierad datatyp där alla noder i listan är länkade med pekare. För att få tillgång till någon nod i listan måste vi gå igenom listan linjärt till skillnad från array där vi kan få direkt tillgång till elementen.

Array vs länkad lista – Skillnaden mellan array och länkad lista

Parametrar Array Länkad lista
Definition Det är en samling av element som har samma datatyp med ett gemensamt namn. Det är en ordnad samling av element som är sammankopplade med länkar eller pekare.
Storlek Fix, när den väl har deklarerats kan den inte ändras. Variabel, kan ändras under körtiden.
Minnesallokering Kräver sammanhängande block av minne. Randomminne kan allokeras.
Åtkomst Direkt eller slumpmässigt åtkomlig, dvs, Ange arrayindex eller subscript. Sekventiell åtkomst, dvs, Genomgång från den första noden i listan med hjälp av pekaren.
Insättning och borttagning Relativt långsamt, eftersom andra element måste flyttas för att ta in eller ta bort ett element för att ta upp det tomma utrymmet eller skapa utrymme. Snabbare, enklare och effektivare, eftersom det räcker med att länka eller avlänka en nod.
Sökning Binär sökning och linjär sökning Linjär sökning
Extra utrymme Extra utrymme behövs inte. För att länka samman noder i en lista används pekare som kräver extra utrymme.
Minnesanvändning Ineffektiv Effektiv
Typer Den kan vara endimensionell, tvådimensionell eller flerdimensionell. Den kan vara singel-, dubbel- eller cirkulärt länkad lista.

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 av en heltalsarray av storlek 5
arr=5; // tilldelning av värden till arrayelementen
arr=4; // observera att indexeringen av matrisen börjar från 0 och slutar vid storlek-1
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i++)
cout<<arr<<” ”; // utskrift av matriselement
return 0;
}

Output

5 4 3 2 1

Länklistaimplementering i 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;
/* Skapa användardefinierad struktur för lagring av data i länkad lista */
struct Node
{
int data;
struct Node *next; // pekare till länkade noder i listan
};
struct Node* head = NULL; // Initialt finns inget element i listan, så head pekar ingenstans
/* funktion för att infoga och länka noder till listan */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // Allokering av minne dynamiskt
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* funktion för att visa listans data */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<” ”;
ptr = ptr->nästa;
}
}
int main()
{
insert(5); // infoga data i listan
insert(1);
insert(4);
insert(6);
insert(7);
insert(7);
cout<<”The linked list is: ”;
display();
return 0;
}

Output

The linked list is: 7 6 4 1 5

Videohandledning

Lämna ett svar

Lämna ett svar

Din e-postadress kommer inte publiceras.