Ero yhdenmukaisesti linkitetyn luettelon ja kaksinkertaisesti linkitetyn luettelon välillä

Yksinkertaisesti linkitetty luettelo vs. kaksinkertaisesti linkitetty luettelo

Linkitetty luettelo on lineaarinen tietorakenne, jota käytetään tietokokoelman tallentamiseen. Yhdistetty luettelo allokoi muistin elementeilleen erikseen omassa muistilohkossaan ja kokonaisrakenne saadaan yhdistämällä nämä elementit ketjun linkkiksi. Yksittäisesti linkitetty luettelo koostuu solmujen sekvenssistä ja jokaisella solmulla on viittaus sekvenssin seuraavaan solmuun. Kaksinkertaisesti linkitetty luettelo sisältää solmusarjan, jossa jokainen solmu sisältää viittauksen seuraavaan solmuun sekä edelliseen solmuun.

Yksittäisesti linkitetty lista

Jokaisella erikseen linkitetyn luettelon elementillä on kaksi kenttää, kuten kuviossa 1 esitetään. Tietokenttä sisältää todellisen tallennetun datan ja seuraava kenttä viittaa ketjun seuraavaan elementtiin. Linkitetyn luettelon ensimmäinen elementti tallennetaan linkitetyn luettelon päähän.

Kuvio 2 kuvaa yhden linkitetyn luettelon, jossa on kolme elementtiä. Jokainen elementti tallentaa tietonsa ja kaikki elementit, paitsi viimeinen, tallentaa viittauksen seuraavaan elementtiin. Viimeisellä elementillä on nolla-arvo seuraavassa kentässä. Mihin tahansa luettelon elementtiin pääsee aloittamalla päästä ja seuraamalla seuraavaa osoitinta, kunnes saavutat vaaditun elementin.

Kaksinkertaisesti linkitetty luettelo

Jokaisella kaksinkertaisesti linkitetyn luettelon elementillä on kolme kenttää, kuten kuviossa 3 esitetään. Samoin kuin erillisesti linkitetyssä luettelossa, tietokenttä pitää tallennettua todellista dataa ja seuraava kenttä pitää viittauksen ketjun seuraavaan elementtiin. Lisäksi edellisessä kentässä on viittaus ketjun edelliseen elementtiin. Linkitetyn luettelon ensimmäinen elementti tallennetaan linkitetyn luettelon päähän.

Kuvio 4 kuvaa kaksinkertaisesti linkitetyn luettelon, jossa on kolme elementtiä. Kaikki välielementit tallentavat viittauksia ensimmäiseen ja edelliseen elementtiin. Luettelon viimeisellä elementillä on nolla-arvo seuraavassa kentässä ja luettelon ensimmäisellä elementillä on nolla-arvo edellisessä kentässä. Kaksinkertaisesti linkitetyt luettelot voidaan kulkea eteenpäin seuraamalla seuraavia viitteitä kussakin elementissä, ja samalla tavalla voidaan kulkea taaksepäin käyttämällä kunkin elementin aiempia viittauksia.

Mikä on ero Singly Linked List ja Doubly Linked List välillä?

Jokainen erillisesti linkitetyn luettelon elementti sisältää viittauksen luettelon seuraavaan elementtiin, kun taas jokainen kaksinkertaisesti linkitetyn luettelon elementti sisältää viittaukset seuraavaan elementtiin samoin kuin luettelon edelliseen elementtiin. Kaksinkertaisesti linkitetyt luettelot vaativat enemmän tilaa jokaiselle luettelon elementille, ja perustoiminnot, kuten lisääminen ja poistaminen, ovat monimutkaisempia, koska niiden on käsiteltävä kahta viitettä. Mutta kaksinkertaisesti linkittävät luettelot sallivat helpomman käsittelyn, koska se sallii luettelon siirtymisen eteen- ja taaksepäin.