Tietojenkäsittelyn perusteita: tietorakenteet – linkitetty lista

Linkitetty lista (linked list) on yksi yleisimmistä tietorakenteista ja se koostuu yhdestä tai useammasta elementistä, joissa on normaalin datan lisäksi ns. linkki seuraavaan elementtiin. Tietojenkäsittelyssä puhutaan usein myös solmuista. Kahteen suuntaan linkitetyssä listassa elementeillä on datan lisäksi linkki seuraavaan ja edelliseen elementtiin. Tosiasiassahan lista itsessään ei sisällä mainittua dataa vaan viitteen siihen, on helpompi esittää asia kuten sen yllä tein.

Tavallisesti linkitetystä listasta voidaan hakea tietty elementti vain liikkumalla ensimmäisestä elementistä kohti listan loppua elementti kerrallaan. Kahdensuuntaisessa listassa voidaan aloittaa alusta tai lopusta ja vaihtaa myös suuntaa.

Reaalielämän vertauksena voisi asian esittää:

Valitaan satunnaisesti henkilöitä maapallolta ja listataan heidät jonkinlaiseen järjestykseen. Jokaiselle kerrotaan, että kun hän saa keltaisen kirjekuoren, hänen tulee lähettää se seuraavalle listalla olevalle henkilölle. Henkilöstä ei kuitenkaan kerrota muuta kuin nimi ja osoite.

Jokainen listalla oleva henkilö on ”olio” joka tietää minne kirje edelleen lähettää. He eivät tiedä muista olioista tai siitä, kuka oli se edellinen olio joka kirjeen hänelle lähetti. Totta kai jokaiselle oliolle voidaan antaa erilaiset ohjeet toimia kuten olioille yleensäkin. Kahdensuuntaisessa listassa voidaan ohjeistaa lähettämään kirje myös edelliselle oliolle. Tällöin on myös toimitettava kaksi osoitetta yhden sijaan.

Tarpeesta riippuen, voidaan henkilö poistaa sen jälkeen listalta kun hän on oman osuutensa tehnyt, eli lähettänyt kirjeen seuraavalle listalla olevalle.

Advertisements

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out / Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out / Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out / Muuta )

Google+ photo

Olet kommentoimassa Google+ -tilin nimissä. Log Out / Muuta )

Muodostetaan yhteyttä palveluun %s