Array vs Linked List – Array:n ja Linked List:n ero

Oletko koskaan miettinyt, miten tiedot tallennetaan tietokoneen muistiin? Et voi vain heittää dataa muistiin tekemättä sille kunnollista rakennetta.

Tietorakenteiden avulla voimme tarjota järjestetyn rakenteen datan tallentamiselle tietokoneen muistiin, jotta voimme käyttää ja hallita tallennettua dataa mahdollisimman tehokkaasti, käytämme tietorakenteita.

Kaikki ohjelmointikielet tarjoavat perustavanlaatuisia tietorakenteita, kuten int-, char-, float-, jne. Käyttäjän määrittelemien tietotyyppien avulla voimme kuitenkin luoda tietorakenteita tarpeen mukaan. Se on kuin kotimme rakentaminen tiilistä, voimme tehdä minkälaisen rakenteen haluamme.

Tässä artikkelissa tutustumme kahteen yleisimmin käytettyyn käyttäjän määrittelemään tietotyyppiin:

Array

Yksinkertaisin tietorakennetyyppi on Array, jota käytetään tallentamaan joukko samankaltaisia tietoja jatkuviin muistilohkoihin yhteisen otsikon tai muuttujan nimen alle. Sen yksinkertaisuuteen liittyy joitakin esteitä, kuten se tarvitsee jatkuvaa muistilohkoa, ja jos vapaata muistia ei ole saatavilla vierekkäisissä lohkoissa, matriisien käytöstä tulee tehotonta.

Matriisien esitys

Matriisien esitys (lähde)

Matriisien indeksointi alkaa 0:sta, ja jokaiseen matriisin elementtiin pääsee käsiksi sen indeksin avulla. Joukkoon kohdistuva toiminta on erittäin nopeaa, koska mihin tahansa elementtiin pääsee suoraan käsiksi joukon indeksoinnin avulla. Joukon nimi on joukon perusosoite ja kaikkiin muihin elementteihin voidaan päästä käsiksi perusosoitteen avulla, koska joukolle varattu muisti on peräkkäistä.

Linked List

Toisaalta yksinkertainen, mutta erittäin hyödyllinen tietorakenne, joka ei tarvitse peräkkäisiä muistilohkoja, on Linked List. Niitä käytetään tilanteissa, joissa on tarve varata muistia dynaamisesti eli ohjelman ajon aikana. Se voidaan havainnollistaa kuin juna, jossa on veturi (pää) ja kaikki vaunut (solmut) on linkitetty junan veturiin joko suoraan tai epäsuorasti muiden vaunujen kautta.

Linkitetyn listan esitys

Linkitetyn listan esitys (lähde)

Linkitetty lista on käyttäjän määrittelemä tietotyyppi, jossa kaikki listan solmut on linkitetty toisiinsa osoittimien avulla. Päästäksemme käsiksi mihin tahansa listan solmuun, meidän on kuljettava listaa lineaarisesti toisin kuin array, jossa voimme käyttää elementtejä suoraan.

Se on järjestetty kokoelma elementtejä, jotka on liitetty toisiinsa linkkien tai osoittimien avulla. Koko Fixed, kun se on kerran ilmoitettu, sitä ei voi muuttaa. Variable, sitä voidaan muuttaa ajon aikana. Muistin allokointi Vaatii vierekkäisiä muistilohkoja. Muistia voidaan allokoida satunnaisesti.

Käyttökohde Suoraa tai satunnaista käyttökohdetta, ts, Määritä matriisin indeksi tai alaindeksi. Seuraavasti käytetty, ts, Kierretään luettelon ensimmäisestä solmusta alkaen osoittimen avulla. Sisällyttäminen ja poistaminen Suhteellisen hidas, koska minkä tahansa elementin lisäämiseksi tai poistamiseksi on siirrettävä muita elementtejä, jotta tyhjä tila voidaan ottaa käyttöön tai tehdä tilaa. Nopeampi, helpompi ja tehokkaampi, koska tarvitaan vain solmun linkittäminen tai linkityksen poistaminen. Haku Binäärinen haku ja Lineaarinen haku Lineaarinen haku Extra-tilaa Extra-tilaa ei tarvita. Luettelon solmujen linkittämiseen käytetään osoittimia, jotka vaativat lisää tilaa. Muistin käyttö Tehoton Tehokas Tyypit Luettelo voi olla yksiulotteinen, kaksiulotteinen tai moniulotteinen. Luettelo voi olla yksi-, kaksi- tai ympyrälinkitetty.

Array-toteutus C++:ssa

.

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; // julistetaan kokonaislukujoukko, jonka koko on 5
arr=5; // annetaan arvot joukon alkioille
arr=4; // huomaa, että matriisin indeksointi alkaa 0:sta ja päättyy kokoon-1
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i++)
cout<<<arr<<<< ” ”; // tulostetaan matriisin elementit
return 0;
}

Tulostus

5 4 3 3 2 1

Linkitetyn listan toteutus C++:ssa

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;
/* Luodaan käyttäjän määrittelemä rakenne linkitetyn listan tietojen tallentamista varten */
struct Node
{
int data;
struct Node *next; // osoitin listan linkitetyille solmuille
};
struct Node* head = NULL; // Aluksi listassa ei ole yhtään elementtiä, joten head osoittaa ei minnekään
/* funktio, jolla lisätään ja linkitetään solmuja listaan */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // muistin varaaminen dynaamisesti
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* funktio, jolla näytetään listan tiedot */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<” ”;
ptr = ptr->next;
} }
}
int main()
{
insert(5); // tietojen lisääminen listaan
insert(1);
insert(4);
insert(6);
insert(7);
cout<<”Linkitetty lista: ”;
display();
return 0;
}

Output

Linkitetty lista on: 7 6 4 1 5

Video opetusohjelma

Leave a Reply

Vastaa

Sähköpostiosoitettasi ei julkaista.