Kahteen suuntaan linkitetty lista¶

Toteutetaan kokonaislukujoukko kahteen suuntaan linkitettynä listana, johon alkiot on talletettu kasvavassa järjestyksessä. Lisäksi, jos joukkoon yritetään lisätä luku, joka on joukossa jo entuudestaan, lisäys epäonnistuu (siis jokainen luku voi olla joukossa korkeintaan yhden kerran).

Esimerkiksi joukko, joka koostuu alkioista 2, 5, 6 ja 10, näyttää seuraavalta:

Edellisessä havaintokuvassa shared_ptr-osoittimet on esitetty valkoisina ympyröinä ja normaaliosoittimet mustina.

Ohjelmakoodissa listan ensimmäiseen alkioon osoittava jäsenmuuttuja ja jokaisessa alkiossa seuraavan alkion osoitteen sisältävä kenttä on toteutettu shared_ptr-tyypin avulla. Syynä tähän on se, että listaa toteutettaessa ei tarvitse huolehtia listan alkioiden vapauttamisesta delete-käskyllä.

Miksi viimeiseen alkioon osoittava jäsenmuuttuja ja listan alkiota edeltävään alkioon osoittava kenttä on ollut kuitenkin järkevää toteuttaa tavallisena osoittimena?

Tutki esimerkkiohjelmaa, jonka löydät hakemistosta examples/09/two_way_list. Lista on toteutettuna tiedostoissa two_way_list.hh ja two_way_list.cpp.

Koodi on melkoisen pitkä, eikä sitä ole mielekästä käydä tässä läpi rivi riviltä. Lisäyksen ja poiston suorittavat funktiot on kommentoitu kohtalaisesti keskeisimmiltä osiltaan, joten niitä pystyy tutkimaan itse. Seuraavassa kuitenkin muutama yleinen huomio toteutuksesta.

• Linkkikentät (siis osoittimet) listan alkioissa on jouduttu toteuttamaan siten, että toinen on tyypiltään shared_ptr ja toinen normaaliosoitin, seuraavista syistä.

  • Tyypin shared_ptr avulla ohjelmoijan ei tarvitse itse huolehtia dynaamisen muistin vapautuksesta.

  • Toisaalta jos listan alkiossa kumpikin osoitin olisi shared_ptr-tyyppinen, muistia ei koskaan vapautettaisi, koska peräkkäiset alkiot osoittaisivat toisiinsa.

    Tämä on yleisestikin shared_ptr-tyypin heikkous: Yksinomaan sitä käyttämällä ei voi toteuttaa rakenteita, joihin sisältyy osoitinsilmukoita (A osoittaa B:hen ja B osoittaa A:han, tai jokin pidempi ketju).

  • Listan viimeiseen alkioon osoittava jäsenmuuttuja taas on tyypiltään normaaliosoitin, koska kun ei-tyhjästä listasta poistetaan viimeisenä oleva alkio (rivit 103–104 tiedostossa two_way_list.cpp), kyseinen jäsenmuuttuja pitää asettaa osoittamaan alkuperäiseen toiseksi viimeiseen alkioon (siis poistetun alkion edeltäjään):

    last_ = last_->prev;
    

    Jos last_ ei olisi normaaliosoitin, jouduttaisiin edellä tilanteeseen, jossa normaaliosoitin olisi tarve sijoittaa shared_ptr-osoittimeen muutoin kuin alustuksen yhteydessä. Tämä on vaarallista ja johtaa lähes poikkeuksetta ongelmiin.

• Aina kun shared_ptr-osoittimia on tarpeen käsitellä samassa lausekkeessa normaaliosoittimien kanssa, shared_ptr-oliosta saadaan sen osoittama muistiosoite normaaliosoittimena get-metodilla. Saadun arvon voi sijoittaa normaaliosoitinmuuttujaan ja sitä voidaan vertailla normaaliosoittimen kanssa.

  Metodilla get saatua normaaliosoitinta ei saa itse vapauttaa delete:llä, koska se sotkee shared_ptr:n sisäisen kirjanpidon.

• Kannattaa myös laittaa merkille, kuinka sekä lisäyksen että poiston yhteydessä jouduttiin tutkimaan varsin useita erikoistapauksia, joista puhuttiin materiaaliosion 8.4.2 lopussa.

• Aina kun käsitellään vähänkään yhteen suuntaan linkitettyä listaa monimutkaisempia osoitinrakenteita, päädytään lähes väistämättä lausekkeisiin, jotka ovat seuraavan muotoisia:

  a->b->c
  

  Eli -> -operaattoria joudutaan kirjoittamaan samaan lausekkeeseen perätysten.

  Tässä ei varsinaisesti ole mitään kummallista. C++:n laskujärjestyssäännöt määräävät, että lauseketta tulkitaan vasemmalta oikealle.

  Jos asiaa mitenkään helpottaa, nuolioperaattorin paikalle voi mielessään korvata tekstin: “osoittaman tietueen kentän nimeltään”. Edellinen esimerkki siis tulkittaisin: a:n osoittaman tietueen kentän nimeltään b osoittaman tietueen kentän nimeltään c arvo.