Array vs Linked List – különbség az Array és Linked List között

Gondolkodtál már azon, hogyan tárolódnak az adatok a számítógép memóriájában? Nem dobhatunk csak úgy adatokat a memóriába anélkül, hogy megfelelő struktúrát hoznánk létre az adatok számára.

Az adatoknak a számítógép memóriájában való tárolásához szervezett struktúrát biztosítunk, hogy a tárolt adatokat a lehető leghatékonyabban tudjuk használni és kezelni, ezért használjuk az adatszerkezeteket.

A primitív típusú értékek tárolásához minden programozási nyelv alapvető adatszerkezeteket biztosít, mint például int, char, float stb. A felhasználó által definiált adattípusok használatával azonban igény szerint hozhatunk létre adatszerkezeteket. Ez olyan, mintha otthonunkat téglákból építenénk, bármilyen típusú struktúrát létrehozhatunk, amilyet csak akarunk.

Ezekben a cikkekben a két leggyakrabban használt felhasználó által definiált adattípust fogjuk látni:

Array

Az adatstruktúra legegyszerűbb típusa az Array, amely arra szolgál, hogy hasonló adatok halmazát folyamatos memóriablokkokban tároljuk egy közös címszó vagy változónév alatt. Egyszerűségével együtt jár néhány akadály, például folyamatos memóriablokkot igényel, és ha nem áll rendelkezésre szabad memória egybefüggő blokkban, akkor nem lesz hatékony a tömbök használata.

Tömb ábrázolás

Tömb ábrázolás (Forrás)

A tömbök indexelése 0-val kezdődik, és a tömb minden eleme az indexével érhető el. A tömbön végzett műveletek nagyon gyorsak, mivel a tömbindexelés segítségével bármely elem közvetlenül elérhető. A tömb neve a tömb alapcíme, és az összes többi elemet az alapcím segítségével lehet elérni, mivel a tömbhöz rendelt memória egymás után következik.

Linked List

A másik oldalon egy egyszerű, de nagyon hasznos adatszerkezet, amelynek nincs szüksége összefüggő memóriablokkokra, a Linked List. Ezeket olyan helyzetekben használják, amikor dinamikusan kell memóriát allokálni, vagyis a program futási ideje alatt. Úgy lehet elképzelni, mint egy vonatot, ahol van egy mozdony (fej), és az összes kocsi (csomópont) közvetlenül vagy más kocsikon keresztül közvetve kapcsolódik a mozdonyhoz.

Linkelt lista ábrázolása

Linkelt lista ábrázolása (Forrás)

A linkelt lista egy felhasználó által definiált adattípus, ahol a lista összes csomópontja mutató segítségével kapcsolódik. A lista bármely csomópontjának eléréséhez lineárisan kell végigjárnunk a listát, ellentétben a tömbökkel, ahol közvetlenül hozzáférhetünk az elemekhez.

Array vs Linked List – A tömb és a Linked List közötti különbség

Paraméterek Tömb Linkelt lista
Definíció Egy közös nevű, azonos adattípusú elemek gyűjteménye. Elemek rendezett gyűjteménye, amelyeket linkek vagy mutatók kötnek össze.
Size Fixed, egyszer deklarálva nem módosítható. Variable, futás közben módosítható.
Memória kiosztás Egybefüggő memóriablokkokat igényel. Véletlenszerű memória kiosztható.
Hozzáférés Közvetlen vagy véletlenszerű hozzáférés, ill, Adja meg a tömbindexet vagy az alindexet. Sorozatos hozzáférés, azaz, A lista első csomópontjától kezdve a mutatóval történő átjárás.
Beszúrás és törlés Viszonylag lassú, mivel bármely elem beszúrásához vagy törléséhez más elemeket kell eltolni, hogy elfoglalják az üres helyet vagy helyet csináljanak. Gyorsabb, egyszerűbb és hatékonyabb, mivel csak a csomópontok összekapcsolása vagy szétkapcsolása szükséges.
Keresés Bináris keresés és lineáris keresés Lineáris keresés
Extra hely Extra hely nem szükséges. A lista csomópontjainak összekapcsolásához mutatót használunk, ami extra helyet igényel.
Memória kihasználás Eredménytelen Eredményes
Típusok Egydimenziós, kétdimenziós vagy többdimenziós lehet. Egyszerűen, kétszeresen vagy körkörösen kapcsolt lista lehet.

Tömb implementáció C++-ban

.

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; // egy 5 méretű integer tömb deklarálása
arr=5; // értékek hozzárendelése a tömb elemeihez
arr=4; // vegyük észre, hogy a tömb indexelése 0-tól kezdődik és a méret-1-nél végződik
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i++)
cout<<arr<<<” “; // tömbelemek kiírása
return 0;
}

Kimenet

5 4 3 3 2 1

Linkelt lista megvalósítása 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;
/* Felhasználó által definiált struktúra létrehozása a linkelt lista adatainak tárolására */
struct Node
{
int data;
struct Node *next; // mutató a lista linkelt csomópontjaira
};
struct Node* head = NULL; // Kezdetben nincs elemük a listában, ezért a head sehova sem mutat
/* függvény a lista csomópontjainak beszúrására és összekapcsolására */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // memória dinamikus allokálása
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* függvény a lista adatainak megjelenítésére */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<” “;
ptr = ptr->next;
} }
}
int main()
{
insert(5); // adatok beszúrása a listába
insert(1);
insert(4);
insert(6);
insert(7);
cout<<“A linkelt lista: “;
display();
return 0;
}

Output

A linkelt lista a következő:

Video Tutorial

Leave a Reply

Vélemény, hozzászólás?

Az e-mail-címet nem tesszük közzé.