Yhdistetysti linkitetty luettelo vs. kaksinkertaisesti linkitetty luettelo
Linkitetty luettelo on lineaarinen tietorakenne, jota käytetään datakokoelman tallentamiseen. Linkitetty luettelo jakaa muistin elementteilleen erikseen omassa muistilohkossaan, ja kokonaisrakenne saadaan yhdistämällä nämä elementit ketjun linkkeinä. Yksin linkitetty luettelo koostuu solmujen sarjasta, ja jokaisella solmulla on viittaus sekvenssin seuraavaan solmuun. Kaksinkertaisesti linkitetty luettelo sisältää solmujen sarjan, jossa kukin solmu sisältää viittauksen seuraavaan solmuun sekä edelliseen solmuun.
Yksin linkitetty luettelo
Jokaisella yksittäisesti linkitetyn luettelon elementillä on kaksi kenttää, kuten kuvassa 1 on esitetty. Tietokentässä on varsinainen tallennettu data ja seuraavassa kentässä on viittaus ketjun seuraavaan elementtiin. Linkitetyn luettelon ensimmäinen osa tallennetaan linkitetyn luettelon päähän.
Kuva 2 kuvaa yhtenä linkitetyn luettelon, jossa on kolme elementtiä. Jokainen elementti tallentaa tietonsa ja kaikki paitsi viimeinen elementit viittaavat seuraavaan elementtiin. Viimeisellä elementillä on nolla-arvo seuraavalla kentällä. Mihin tahansa luettelon elementtiin pääsee aloittamalla päästä ja seuraamalla seuraavaa osoitinta, kunnes saavutat vaaditun elementin.
Epäillysti linkitetty luettelo
Jokaisella kaksoislinkityn luettelon elementillä on kolme kenttää, kuten kuvassa 3 on esitetty. Samoin kuin yksittäisesti linkitetyssä luettelossa, datakentässä on varsinaiset tallennetut tiedot ja seuraavassa kentässä viittaus ketjun seuraavaan elementtiin. Edellisessä kentässä on viittaus ketjun edelliseen elementtiin. Linkitetyn luettelon ensimmäinen osa tallennetaan linkitetyn luettelon päähän.
Kuva 4 kuvaa kaksinkertaisella linkitetyllä luettelolla, jossa on kolme elementtiä. Kaikki välielementit tallentavat viitteet ensimmäiseen ja edelliseen elementtiin. Luettelon viimeisellä elementillä on nolla-arvo seuraavalla kentällä ja luettelon ensimmäisellä elementillä nolla-arvo edellisessä kentässään. Kaksinkertaisesti linkitetty luettelo voidaan siirtää eteenpäin seuraamalla jokaisen elementin seuraavia viitteitä, ja vastaavasti voidaan liikkua taaksepäin käyttämällä kunkin elementin edellisiä viitteitä.
Mitä eroa on yksin linkitetyn luettelon ja kaksoislinkityn luettelon välillä?
Jokainen yksittäisesti linkitetyn luettelon elementti sisältää viittauksen luettelon seuraavaan elementtiin, kun taas kaksoislinkitetyn luettelon jokainen elementti sisältää viittauksia seuraavaan elementtiin sekä luettelon edelliseen elementtiin. Kaksinkertaisesti linkitetyt luettelot vaativat enemmän tilaa kullekin luettelon elementille, ja perustoiminnot, kuten lisäys ja poisto, ovat monimutkaisempia, koska niiden on käsiteltävä kahta viittausta. Mutta kaksinkertainen linkkiluettelo sallii helpomman manipuloinnin, koska se sallii luettelon liikkumisen eteen- ja taaksepäin.
