Linkitetyt listat

---

Linkitetty lista on dynaaminen tietorakenne, jossa alkiot voivat sijaita eri puolilla muistia. Jokaisessa alkiossa on hyötytiedon lisäksi osoitin seuraavaan alkioon. Erillinen osoitin pitää kirjaa listan ensimmäisestä alkiosta; usein listan loppuun lisäämistä nopeutetaan tallentamalla myös viimeisen alkion osoite.

Esimerkiksi sähköpostiviestin rivit voi tallentaa listaan yksi rivi kutakin alkiota kohti:

struct Listan_alkio {
    string tekstirivi;
    shared_ptr<Listan_alkio> seuraavan_osoite;
};

shared_ptr<Listan_alkio> ensimmaisen_osoite;
shared_ptr<Listan_alkio> viimeisen_osoite;

Kun listaan lisätään alkio, make_shared luo uuden Listan_alkio-olion. Olio sisältää sekä varsinaisen tekstirivin että linkin seuraavaan alkioon. Lisäämisen ja poistamisen yhteydessä linkkejä ja alku- sekä loppuosoittimia päivitetään, jotta lista pysyy ehjänä.

Listan rakenne ja osoittimet kannattaa yleensä piilottaa luokan private-osaan. Käyttäjille tarjotaan jäsenfunktiot alkioiden lisäämiseen, poistamiseen ja tulostamiseen. Näin listan sisäinen toteutus ei pääse vahingossa rikkoutumaan ulkopuolisesta koodista.

Esimerkki listaluokasta

Tutustu Qt Creatorissa projektiin examples/06/task_list/. Jos haluat suorittaa tai muokata ohjelmaa, kopioi projekti student-hakemiston alle. Projektissa on kolme keskeistä tiedostoa:

• list.hh määrittelee listaluokan julkisen rajapinnan ja yksityisen toteutusrakenteen
• main.cpp käyttää listaluokkaa
• list.cpp sisältää listaluokan jäsenfunktioiden toteutukset

Pääohjelma ei sisällä muistinhallinnan kannalta olennaisia yksityiskohtia, joten huomio kannattaa keskittää listaluokan toteutukseen.

Listan esittäminen ja läpikäynti

Esimerkin listaluokassa alkioita lisätään loppuun ja poistetaan alusta. Yksittäinen List_item-tyyppi on luokan yksityinen tietue. Luokan jäsenmuuttujat first_ ja last_ pitävät kirjaa ensimmäisen ja viimeisen alkion sijainnista.

Rakentaja asettaa molemmat osoittimet arvoon nullptr, mikä tarkoittaa, että lista on tyhjä. Viimeisestä alkiosta kirjaa pitäminen on hyödyllistä, kun lisäys tehdään aina loppuun: uuden alkion voi liittää suoraan viimeiseen ilman, että koko lista täytyy ensin käydä läpi.

Tulostus ja muut koko listan läpikäyvät operaatiot noudattavat samaa mallia: aloitetaan ensimmäisestä alkiosta, käsitellään sen sisältö ja siirrytään seuraavan_osoite-linkin avulla seuraavaan. Läpäisy päättyy, kun osoitin on nullptr. Viimeisen alkion linkki on null, joten tämä päätepiste saavutetaan aina.

Lisääminen ja poistaminen

Lisäys loppuun etenee yleisesti näin:

1. Luodaan uusi alkio, jonka seuraavan alkion osoite on nullptr.
2. Jos lista on tyhjä, uusi alkio asetetaan sekä ensimmäiseksi että viimeiseksi.
3. Muussa tapauksessa nykyisen viimeisen alkion linkki asetetaan osoittamaan uuteen alkioon, ja viimeisen alkion osoitin päivitetään.

Tyhjään listaan lisääminen vaatii oman käsittelynsä, sillä silloin ei ole aiempaa viimeistä alkiota, jonka linkkiä voisi päivittää.

Alusta poistettaessa tarkistetaan ensin, onko lista tyhjä. Tyhjästä listasta poistaminen epäonnistuu. Muussa tapauksessa talletetaan poistettavan alkion sisältö tarvittaessa viiteparametriin ja siirretään ensimmäisen alkion osoitin seuraavaan alkioon. Jos poistettu alkio oli viimeinen, myös viimeisen alkion osoitin pitää asettaa arvoon nullptr.

shared_ptr hoitaa tässä muistista vapauttamisen: kun poistettu alkio ei enää ole minkään omistavan osoittimen saavutettavissa ja sen omistusmäärä putoaa nollaan, olio tuhoutuu. Muista silti päivittää linkit ja kirjanpito-osoittimet oikein.

Erikoistapaukset

Linkitettyjen rakenteiden virheet syntyvät usein siitä, että jokin rajatapaus jää käsittelemättä. Pysähdy suunnittelussa tarkistamaan ainakin nämä tilanteet:

• ensimmäisen alkion lisääminen tyhjään listaan
• listan ainoan alkion poistaminen
• alkion lisääminen tai poistaminen alusta
• alkion lisääminen tai poistaminen keskeltä
• alkion lisääminen tai poistaminen lopusta

Esimerkkiluokassa lisätään loppuun ja poistetaan alusta, mutta muiden toimintojen toteuttaminen tuo mukaan lisää osoittimien päivityksiä. Hahmottele muutokset piirtämällä lista ennen operaatiota ja sen jälkeen.

Katso video linkitetyistä listoista.