Array ja Linkitetty lista ovat kaksi tapaa järjestää tiedot muistissa. Ennen kuin ymmärrät erot Array ja Linkitetty lista , katsomme ensin joukossa ja linkitetty lista .
jousenrakentaja
Mikä on array?
Tietorakenne, joka sisältää samantyyppiset elementit. Tietorakenne on tapa järjestää data; taulukko on tietorakenne, koska se järjestää tiedot peräkkäin. Joukko on iso muistipala, jossa muisti on jaettu pieniin-pieniin lohkoihin ja jokaiseen lohkoon voidaan tallentaa jonkin verran arvoa.
Oletetaan, että olemme luoneet taulukon, joka koostuu 10 arvosta, jolloin jokainen lohko tallentaa kokonaislukutyypin arvon. Jos yritämme tallentaa arvon erityyppiseen taulukkoon, se ei ole oikea taulukko ja aiheuttaa käännösaikavirheen.
Taulukkoilmoitus
Taulukko voidaan ilmoittaa seuraavasti:
data_type name of the array[no of elements]
Määrittääksesi taulukon, meidän on ensin määritettävä taulukon tyyppi ja sitten taulukon nimi. Hakasulkeiden sisällä meidän on määritettävä elementtien lukumäärä, jonka taulukon tulisi sisältää.
Ymmärretään esimerkin kautta.
int a[5];
Yllä olevassa tapauksessa olemme ilmoittaneet 5 elementin taulukon, jossa on ' a 'n nimi kokonaisluku tietotyyppi.
Mikä on linkitetty lista?
Linkitetty luettelo on kokoelma satunnaisesti tallennettuja solmuja. Jokainen solmu koostuu kahdesta kentästä, ts. tiedot ja linkki . Tässä data on kyseiseen solmuun tallennettu arvo, ja linkki on osoitin, joka sisältää seuraavan solmun osoitteen.
Erot taulukon ja linkitetyn luettelon välillä
Emme voi sanoa, mikä tietorakenne on parempi, eli taulukko vai linkitetty lista . Voi olla mahdollista, että yksi tietorakenne sopii paremmin yhteen vaatimuksiin, kun taas toinen tietorakenne on parempi toiselle vaatimukselle. On olemassa erilaisia tekijöitä, kuten tietorakenteelle usein suoritettavia operaatioita tai datan kokoa, ja muita tekijöitä, joiden perusteella tietorakenne valitaan. Nyt näemme joitain eroja taulukon ja linkitetyn luettelon välillä joidenkin parametrien perusteella.
1. Elementin käyttökustannukset
Jos kyseessä on taulukko, taulukon koosta riippumatta taulukko vie vakioajan päästäkseen elementtiin. Taulukossa elementit tallennetaan vierekkäin, joten jos tiedämme elementin kantaosoitteen, saamme helposti minkä tahansa taulukon elementin osoitteen. Meidän on suoritettava yksinkertainen laskutoimitus saadaksemme minkä tahansa taulukon elementin osoitteen. Joten taulukon elementin käyttäminen on O(1) ajan monimutkaisuuden kannalta.
Linkitetyssä luettelossa elementtejä ei tallenneta vierekkäin. Se koostuu useista lohkoista, ja jokainen lohko on esitetty solmuna. Jokaisessa solmussa on kaksi kenttää, eli yksi on tietokenttiä varten ja toinen tallentaa seuraavan solmun osoitteen. Löytääksemme minkä tahansa solmun linkitetystä luettelosta, meidän on ensin määritettävä ensimmäinen solmu, joka tunnetaan pääsolmuna. Jos meidän on löydettävä luettelosta toinen solmu, meidän on kuljettava ensimmäisestä solmusta, ja pahimmassa tapauksessa viimeisen solmun löytämiseksi kuljemme kaikkien solmujen läpi. Keskimääräinen tapaus elementtiin pääsylle on O(n).
Päättelemme, että taulukon elementin käyttökustannukset ovat alhaisemmat kuin linkitetyn luettelon. Siksi, jos meillä on vaatimuksia elementtien käyttämiselle, matriisi on parempi valinta.
mitä on klusterointi
2. Elementin lisäämisen kustannukset
Lisäyksessä voi olla kolme skenaariota:
Jos kyseessä on linkitetty luettelo, lisäämällä elementin linkitetyn luettelon alkuun luomme uuden solmun, ja ensimmäisen solmun osoite lisätään uuteen solmuun. Tällä tavalla uudesta solmusta tulee ensimmäinen solmu. Joten aika monimutkaisuus ei ole verrannollinen luettelon kokoon. Aikamonimutkaisuus olisi vakio, eli O(1).
Jos taulukko ei ole täynnä, voimme lisätä uuden elementin suoraan indeksin kautta. Tässä tapauksessa aikakompleksisuus olisi vakio, eli O(1). Jos taulukko on täynnä, meidän on ensin kopioitava taulukko toiseen taulukkoon ja lisättävä uusi elementti. Tässä tapauksessa aikamonimutkaisuus olisi O(n).
Jos haluat lisätä elementin linkitetyn luettelon loppuun, meidän on kuljetettava koko luettelo. Jos linkitetty lista koostuu n elementistä, niin aikamonimutkaisuus olisi O(n).
Oletetaan, että haluamme lisätä elementin kohtaan ithtaulukon sijainti; meidän on siirrettävä n/2-elementtejä oikealle. Siksi aika monimutkaisuus on verrannollinen elementtien lukumäärään. Aikamonimutkaisuus olisi O(n) keskimääräiselle tapaukselle.
linuxin pikakuvakkeet
Linkitetyn listan tapauksessa meidän on siirryttävä siihen kohtaan, jossa meidän on lisättävä uusi elementti. Tosin meidän ei tarvitse suorittaa minkäänlaista vaihtoa, vaan meidän on ajauduttava n/2-asentoon. Kuluva aika on verrannollinen n elementtien määrään, ja keskimääräisen tapauksen aikamonimutkaisuus olisi O(n).
Tuloksena oleva linkitetty luettelo on:
Taulukon toteuttaminen on helppoa verrattuna linkitettyyn luetteloon. Kun ohjelmaa luodaan linkitetyn luettelon avulla, ohjelma on alttiimpi virheille, kuten segmentointivika tai muistivuoto. Joten paljon huolellisuutta on noudatettava luotaessa ohjelmaa linkitetyssä luettelossa.
Linkitetty luettelo on kooltaan dynaaminen, kun taas matriisi on staattinen. Tässä staattinen ei tarkoita, että emme voi päättää kokoa ajon aikana, mutta emme voi muuttaa sitä, kun koko on päätetty.
3. Muistivaatimukset
Kuten taulukon elementit tallentuvat yhteen vierekkäiseen muistilohkoon, taulukko on kiinteän kokoinen. Oletetaan, että meillä on taulukko, jonka koko on 7 ja matriisi koostuu 4 elementistä, niin loput tilasta on käyttämätön. 7 elementin varaama muisti:
Muistitila = 7*4 = 28 tavua
Missä 7 on taulukon elementtien lukumäärä ja 4 on kokonaislukutyyppisten tavujen lukumäärä.
Linkitetyn listan tapauksessa käyttämätöntä muistia ei ole, mutta ylimääräinen muisti on osoitinmuuttujien käytössä. Jos data on kokonaislukutyyppiä, niin yhden solmun varaama kokonaismuisti on 8 tavua, eli 4 tavua datalle ja 4 tavua osoitinmuuttujalle. Jos linkitetty luettelo koostuu 4 elementistä, linkitetyn luettelon käyttämä muistitila olisi:
web-ajuri
Muistitila = 8*4 = 32 tavua
Linkitetty luettelo olisi parempi valinta, jos tietoosa on kooltaan suurempi. Oletetaan, että data on 16 tavua. Matriisin käyttämä muistitila olisi 16*7=112 tavua, kun taas linkitetty lista vie 20*4=80, tässä olemme määrittäneet 20 tavua 16 tavuksi tiedon kooksi plus 4 tavua osoitinmuuttujalle. Jos valitsemme suuremman datakoon, linkitetty luettelo kuluttaisi vähemmän muistia; muuten se riippuu tekijöistä, joita käytämme koon määrittämiseen.
Tarkastellaan eroja taulukon ja linkitetyn luettelon välillä taulukkomuodossa.
| Array | Linkitetty lista |
|---|---|
| Taulukko on kokoelma samantyyppisiä elementtejä. | Linkitetty lista on kokoelma objekteja, jotka tunnetaan solmuna ja jossa solmu koostuu kahdesta osasta, eli tiedosta ja osoitteesta. |
| Matriisielementit tallennetaan viereiseen muistipaikkaan. | Linkitetyt luetteloelementit voidaan tallentaa mihin tahansa muistiin tai tallentaa satunnaisesti. |
| Array toimii staattisen muistin kanssa. Tässä staattinen muisti tarkoittaa, että muistin koko on kiinteä eikä sitä voi muuttaa ajon aikana. | Linkitetty luettelo toimii dynaamisen muistin kanssa. Tässä dynaaminen muisti tarkoittaa, että muistin kokoa voidaan muuttaa ajon aikana tarpeidemme mukaan. |
| Taulukon elementit ovat toisistaan riippumattomia. | Linkitetyt luetteloelementit ovat riippuvaisia toisistaan. Koska jokainen solmu sisältää seuraavan solmun osoitteen, joten päästäksemme seuraavaan solmuun, meidän on käytettävä sen edellistä solmua. |
| Taulukko vie enemmän aikaa suoritettaessa mitä tahansa toimintoa, kuten lisäystä, poistamista jne. | Linkitetty luettelo vie vähemmän aikaa suoritettaessa mitä tahansa toimintoa, kuten lisäämistä, poistamista jne. |
| Pääsy mihin tahansa taulukon elementtiin on nopeampaa, koska taulukon elementtiä voidaan käyttää suoraan indeksin kautta. | Linkitetyn luettelon elementin käyttö on hitaampaa, koska se alkaa kulkea linkitetyn luettelon ensimmäisestä elementistä. |
| Jos kyseessä on taulukko, muisti varataan käännöshetkellä. | Jos kyseessä on linkitetty luettelo, muisti varataan ajon aikana. |
| Muistin käyttö on tehotonta taulukossa. Jos esimerkiksi taulukon koko on 6 ja taulukko koostuu vain 3 elementistä, loput tilasta jää käyttämättä. | Muistin käyttö on tehokasta linkitetyn listan tapauksessa, koska muistia voidaan varata tai vapauttaa ajon aikana vaatimuksemme mukaan. |