Yksi linkitetty luettelo vs. kaksoislinkitetty luettelo
Linkitetty luettelo on lineaarinen tietorakenne, jota käytetään datakokoelman tallentamiseen. Linkitetty lista varaa muistin elementeilleen erikseen omassa muistilohkossaan ja kokonaisrakenne saadaan linkittämällä nämä elementit linkkeinä ketjuun. Yksittäin linkitetty lista koostuu solmujen sekvenssistä ja jokaisella solmulla on viittaus sekvenssin seuraavaan solmuun. Kaksoislinkitetty luettelo sisältää solmusekvenssin, jossa jokainen solmu sisältää viittauksen seuraavaan solmuun sekä edelliseen solmuun.
Yksittäin linkitetty luettelo
Yksi linkitetyn luettelon jokaisessa elementissä on kaksi kenttää, kuten kuvassa 1 on esitetty. Datakenttä sisältää todelliset tallennetut tiedot ja seuraava kenttä sisältää viittauksen ketjun seuraavaan elementtiin. Linkitetyn luettelon ensimmäinen elementti tallennetaan linkitetyn luettelon pääksi.
Kuva 2 esittää erikseen linkitettyä luetteloa, jossa on kolme elementtiä. Jokainen elementti tallentaa tietonsa ja kaikki elementit paitsi viimeinen tallentavat viittauksen seuraavaan elementtiin. Viimeisellä elementillä on nolla-arvo seuraavassa kentässään. Mitä tahansa luettelon elementtiä pääsee käsiksi aloittamalla alusta ja seuraamalla seuraavaa osoitinta, kunnes saavutat vaaditun elementin.
Kaksoislinkitetty luettelo
Kaksoislinkitetyn luettelon jokaisessa elementissä on kolme kenttää, kuten kuvassa 3 näkyy. Samoin kuin yksitellen linkitetyssä luettelossa, tietokenttä sisältää todelliset tallennetut tiedot ja seuraava kenttä sisältää viittauksen ketjun seuraavaan elementtiin. Lisäksi edellinen kenttä sisältää viittauksen ketjun edelliseen elementtiin. Linkitetyn luettelon ensimmäinen elementti tallennetaan linkitetyn luettelon pääksi.
Kuva 4 esittää kaksinkertaisesti linkitettyä luetteloa, jossa on kolme elementtiä. Kaikki välielementit tallentavat viittauksia ensimmäiseen ja edelliseen elementtiin. Listan viimeisellä elementillä on tyhjä arvo seuraavassa kentässä ja luettelon ensimmäisellä elementillä on tyhjä arvo edellisessä kentässään. Kaksoislinkitetty lista voidaan kulkea eteenpäin seuraamalla kunkin elementin seuraavia viittauksia ja vastaavasti voidaan selata taaksepäin käyttämällä kunkin elementin aiempia viittauksia.
Mitä eroa on yksitellen linkitetyllä luettelolla ja kaksoislinkitetyllä luettelolla?
Jokainen yksitellen linkitetyn luettelon elementti sisältää viittauksen luettelon seuraavaan elementtiin, kun taas jokainen kaksoislinkitetyn luettelon elementti sisältää viittaukset seuraavaan elementtiin sekä luettelon edelliseen elementtiin. Kaksoislinkitetyt luettelot vaativat enemmän tilaa luettelon jokaiselle elementille, ja perustoiminnot, kuten lisääminen ja poistaminen, ovat monimutkaisempia, koska niissä on käsiteltävä kahta viittausta. Mutta kaksoislinkkiluettelot mahdollistavat helpomman käsittelyn, koska se mahdollistaa luettelon kulkemisen eteenpäin ja taaksepäin.
