Linkitetty lista on tietojenkäsittelytieteen perustietorakenne, joka koostuu dataa sisältävistä solmuista ja linkkejä ("linkkejä") luettelon seuraavaan ja/tai edelliseen solmuun. [1] Perusetu taulukkoon verrattuna on rakenteellinen joustavuus: linkitetyn listan elementtien järjestys ei välttämättä ole sama kuin tietoelementtien järjestys tietokoneen muistissa [2] ja listan läpikulkujärjestys on aina sen sisäisten linkkien avulla.
Lineaarinen yksisuuntainen lista on tietorakenne, joka koostuu samantyyppisistä elementeistä, jotka on linkitetty peräkkäin osoittimien kautta. Jokaisella luettelon elementillä on osoitin seuraavaan elementtiin. Listan viimeinen elementti osoittaa NULL . Elementti, johon ei osoiteta, on luettelon ensimmäinen (head) elementti. Tässä kunkin solmun linkki osoittaa luettelon seuraavaan solmuun. Yksittäin linkitetyssä luettelossa voit siirtyä vain luettelon loppua kohti. Edellisen elementin osoitetta on mahdotonta saada selville nykyisen solmun sisällön perusteella.
Tietojenkäsittelytieteessä lineaarinen lista määritellään yleensä abstraktiksi tietotyypiksi (ADT), joka formalisoi käsitteen järjestetystä datakokoelmasta . Käytännössä lineaariset listat toteutetaan yleensä taulukoiden ja linkitettyjen listojen avulla. Joskus termiä "luettelo" käytetään myös epävirallisesti "linkitetyn luettelon" synonyyminä. Esimerkiksi tyypittämätön muuttuva lista ADT voidaan määritellä joukoksi konstruktori- ja perustoimintoja:
käyttämällä linkitettyä luetteloa:
struct list * l1 = ( struct list * ) malloc ( sizeof ( struct list )); l1 -> kenttä = 1 ; l1 -> next = ( struct list * ) malloc ( sizeof ( struct list )); l1 -> seuraava -> kenttä = 2 ; l1 -> seuraava -> seuraava = ( struct list * ) malloc ( sizeof ( struct list )); /* jne. */ Kaksinkertaisesti linkitetty luettelo (kaksinkertaisesti linkitetty luettelo)Tässä kunkin solmun linkit osoittavat luettelon edelliseen ja seuraavaan solmuun. Kuten yksitellen linkitetty luettelo, myös kaksoislinkitetty luettelo sallii vain peräkkäisen pääsyn elementteihin, mutta se sallii myös liikkumisen molempiin suuntiin. Tässä listassa elementtien poistaminen ja järjesteleminen on helpompaa, koska niiden listan elementtien osoitteet, joiden osoittimet ovat suunnattu muutettavaan elementtiin, ovat helposti saatavilla.
XOR linkitetty listaHarvoin käytetty.
Eräänlainen linkitetty lista on rengaslista (syklinen, suljettu). Se voi olla myös yksi- tai kaksoislinkitetty. Pyöreän listan viimeinen elementti sisältää osoittimen ensimmäiseen ja ensimmäinen (kaksoislinkitetyn luettelon tapauksessa) viimeiseen.
Pääsääntöisesti tällainen rakenne toteutetaan lineaarisen listan perusteella. Jokainen pyöreä luettelo tallentaa lisäksi osoittimen ensimmäiseen elementtiin. Tässä luettelossa ei ole viittausta NULL:iin.
On myös pyöreitä luetteloita, joissa on oma pääelementti, mikä helpottaa koko luettelon läpikulkua.
Linkitettyjen luetteloiden haitat johtuvat niiden pääominaisuudesta - peräkkäisestä pääsystä tietoihin:
Tietorakenteet | |
---|---|
Luettelot | |
puut | |
Laskee | |
muu |