Linkitetty lista¶

Yksi perusmekanismi dynaamisten tietorakenteiden toteuttamiseen on nk. linkitetty lista (linked list).

Linkitetyt listat muodostuvat tietuetyyppisistä (struct) alkioista, joista jokainen on varattu erikseen new-komennolla. Jokainen alkio sisältää listaan talletettavan hyötytiedon lisäksi osoittimen, jonka avulla listan seuraava alkio löydetään. Tämän lisäksi tarvitaan erillinen osoitintyyppinen muuttuja, jossa pidetään tallessa listan ensimmäisen alkion sijainti. Joskus on tehokkuussyistä hyödyllistä ylläpitää myös toista osoitinmuuttujaa, jossa on tallessa listan viimeisen alkion osoite.

Jos esimerkiksi halutaan tallentaa listaan tekstiä siten, että sähköpostiviestin jokainen rivi on listassa erillisenä alkiona, tarvittaisiin seuraava struct-tyyppi ja kirjanpito-osoittimet:

struct Listan_alkio {
    string  tekstirivi;
    Listan_alkio*  seuraavan_osoite;
};

Listan_alkio*  ensimmaisen_osoite;
Listan_alkio*  viimeisen_osoite;

Kun tällaiseen listaan lisätään kolme alkiota, näyttää tilanne seuraavalta:

Edellisessä havaintokuvassa dynaamisesti varattuja Listan_alkio-tyyppisiä tietueita on korostettu harmaalla taustalla. Lisäksi nullptr-arvo esitetään kuvissa yleensä “maadoituksena”.

Aina kun listaan lisätään uusi alkio, varataan new-komennolla tilaa tietueelle, joka sisältää lisättävänä olevan hyötytiedon lisäksi rakenteen toteuttamiseen liittyvää kirjanpitotietoa (siis osoittimen listan seuraavaan alkioon). Aina kun listasta poistetaan alkio, sille aiemmin varattu tila vapautetaan delete-komennolla.

Lisäksi sekä lisäys- että poistovaiheessa joudutaan päivittämään osoittimien arvoja niin, että niissä on tallessa oikeat muistiosoitteet.

Hyväksi todettu tapa listarakenteiden toteuttamiseen on se, että edellä esitetty tietuetyyppi ja osoittimet listan ensimmäiseen ja viimeiseen alkioon kätketään luokan private-osaan, ja toteutetaan listan käsittelyyn tarvittavat operaatiot luokan metodeina.

Monimutkaisemmatkin rakenteet ovat luonnollisesti mahdollisia (esim. puut ja verkot). Vain mielikuvitus asettaa rajat sen jälkeen, kun perusymmärtämys linkkikenttien käsittelystä on sisäistetty.

Tehtävälista C++-osoittimilla¶

Tutustu Qt Creatorissa projektiin examples/08/task_list. Jos haluat myös suorittaa ja editoida ohjelmakoodia, kopioi se student-hakemiston alle.

Projekti sisältää kolme ohjelmakooditiedostoa:

list.hh eli listaluokan julkinen rajapinta
main.cpp eli listaluokan käyttäjä
list.cpp eli listaluokan toteutus.

Pääohjelma ei sisällä mitään erityisen mielenkiintoista dynaamiseen muistinhallintaan liittyen, joten seuraavaksi käydään läpi listaluokan olennaisimpia osia.

list.hh:

rivit 12-13:

Listan on tarkoitus toimia siten, että uudet alkiot lisätään loppuun ja alkioiden poisto tapahtuu alusta. Kun alkio poistetaan, sen arvo tallentuu viiteparametriin removed_task.

rivi 17:

Ensimmäistä kertaa ollaan tilanteessa, jossa luokalle on pakko toteuttaa purkaja. Jos List-tyyppisen olion elinikä päättyy tilanteessa, jossa lista ei ole tyhjä, purkajan tehtävänä on vapauttaa varattuina olevat listan solut.

Purkajametodin nimi on C++:ssa sama kuin luokan nimi, mutta sen eteen on lisätty tilde-merkki (mato). Sitä kutsutaan kulissien takana automaattisesti, kun olion elinkaari päättyy.

rivit 20-23:

Määritellään tietuetyyppi, jonka avulla listan yksittäisten alkiot saadaan esitettyä. Koska List_item-tyyppi on määritelty luokan private-osassa, sitä ei voi käyttää muualla kuin luokan metodeissa.

rivit 25-26:

Kirjanpitojäsenmuuttujat, joiden tehtävänä on pitää tallessa listan ensimmäisen ja viimeisen alkion sijainti muistissa.

Tässä esimerkissä on toteutustavaksi valittu se, että myös listan viimeisen alkion osoitteesta pidetään kirjaa. Tämä on yleensä järkevää silloin, alkiot lisätään listan loppuun. Miksi?
list.cpp:

Rakentaja:

Rakentaja alustaa kummankin kirjanpitojäsenmuuttujan arvoksi nullptr:in, mikä tulkitaan aina jatkossa tarkoittamaan sitä, että listassa ei ole yhtään alkiota (siis se on tyhjä).

Purkaja:

Kun List-olion elinkaari päättyy, purkajaa kutsutaan automaattisesti. Sen tehtävän on vapauttaa kaikki listassa vielä olevat dynaamisesti varatut alkiot (List_item-tyyppisiä).

Koska lista on tässä esimerkissä toteutettu normaaleilla C++-osoittimilla, dynaamisen muistin vapauttaminen on ohjelmoijan vastuulla. Jos purkaja puuttuisi, muistia jäisi siis vapauttamatta.

Purkajan toimintaperiaate on, että jokaisella silmukan kierroksella listan alusta poistetaan yksi alkio ja sille varattu muisti vapautetaan.

Metodi print:

Listan tulostus on toteutettu “standardimekanismilla”, joka toimii aina, kun listan alkiot on tarpeen käydä läpi alusta loppuun.

Osoitinapumuuttuja asetetaan osoittamaan listan ensimmäiseen alkioon. Niin kauan kun sen arvo ei ole nullptr (miksi sen arvoksi väistämättä tulee lopulta nullptr?), tulostetaan osoitetun alkion sisältö. Lopuksi siirretään apuosoitin osoittamaan listan seuraavaan alkioon.

Metodi add_back:

Alkion lisääminen listaan on helpointa ymmärtää, kun piirrät itsellesi havaintokuvion, jonka avulla animoit, miten toimenpide etenee.

Perusidea on seuraava. Varataan dynaamisesti uusi List_item-tyyppinen tietue ja otetaan sen osoite talteen. Tämän jälkeen päivitetään kaikkia olennaisia osoittimia siten, että listan rakenne säilyy halutun mukaisena. Huomaa, kuinka lisäysoperaatio täytyy tehdä eri tavoin riippuen siitä, ollaanko tyhjään listaan lisäämässä ensimmäistä alkiota, vai onko listassa alkioita jo ennestään. (Miksi?)

Metodi remove_front:

Listasta poistetaan tässä toteutuksessa aina listan ensimmäinen alkio, eli siis se, johon first_ osoittaa. Ennen kuin poisto voidaan tehdä, pitää varmistua, että listassa on alkioita jäljellä. Jos ei ole, kyseessä virhe (paluuarvo false).

Varsinainen poisto tapahtuu siten, että ensimmäinen alkio otetaan pois listasta, eli siis päivitetään osoittimia siten, että first_-jäsenmuuttuja alkaa osoittamaan poistettavan alkion perässä tulevaan alkioon (tai nullptr:iin, jos poistettiin viimeinen alkio).

Osoitinpäivitysten jälkeen poistettavalle alkiolle varattu muisti vapautetaan.

Huomaa, kuinka taas pitää käsitellä hiukan eri tavoin ainoan alkion poisto ja poisto listasta jossa on enemmän alkioita.

Metodi is_empty:

Tämä metodi on yksinkertainen. Lista on tyhjä, jos first_ on nullptr, kuten rakentajan yhteydessä todettiin.

Yhteenveto¶

Linkitettyjä tietorakenteita toteutettaessa, pitää aina pitää mielessä kaikki tietorakenteen käsittelemiseen liittyvät erikoistapaukset. Tässä esimerkissä tilanteesta riippuen poisto ja lisäys on toteutettava hiukan eri tavoin.

Tyhjään listaan lisääminen vaatii eri järjestelyn kuin ei-tyhjään listaan lisääminen. Vastaavasti viimeisen jäljellä olevan alkion poisto pitää käsitellä toisin kuin muiden alkioiden poisto.

Jotta listan käsittely menisi monimutkaisemmissakin tilanteissa oikein, toteutusvaiheessa on aina syytä pysähtyä miettimään, mitkä seuraavista erikoistapauksista on tarpeen huomioida:

ensimmäisen alkion lisääminen tyhjään listaan
listan ainoan jäljellä olevan alkion poisto
listan alkuun lisääminen
listan ensimmäisen alkion poistaminen
alkion lisääminen listan keskelle
alkion poistaminen listan keskeltä
alkion lisääminen listan loppuun
alkion poistaminen listan lopusta.